Berger B, Leighton T
Mathematics Department and Laboratory for Computer Science, MIT, Cambridge, MA 02139, USA.
J Comput Biol. 1998 Spring;5(1):27-40. doi: 10.1089/cmb.1998.5.27.
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.
蛋白质折叠最简单且最流行的生物物理模型之一是疏水-亲水（HP）模型。HP模型通过将氨基酸标记为疏水（非极性用H表示）或亲水（极性用P表示）来抽象蛋白质折叠中的疏水相互作用。氨基酸链被配置为三维立方晶格上的自回避行走，其中最优构象使H之间的邻接数最大化。本文表明，立方晶格上HP模型下的蛋白质折叠问题是NP完全问题。这意味着蛋白质折叠问题属于一大类被认为计算上难以处理的问题。
