PROTEIN-FOLDING IN THE HYDROPHOBIC-HYDROPHILIC (HP) MODEL IS NP-COMPLETE

One of the simplest and most popular biophysical models of protein fol ding 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), Ch ains of amino acids are configured as self-avoiding walks on the 3D cu bic lattice, where an optimal conformation maximizes the number of adj acencies 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 me ans that the protein folding problem belongs to a large set of problem s that are believed to be computationally intractable.