The algorithmics of folding proteins on lattices. (English) Zbl 1038.92013
Summary: It should be possible to predict the fold of a protein into its native conformation, once we are given the sequence of the constituent amino acids. This is known as the protein structure prediction problem and is sometimes referred to as the problem of deciphering the second half of the genetic code. While large proteins fold in nature in seconds, computational chemists and biologists have found that folding proteins to their minimum energy conformations is a challenging unsolved optimization problem. Computational complexity theory has been useful in explaining, at least partially, this (Levinthal’s) paradox. The pedagogic cross-disciplinary survey by J. T. Ngo, J. Marks and M. Karplus, Computational complexity, protein structure prediction and the Levinthal paradox (1994), provides an excellent starting point for non-biologists to take a plunge into the problem of folding proteins. Since then, there has been remarkable progress in the algorithmics of folding proteins on discrete lattice models, an account of which is presented herein.
MSC:
| 92C40 | Biochemistry, molecular biology |
References:
| [1] | R. Agarwala, S. Batzogloa, V. Dancik, S.E. Decatur, S. Hannenhalli, M. Farach, S. Muthukrishnan, S. Skiena, Local rules for protein folding on a triangular lattice and generalised hydrophobicity, RECOMB (1997) 1-2.; R. Agarwala, S. Batzogloa, V. Dancik, S.E. Decatur, S. Hannenhalli, M. Farach, S. Muthukrishnan, S. Skiena, Local rules for protein folding on a triangular lattice and generalised hydrophobicity, RECOMB (1997) 1-2. · Zbl 1321.92051 |
| [2] | Atkins, J.; Hart, W. E., On the intractability of protein folding with a finite alphabet of amino acids, Algorithmica, 25, 279-294 (1999) · Zbl 0951.68516 |
| [3] | R. Backofen, The protein structure prediction problem: a constraint optimisation approach using a new lower bound, J. Constraints (2000).; R. Backofen, The protein structure prediction problem: a constraint optimisation approach using a new lower bound, J. Constraints (2000). · Zbl 0976.68067 |
| [4] | Berger, B.; Leighton, T., Protein folding in the hydrophobic-hydrophilic model is NP complete, J. Comput. Biol., 5, 27-40 (1998) |
| [5] | L.T. Biegler, T.F. Coleman, A.R. Conn, F.N. Santosa (Eds.), Large scale optimization with applications, Part III: molecular structure and optimization, IMA Vol. Math. Appl. 94 (1997).; L.T. Biegler, T.F. Coleman, A.R. Conn, F.N. Santosa (Eds.), Large scale optimization with applications, Part III: molecular structure and optimization, IMA Vol. Math. Appl. 94 (1997). · Zbl 0872.00044 |
| [6] | S. Bromberg, K. Dill, Side chain entropy and packing in proteins, Protein Sci. 3 (1994) 997-1009.; S. Bromberg, K. Dill, Side chain entropy and packing in proteins, Protein Sci. 3 (1994) 997-1009. |
| [7] | Chandru, V.; Ganesh, S.; Rao, M. R., Folding proteins on lattices: an integer programming approach, (Groetschel, M., Festschrift for Professor Manfred Padberg (2002), Springer: Springer Berlin) · Zbl 1100.92018 |
| [8] | P. Clote, Protein folding, the Levinthal paradox and rapidly mixing Markov chains, ICALP. Springer Lecture Notes in Computer Science 1644 (1999) 240-249.; P. Clote, Protein folding, the Levinthal paradox and rapidly mixing Markov chains, ICALP. Springer Lecture Notes in Computer Science 1644 (1999) 240-249. · Zbl 1037.92016 |
| [9] | Crescenzi, P.; Goldman, D.; Papadimitrou, C.; Piccolboni, A.; Yannakakis, M., On the complexity of protein folding, J. Comput. Biol., 5, 423-446 (1998) |
| [10] | Dill, K. A., Biochemistry, 24, 1501 (1985) |
| [11] | Dill, K. A.; Bromberg, S.; Yue, K.; Fiebig, K. M.; Yee, D. P.; Thomas, P. D.; Chan, H. S., Principles of protein foldinga perspective from simple exact models, Protein Sci., 4, 561-602 (1995) |
| [12] | A.S. Fraenkel, Complexity of protein folding, Bull. Math. Biol. 55 (1993) 1199-1210.; A.S. Fraenkel, Complexity of protein folding, Bull. Math. Biol. 55 (1993) 1199-1210. · Zbl 0791.92010 |
| [13] | Garey, M. R.; Johnson, D. S., Computers and Intractability—A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [14] | Hart, W. E.; Istrail, S., Fast protein folding in the hydrophobic-hydrophilic model within three-eights of optimal, J. Comput. Biol., 3, 53-96 (1996) |
| [15] | Hart, W. E.; Istrail, S., Robust Proofs of NP-hardness for protein foldinggeneral lattices and energy potentials, J. Comput. Biol., 4, 1, 1-22 (1997) |
| [16] | Hart, W. E.; Istrail, S., Lattice and off-lattice side chain models of protein foldinglinear time structure prediction better than 86 |
| [17] | V. Heun, Approximate protein folding in the HP side chain model on extended cubic lattices, Proceedings of the European Symposium on Algorithms, 1999.; V. Heun, Approximate protein folding in the HP side chain model on extended cubic lattices, Proceedings of the European Symposium on Algorithms, 1999. · Zbl 0936.92021 |
| [18] | Lau, K. F.; Dill, K. A., A lattice statistical mechanics model of the conformation and sequence spaces of proteins, Macromolecules, 22, 3986-3997 (1989) |
| [19] | Lau, K. F.; Dill, K. A., Theory for protein mutability and biogenesis, Proc. Natl Acad. Sci. USA, 87, 638-642 (1990) |
| [20] | Lipman, D.; Wilber, J., Proc. Roy. Soc. London, 245, 8 (1991) |
| [21] | A. Newman, A new algorithm for protein folding in the HP model, in: Proceedings of the 13th ACM-SIAM, Symposium on Discrete Algorithms, 2002.; A. Newman, A new algorithm for protein folding in the HP model, in: Proceedings of the 13th ACM-SIAM, Symposium on Discrete Algorithms, 2002. · Zbl 1052.92026 |
| [22] | Ngo, J. T.; Marks, J., Computational complexity of a problem in molecular-structure prediction, Protein Eng., 5, 4, 313-321 (1992) |
| [23] | Ngo, J. T.; Marks, J.; Karplus, M., Computational Complexity, Protein Structure Prediction and the Levinthal Paradox (1994), Birkhauser: Birkhauser Basel |
| [24] | A. Nayak, A. Sinclair, U. Zwick, Spatial codes and the hardness of string folding problems, Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 639-648.; A. Nayak, A. Sinclair, U. Zwick, Spatial codes and the hardness of string folding problems, Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 639-648. · Zbl 0929.68128 |
| [25] | P.M. Pardalos, D. Shalloway, G.L. Xue, (Eds.), Global minimization of nonconvex energy functions: molecular conformation and protein folding, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. Vol. 23, American Mathematical Society.; P.M. Pardalos, D. Shalloway, G.L. Xue, (Eds.), Global minimization of nonconvex energy functions: molecular conformation and protein folding, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. Vol. 23, American Mathematical Society. · Zbl 0831.00024 |
| [26] | Paterson, M.; Przytycka, T., On the complexity of string folding, Discrete Appl. Math., 71, 217-230 (1996) · Zbl 0879.92010 |
| [27] | Šali, A.; Shakhnovich, E.; Karplus, M., How does a protein fold?, Nature, 369, 248-251 (1994) |
| [28] | Šali, A.; Shakhnovich, E.; Karplus, M., Kinetics of protein foldinga lattice model study of the requirements for folding to the native state, J. Mol. Biol., 235, 1614-1636 (1994) |
| [29] | Sinclair, A., Algorithms for Random Generation and Counting: A Markov Chain Approach (1993), Birkhäuser: Birkhäuser Basel · Zbl 0780.68096 |
| [30] | Unger, R.; Moult, J., Finding the lowest free energy conformation of a protein is a NP-hard problem: proof and implications, Bull. Math. Biol., 55, 1183-1198 (1993) · Zbl 0791.92011 |
| [31] | Unger, R.; Moult, J., Genetic algorithms for protein folding simulations, J. Mol. Biol., 231, 1, 75-81 (1993) |
| [32] | R. Unger, J. Moult, A genetic algorithm for three dimensional protein folding simulations, Proceedings of the 5th International Conference on Genetic Algorithms, 1993, pp. 581-588.; R. Unger, J. Moult, A genetic algorithm for three dimensional protein folding simulations, Proceedings of the 5th International Conference on Genetic Algorithms, 1993, pp. 581-588. |
| [33] | Yue, K.; Dill, K., Folding proteins with a simple energy function and extensive conformational searching, Protein Sci., 5, 254-261 (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
