doi: 10.1007/BF02460704.
Complexity of protein folding
Affiliations
- PMID: 8281132
- DOI: 10.1007/BF02460704
Item in Clipboard
Complexity of protein folding
Bull Math Biol.
1993 Nov.
Abstract
It is believed that the native folded three-dimensional conformation of a protein is its lowest free energy state, or one of its lowest. It is shown here that both a two- and three-dimensional mathematical model describing the folding process as a free energy minimization problem is NP-hard. This means that the problem belongs to a large set of computational problems, assumed to be very hard ("conditionally intractable"). Some of the possible ramifications of this result are speculated upon.
Similar articles
-
Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications.Bull Math Biol. 1993 Nov;55(6):1183-98. doi: 10.1007/BF02460703. Bull Math Biol. 1993. PMID: 8281131
-
Kinetics of protein folding. A lattice model study of the requirements for folding to the native state.J Mol Biol. 1994 Feb 4;235(5):1614-36. doi: 10.1006/jmbi.1994.1110. J Mol Biol. 1994. PMID: 8107095
-
A framework for describing topological frustration in models of protein folding.J Mol Biol. 2006 Sep 22;362(3):605-21. doi: 10.1016/j.jmb.2006.07.054. Epub 2006 Jul 29. J Mol Biol. 2006. PMID: 16930616
-
Circular dichroism.Methods Enzymol. 1995;246:34-71. doi: 10.1016/0076-6879(95)46006-3. Methods Enzymol. 1995. PMID: 7538625 Review. No abstract available.
-
Roadmap methods for protein folding.Methods Mol Biol. 2008;413:219-39. doi: 10.1007/978-1-59745-574-9_9. Methods Mol Biol. 2008. PMID: 18075168 Review.
Cited by
-
Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications.Bull Math Biol. 1993 Nov;55(6):1183-98. doi: 10.1007/BF02460703. Bull Math Biol. 1993. PMID: 8281131
-
Parallel computation with molecular-motor-propelled agents in nanofabricated networks.Proc Natl Acad Sci U S A. 2016 Mar 8;113(10):2591-6. doi: 10.1073/pnas.1510825113. Epub 2016 Feb 22. Proc Natl Acad Sci U S A. 2016. PMID: 26903637 Free PMC article.
-
Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems.Interface Focus. 2018 Dec 6;8(6):20180034. doi: 10.1098/rsfs.2018.0034. Epub 2018 Oct 19. Interface Focus. 2018. PMID: 30443332 Free PMC article. Review.
-
A continuous-time MaxSAT solver with high analog performance.Nat Commun. 2018 Nov 19;9(1):4864. doi: 10.1038/s41467-018-07327-2. Nat Commun. 2018. PMID: 30451849 Free PMC article.
-
Differential evolution for protein folding optimization based on a three-dimensional AB off-lattice model.J Mol Model. 2016 Oct;22(10):252. doi: 10.1007/s00894-016-3104-z. Epub 2016 Sep 30. J Mol Model. 2016. PMID: 27696088
References
MeSH terms
Substances
LinkOut - more resources
Miscellaneous