Complexity of protein folding
- 1 November 1993
- journal article
- Published by Springer Nature in Bulletin of Mathematical Biology
- Vol. 55 (6) , 1199-1210
- https://doi.org/10.1007/bf02460704
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 problems 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 results are speculated upon.Keywords
This publication has 19 references indexed in Scilit:
- Experimental quantum cryptography: the dawn of a new era for quantum cryptography: the experimental prototype is working]ACM SIGACT News, 1989
- Quantum computational networksProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1989
- Biochemical Topology: Applications to DNA Recombination and ReplicationScience, 1986
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1985
- Structural domains in proteins and their role in the dynamics of protein functionProgress in Biophysics and Molecular Biology, 1983
- Conjugate codingACM SIGACT News, 1983
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- On the ground states of the frustration model of a spin glass by a matching method of graph theoryJournal of Physics A: General Physics, 1980
- Principles that Govern the Folding of Protein ChainsScience, 1973
- Refinement of protein conformations using a macromolecular energy minimization procedureJournal of Molecular Biology, 1969