Artificial Intelligence in Medicine
Volume 35, Issue 1 , Pages 135-145 , September 2005

Application of tabu search strategy for finding low energy structure of protein

  • Jacek Błażewicz

      Affiliations

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

      Affiliations

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

      Affiliations

    • Institute of Computing Science, Poznań University of Technology, Piotrowo 3a, 60-965 Poznań, Poland
    • Corresponding Author InformationCorresponding author. Tel.: +48 61 665 2826; fax: +48 61 877 1525.

Received 18 November 2004 ,Revised 24 January 2005 ,Accepted 22 February 2005.

References 

  1. Anfinsen CB, Haber E, Sela M, White FH. The kinetics of formation of native ribonuclease during oxidation of the reduced polypeptide chain. Proc Natl Acad Sci USA. 1961;47:1309–1314
  2. Anfinsen CB. Principles that govern the folding of protein chains. Science. 1973;181:223–230
  3. Branden C, Tooze J. Introduction to protein structure. 2nd ed. Garland Science Publishing; 1999. p. 89–120.
  4. Levinthal C. Are there pathways for protein folding?. Chem Phys. 1968;65:44–45
  5. Glover F, Laguna M. Tabu search. In: Boston, USA: Kluwer Academic Publishers; 1997;p. 1–357
  6. Unger R, Moult J. Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications. Bull Math Biol. 1993;55(6):1183–1198
  7. Crescenzi P, Goldman D, Papadimitriou C, Piccolboni A, Yannakakis M. On the complexity of protein folding. Proceedings of the 1998 STOC. J Comput Biol. 1998;5(3):409–422
  8. Berger B, Leighton T. Protein folding in the hydrophobic–hydrophilic (HP) model is NP-complete. J Comput Biol. 1998;5(1):27–40
  9. Dill KA. Theory for the folding and stability of globular proteins. Biochemistry. 1985;24:1501–1509
  10. Dill KA, Bomberg S, Yue K, Fiebig KM, Yee DP, Thomas PD, et al. Principles of protein folding: a perspective from simple exact models. Protein Sci. 1995;4:561–602
  11. Dill KA. Polymer principles and protein folding. Protein Sci. 1999;8:1166–1180
  12. Lesh N, Mitzenmacher M, Whitesides S. A complete and effective move set for simplified protein folding. RECOMB Proc. 2003;188–195
  13. Miłostan M, Łukasiak P, Dill KA, Błażewicz . A tabu search strategy for finding low energy structures of proteins in HP-model. Curr Comput Mol Biol RECOMB. 2003;205–206
  14. Pardalos PM, Liu X, Xue G. Protein conformation of a lattice model using tabu search. J Global Opt. 1997;11(1):55–68
  15. Beutler TC, Dill KA. A fast conformational search strategy for finding low energy structures of model proteins. Protein Sci. 1996;5:2037–2043
  16. Glover F. Tabu search, Part I. ORSA J Comput. 1989;1:190–206
  17. Glover F. Tabu search and adaptive memory programming—advances, applications and challenges. In: Interfaces in computer science an operations research. Kluwer Academic Publishers; 1996;p. 1–75
  18. Glover F, Laguna M, Tabu search. Modern heuristic techniques for combinatorial problems. Oxford: Blackwell Scientific Publishing; 1993. p. 70–141.
  19. Bł ażewicz J, Dill KA, Łukasiak P, Miłostan M. A tabu search strategy for finding low energy structures of proteins in HP-model. Comput Meth Sci Technol. 2004;10(1):7–19
  20. Toma L, Toma S. Contact interactions method: a new algorithm for protein folding simulations. Protein Sci. 1996;5:147–153
  21. Unger R, Moult J. Genetic algorithms for protein folding simulations. J Mol Biol. 1993;231:75–81

PII: S0933-3657(05)00050-3

doi: 10.1016/j.artmed.2005.02.001

Artificial Intelligence in Medicine
Volume 35, Issue 1 , Pages 135-145 , September 2005

Article Tools

* Image Usage & Resolution