Protein Folding in the Hydrophobic-Hydrophilic (HP) Model is NP-Complete

1 January 1998

journal article
research article
Published by Mary Ann Liebert Inc in Journal of Computational Biology

Vol. 5 (1) , 27-40
https://doi.org/10.1089/cmb.1998.5.27

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.

Keywords

This publication has 11 references indexed in Scilit:

Local Rules for Protein Folding on a Triangular Lattice and Generalized Hydrophobicity in the HP Model
Journal of Computational Biology, 1997
On the complexity of string folding
Discrete Applied Mathematics, 1996
Fast Protein Folding in the Hydrophobic–Hydrophilic Model within Three-Eighths of Optimal
Journal of Computational Biology, 1996
Principles of protein folding — A perspective from simple exact models
Protein Science, 1995
Funnels, pathways, and the energy landscape of protein folding: A synthesis
Proteins-Structure Function and Bioinformatics, 1995
The protein threading problem with sequence amino acid interaction preferences is NP-complete
Protein Engineering, Design and Selection, 1994
Complexity of protein folding
Bulletin of Mathematical Biology, 1993
Computational complexity of a problem in molecular structure prediction
Protein Engineering, Design and Selection, 1992
Three-Dimensional Circuit Layouts
SIAM Journal on Computing, 1986
Theory for the folding and stability of globular proteins
Biochemistry, 1985