title: Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications.
abstract: The protein folding problem and the notion of NP-completeness and NP-hardness are discussed. A lattice model is suggested to capture the essence of protein folding. For this model we present a proof that finding the lowest free energy conformation belongs to the class of NP-hard problems. The implications of the proof are discussed and we suggest that the natural folding process cannot be considered as a search for the global free energy minimum. However, we suggest an explanation as to why, for many proteins, the native functional conformation may coincide with the lowest free energy conformation.
authors.affiliation: Center for Advanced Research in Biotechnology, Maryland Biotechnology Institute, University of Maryland, Rockville 20850.
authors.forename: R
authors.initials: R
authors.lastname: Unger
authors.forename: J
authors.initials: J
authors.lastname: Moult
mesh_terms: D000595:Amino Acid Sequence; D008433:Mathematics; D008958:Models, Molecular; D008962:Models, Theoretical; D008969:Molecular Sequence Data; D011487:Protein Conformation; D017510:Protein Folding; D011506:Proteins / Q000737:chemistry*; D013816:Thermodynamics
chemical_list: D011506:Proteins