A TABU SEARCH STRATEGY FOR FINDING LOW ENERGY STRUCTURES OF PROTEINS IN HP-MODEL*
Błażewicz Jacek 1,2, Dill Ken 3, Łukasiak Piotr 1,2, Miłostan Maciej 1
1 Institute of Computing Science, Poznań University ofTechnology
Piotrowo 3a, 60-965 Poznań, Poland
Maciej.Milostan@cs.put.poznan.pl
2 Institute of Bioorganic Chemistry, Polish Academy of Sciences
Noskowskiego 12, 61-704Poznań, Poland
3 Department of Pharmaceutical Chemistry, University of California
San Francisco, California, USA
Received:
Rec. 18 November 2003
DOI: 10.12921/cmst.2004.10.01.07-19
OAI: oai:lib.psnc.pl:555
Abstract:
HP-model is one of the most successful and well-studied simplified lattice models of protein
folding. It uses mathematical abstraction of proteins for hiding many aspects of the folding process and works as hypothesis generator. Due to the NP-hardness results of the protein folding problem many approximation algorithms, have been used to solve it. In the paper, the method for finding low energy conformations of proteins, based on the tabu search strategy, has been proposed. The algorithm has been extensively tested and the tests showed its very good performance.
References:
[1] C. B. Anfinsen, E. Haber, M. Sela, F. H. White, Jr., The kinetics of formation of native ribonuclease during oxidation of the reduced polypeptide chain, Proc. Natl. Acad. Sci. USA 47,
1309-1314 (1961).
[2] C. B. Anfinsen, Principles that govern the folding of protein chains, Science 181, 223-230 (1973).
[3] T. C. Beutler, K. A. Dill, A fast conformational search strategy for finding low energy structures of model proteins, Protein Sci. 5, 2037-2043 (1996).
[4] B. Berger, T. Leighton, Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete, J. Comp. Biol. 5(1), 27-40 (1998).
[5] P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, M. Yannakakis, On the complexity of proteinfolding, Proc. 1998 STOC, andJ. Comp. Biol.. 5(2) (1998)
[6] K. A. Dill, Theory for the folding and stability of globular proteins, Biochemistry 24, 1501-1509 (1985).
[7] K. A. Dill, S. Bomberg, K. Yue, K. M. Fiebig, D. P. Yee, P. D. Thomas, H. S. Chan, Principles of
proteinfolding: Aperspectivefrom simple exact models, Protein Sci. 4, 561-602 (1995).
[8] K. A. Dill, Polymer principles andproteinfolding, Protein Sci. 8, 1166-1180 (1999).
[9] F. Glover, Tabu Search – Parti, ORSA J. Comp. 1, 190-206 (1989).
[10] F. Glover, Tabu Search Fundamentals and Uses, Graduated School of Business, University of Colorado, Condensed version published in Mathematical Programming: State of the Art, Birge and Murty (eds.) 64-92 (1994). A Tabu Search Strategy for Finding Low Energy Structures of Proteins in HP-model 19
[11] F. Glover, Tabu Search and Adaptive Memory Programing – Advances, Applications and Challenges. Interfaces in Computer Science an Operations Research (1996), Kluwer Academic
Publishers, 1-75.
[12] F. Glover, M. Laguna, Tabu Search. Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publishing, Oxford, 70-141.
[13] F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers (1997), Boston, USA, 1-357.
[14] W. E. Hart, S. Istrail, Fast protein folding in the hydrophobic-hydrophilic model. within threeeights of optimal, J. Comp. Biol. 3(1), 53-96 (1996).
[15] C. Levinthal, Are there pathways for proteinfolding? Chem. Phys. 65, 44-45 (1968).
[16] N. Lesh, M. Mitzenmacher, S. Whitesides, A complete and effective move setfor simplifiedprotein folding, RECOMB Proc. 188-195 (2003).
[17] K. F. Lau, K. A. Dill, A lattice statistical mechanics model of the conformational and sequence space of proteins, Macromolecules 22, 3986-3997 (1989).
[18] J. T. Ngo, J. Marks, M. Karplus, Computational complexity, protein structure prediction, and the Levinthal paradox. in The protein folding problem and tertiary structure prediction, edited by K. M. Merz and S. M. Le Grand, Birkhauser, Boston (1994).
[19] E. M. O’Toole, A. Z. Panagiotopoulos, Monte Carlo simulation of folding transitions of simple model proteins using a chain growth algorithm, J. Chem. Phys. 97, 8644-8652 (1992).
[20] L. Toma, S. Toma, Contact Interactions Method: A new algorithm for proteinfolding simulations, Protein Sci. 5, 147-153 (1996).
[21] R. Unger, J. Moult, Genetic algorithms for protein folding simulations, J. Mol. Biol. 231, 75-81 (1993).
[22] R. Unger, J. Moult, Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications, Bull. Math. Biol. 55(6) 1183-1198 (1993).
[23] K. Yue, K. A. Dill, Sequence-structure relationships in proteins and copolymers, Phys. Rev. E
48(3) 2267-2278 (1993).
[24] K. Yue, K. M. Fiebig, P. D. Thomas, H. S. Chan, E. L. Shakhnovich, K. A. Dill, A test of lattice
proteinfolding algorithms, Proc. Natl. Acad. Sci. USA 92, 325-329 (1995).
HP-model is one of the most successful and well-studied simplified lattice models of protein
folding. It uses mathematical abstraction of proteins for hiding many aspects of the folding process and works as hypothesis generator. Due to the NP-hardness results of the protein folding problem many approximation algorithms, have been used to solve it. In the paper, the method for finding low energy conformations of proteins, based on the tabu search strategy, has been proposed. The algorithm has been extensively tested and the tests showed its very good performance.
[1] C. B. Anfinsen, E. Haber, M. Sela, F. H. White, Jr., The kinetics of formation of native ribonuclease during oxidation of the reduced polypeptide chain, Proc. Natl. Acad. Sci. USA 47,
1309-1314 (1961).
[2] C. B. Anfinsen, Principles that govern the folding of protein chains, Science 181, 223-230 (1973).
[3] T. C. Beutler, K. A. Dill, A fast conformational search strategy for finding low energy structures of model proteins, Protein Sci. 5, 2037-2043 (1996).
[4] B. Berger, T. Leighton, Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete, J. Comp. Biol. 5(1), 27-40 (1998).
[5] P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccolboni, M. Yannakakis, On the complexity of proteinfolding, Proc. 1998 STOC, andJ. Comp. Biol.. 5(2) (1998)
[6] K. A. Dill, Theory for the folding and stability of globular proteins, Biochemistry 24, 1501-1509 (1985).
[7] K. A. Dill, S. Bomberg, K. Yue, K. M. Fiebig, D. P. Yee, P. D. Thomas, H. S. Chan, Principles of
proteinfolding: Aperspectivefrom simple exact models, Protein Sci. 4, 561-602 (1995).
[8] K. A. Dill, Polymer principles andproteinfolding, Protein Sci. 8, 1166-1180 (1999).
[9] F. Glover, Tabu Search – Parti, ORSA J. Comp. 1, 190-206 (1989).
[10] F. Glover, Tabu Search Fundamentals and Uses, Graduated School of Business, University of Colorado, Condensed version published in Mathematical Programming: State of the Art, Birge and Murty (eds.) 64-92 (1994). A Tabu Search Strategy for Finding Low Energy Structures of Proteins in HP-model 19
[11] F. Glover, Tabu Search and Adaptive Memory Programing – Advances, Applications and Challenges. Interfaces in Computer Science an Operations Research (1996), Kluwer Academic
Publishers, 1-75.
[12] F. Glover, M. Laguna, Tabu Search. Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publishing, Oxford, 70-141.
[13] F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers (1997), Boston, USA, 1-357.
[14] W. E. Hart, S. Istrail, Fast protein folding in the hydrophobic-hydrophilic model. within threeeights of optimal, J. Comp. Biol. 3(1), 53-96 (1996).
[15] C. Levinthal, Are there pathways for proteinfolding? Chem. Phys. 65, 44-45 (1968).
[16] N. Lesh, M. Mitzenmacher, S. Whitesides, A complete and effective move setfor simplifiedprotein folding, RECOMB Proc. 188-195 (2003).
[17] K. F. Lau, K. A. Dill, A lattice statistical mechanics model of the conformational and sequence space of proteins, Macromolecules 22, 3986-3997 (1989).
[18] J. T. Ngo, J. Marks, M. Karplus, Computational complexity, protein structure prediction, and the Levinthal paradox. in The protein folding problem and tertiary structure prediction, edited by K. M. Merz and S. M. Le Grand, Birkhauser, Boston (1994).
[19] E. M. O’Toole, A. Z. Panagiotopoulos, Monte Carlo simulation of folding transitions of simple model proteins using a chain growth algorithm, J. Chem. Phys. 97, 8644-8652 (1992).
[20] L. Toma, S. Toma, Contact Interactions Method: A new algorithm for proteinfolding simulations, Protein Sci. 5, 147-153 (1996).
[21] R. Unger, J. Moult, Genetic algorithms for protein folding simulations, J. Mol. Biol. 231, 75-81 (1993).
[22] R. Unger, J. Moult, Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications, Bull. Math. Biol. 55(6) 1183-1198 (1993).
[23] K. Yue, K. A. Dill, Sequence-structure relationships in proteins and copolymers, Phys. Rev. E
48(3) 2267-2278 (1993).
[24] K. Yue, K. M. Fiebig, P. D. Thomas, H. S. Chan, E. L. Shakhnovich, K. A. Dill, A test of lattice
proteinfolding algorithms, Proc. Natl. Acad. Sci. USA 92, 325-329 (1995).
