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

DOI10.1007/BF02460703zbMath0791.92011WikidataQ52388449 ScholiaQ52388449MaRDI QIDQ1319879

Ron Unger, John Moult

Publication date: 11 July 1994

Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)

zbMATH Keywords

NP-completenessNP-hardnesslattice modelglobal free energy minimumlowest free energy conformationnative functional conformationprotein folding problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40) Computational methods for problems pertaining to biology (92-08)

Related Items

Long proteins with unique optimal foldings in the H-P model, Search optimization, funnel topography, and dynamical criticality on the string landscape, Computational complexity of the landscape. I., An integer programming model for protein structure prediction using the 3D-HP side chain model, A review of Monte Carlo simulations of polymers with PERM, A filter-and-fan approach to the 2D HP model of the protein folding problem, A quadratic approximation for protein sequence to structure mapping., Memetic algorithms: The polynomial local search complexity theory perspective, On the complexity of string folding, Complexity of protein folding, The algorithmics of folding proteins on lattices., Approximate protein folding in the HP side chain model on extended cubic lattices

Cites Work

• Some simplified NP-complete graph problems
• Complexity of protein folding
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item