Format

Send to

Choose Destination
J Comput Biol. 1998 Spring;5(1):27-40.

Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.

Author information

1
Mathematics Department and Laboratory for Computer Science, MIT, Cambridge, MA 02139, USA.

Abstract

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.

PMID:
9541869
DOI:
10.1089/cmb.1998.5.27
[Indexed for MEDLINE]

Supplemental Content

Loading ...
Support Center