Finding the lowest free energy conformation of a protein is an NP-hard problem: Proof and implications

• DOI: 10.1007/bf02460703
• Publication Date: 2006-08-09T00:50:26Z
• Authors: Ron Unger; John Moult
• Keywords: Energy landscape; Folding (DSP implementation); Completeness (order theory)

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.