A tabu search strategy for finding low energy structures of proteins in HP - model

• Autorzy: Błażewicz J. , Łukasiak P. , Miłostan M. , Dill K.
• Języki publikacji: EN

Abstrakty

EN

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.

• Wydawca: Institute of Bioorganic Chemistry Scientific Publishers OWN, Polish Academy of Sciences
• Czasopismo: Computational Methods in Science and Technology
• Rocznik: 2004
• Tom: Vol. 10, nr 1
• Strony: 7--19
• Opis fizyczny: Bibliogr. 24 poz., rys.

Twórcy

autor

Błażewicz J.

• Institute of Computing Science, Poznań University of Technology Piotrowo 3a, 60-965 Poznań, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences Noskowskiego 12, 61-704 Poznań, Poland

autor

Łukasiak P.

• Institute of Computing Science, Poznań University of Technology Piotrowo 3a, 60-965 Poznań, Poland
• Institute of Bioorganic Chemistry, Polish Academy of Sciences Noskowskiego 12, 61-704 Poznań, Poland

autor

Miłostan M.

• Institute of Computing Science, Poznań University of Technology Piotrowo 3a, 60-965 Poznań, Poland

autor

Dill K.

• Department of Pharmaceutical Chemistry, University of California San Francisco, California, USA

Bibliografia

• [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).