Hart W E, Istrail S
Sandia National Laboratories, Algorithms and Discrete Mathematics Department, Albuquerque, New Mexico 87185-1110, USA.
J Comput Biol. 1997 Spring;4(1):1-22. doi: 10.1089/cmb.1997.4.1.
This paper addresses the robustness of intractability arguments for simplified models of protein folding that use lattices to discretize the space of conformations that a protein can assume. We present two generalized NP-hardness results. The first concerns the intractability of protein folding independent of the lattice used to define the discrete protein-folding model. We consider a previously studied model and prove that for any reasonable lattice the protein-structure prediction problem is NP-hard. The second hardness result concerns the intractability of protein folding for a class of energy formulas that contains a broad range of mean force potentials whose form is similar to commonly used pair potentials (e.g., the Lennard-Jones potential). We prove that protein-structure prediction is NP-hard for any energy formula in this class. These are the first robust intractability results that identify sources of computational complexity of protein-structure prediction that transcend particular problem formulations.
本文探讨了用于蛋白质折叠简化模型的难处理性论证的稳健性，该模型使用晶格来离散化蛋白质可能呈现的构象空间。我们给出了两个广义的NP难结果。第一个涉及与用于定义离散蛋白质折叠模型的晶格无关的蛋白质折叠难处理性。我们考虑一个先前研究过的模型，并证明对于任何合理的晶格，蛋白质结构预测问题都是NP难的。第二个难结果涉及一类能量公式的蛋白质折叠难处理性，这类能量公式包含广泛的平均力势，其形式类似于常用的对势（例如，Lennard-Jones势）。我们证明对于该类中的任何能量公式，蛋白质结构预测都是NP难的。这些是首批稳健的难处理性结果，它们确定了超越特定问题表述的蛋白质结构预测计算复杂性的来源。
