Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete
Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete
复制标题
DOI：
10.1089/cmb.1998.5.27
复制
发表时间：
1998-03-01
影响因子：
1.7
通讯作者：
Leighton, T
中科院分区：
文献类型：
--
作者：
Berger, B;Leighton, T
蛋白质折叠的最简单和最流行的生物物理模型之一是疏水-亲水（HP）模型。HP模型通过将氨基酸标记为疏水性来抽象蛋白质折叠中的疏水相互作用（H代表非极性）或亲水性（P表示极性），氨基酸链被配置为3D立方晶格上的自避免行走，其中最佳构象使H之间的邻接数最大化，在本文中，在HP模型下的立方格子上的蛋白质折叠问题被证明是NP完全的，这意味着蛋白质折叠问题属于一个被认为是计算上难以解决的问题的大集合。
One of the simplest and most popular biophysical models of protein folding is the hydrophobic-hydrophilic (HP) model. The HP model abstracts the hydrophobic interaction in protein folding by labeling the amino acids as hydrophobic (H for nonpolar) or hydrophilic (P for polar), Chains of amino acids are configured as self-avoiding walks on the 3D cubic lattice, where an optimal conformation maximizes the number of adjacencies between H's, In this paper, the protein folding problem under the HP model on the cubic lattice is shown to be NP-complete, This means that the protein folding problem belongs to a large set of problems that are believed to be computationally intractable.