Special Issue on Bioinformatics; Guest Editor: J. J. P. TsaiNo Access

EFFECTIVE COMPUTATIONAL REUSE FOR ENERGY EVALUATIONS IN PROTEIN FOLDING

EUNICE E. SANTOS

Department of Computer Science, Virginia Polytechnic Institute & State University, Blacksburg, VA 24061, USA

Search for more papers by this author

and

EUGENE SANTOS, JR.

Thayer School of Engineering, Dartmouth College, Hanover, NH 03755, USA

Search for more papers by this author

https://doi.org/10.1142/S0218213006002904Cited by:5 (Source: Crossref)

Abstract

Predicting native conformations using computational protein models requires a large number of energy evaluations even with simplified models such as hydrophobic-hydrophilic (HP) models. Clearly, energy evaluations constitute a significant portion of computational time. We hypothesize that given the structured nature of algorithms that search for candidate conformations such as stochastic methods, energy evaluation computations can be cached and reused, thus saving computational time and effort. In this paper, we present a caching approach and apply it to 2D triangular HP lattice model. We provide theoretical analysis and prediction of the expected savings from caching as applied this model. We conduct experiments using a sophisticated evolutionary algorithm that contains elements of local search, memetic algorithms, diversity replacement, etc. in order to verify our hypothesis and demonstrate a significant level of savings in computational effort and time that caching can provide.

Keywords:

Remember to check out the Most Cited Articles!
Check out Notable Titles in Artificial Intelligence.

References

K. A. Dillet al., Protein Sci 4, 561 (1995). Crossref, Web of Science, Google Scholar
B. Berger and T. Leighton, Journal of Computational Biology 5(1), 27 (1998). Crossref, Web of Science, Google Scholar
N. Krasnogor et al. , Multimeme algorithms for protein structure prediction , Proceedings of Parallel Problem Solving From Nature , Lecture Notes in Computer Science . Google Scholar
E. Santos Jr. , K. J. Kim and E. E. Santos , Effective search of the energy landscape for protein folding , Proceedings of the Genetic and Evolutionary Computing Conference, GECCO 2003 , Lecture Notes in Computer Science (LNCS) 2723 ( Springer-Verlag , 2003 ) . Google Scholar
E. Santos Jr. , K. J. Kim and E. E. Santos , Local minima-based exploration for off-lattice protein folding , Proceedings of the IEEE Computer Society Computational Systems Boinformatics Conference . Google Scholar
M. Milostan et al. , A tabu search strategy for finding low energy structures of proteins in hp-model , RECOMB Poster Proceedings . Google Scholar
A. Shmygelska , R. Aguirre-Hernández and H. H. Hoos , An ant colony optimization algorithm for the 2d hp protein folding problem , Proceedings of the Third International Workshop, ANTS 2002 , Lecture Notes in Computer Science (LNCS) 2463 ( Springer-Verlag , 2002 ) . Google Scholar
E. E. Santos and E. Santos Jr, International Journal of Artificial Intelligence Tools 10(1-2), 273 (2001). Link, Google Scholar
B. P. Blackburne and J. D. Hirst, J. of Chemical Physics 115(4), 1934 (2001). Google Scholar
E. E. Santos and E. Santos Jr., Reducing the computational load of energy evaluations for protein folding, Proceedings of the Fourth IEEE Symposium on Bioinformatics and Bioengineering BIBE '04 pp. 79–88. Google Scholar
P. Crescenziet al., Journal of Computational Biology 5(3), 423 (1998). Crossref, Web of Science, Google Scholar
E. Bornberg-Bauer, Simple folding model for hp lattice proteins, Proceedings of Bioinformatics German Conference on Bioinformatics GCB '96 (1997) pp. 125–136. Google Scholar
W. E. Hart and S. Istrail, Fast protein folding in the hydrophobic-bydrophilic model within three-eighths of optimal, Proceedings of Twenty-seventh Annual ACM Symposium on Theory of Computing (1995) pp. 157–168. Google Scholar
R. Unger and J. Moult, Journal of Molecule Biology 231, 75 (1993). Crossref, Web of Science, Google Scholar
R. Agarwalaet al., Journal of Computational Biology 4(2), 275 (1997). Crossref, Web of Science, Google Scholar