Genetic algorithm applied to protein structure prediction using the 3D-HP Side Chain model

• César Manuel Vargas Benítez UTFPR
• Heitor S. Lopes UTFPR

Abstract

This work presents a parallel genetic algorithm (PGA) for the protein folding problem, using the 3DHP-SC model. This model has been sparsely studied in the literature due to its complexity. A new fitness function was proposed, based on the free-energy and compacity of the folding. Since there is no benchmark available to date, a set of 5 sequences was used, based on a simpler model. The PGA obtained biologically coherent results, suggesting its adequacy for the problem. Future work will include new knowledge-based genetic operators and the expansion of the benchmark.

Keywords: Genetic Algorithm, Bioinformatics, Protein Folding, 3DHP-SC

References

Armstrong Junior, N., Lopes, H., and Lima, C. (2007). Reconfigurable computing for accelerating protein folding simulations. Lecture Notes in Computer Science, 4419:314–325.

Berger, B. and Leighton, F. (1998). Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology, 5(1):27–40.

Cantú-Paz, E. (2000). Efficient and Accurate Parallel Genetic Algorithms. Springer.

Dill, K. (1985). Theory for the folding and stability of globular proteins. Biochemistry, 24(6):1501–1509.

Krasnogor, N., Hart, W., Smith, J., and Pelta, D. (1999). “Protein structure prediction with evolutionary algorithms”. In International Genetic and Evolutionary Computation Conference (GECCO), volume 4, pages 1596–1601.

Li, M. S., Klimov, D. K., and Thirumalai, D. (2002). Folding in lattice models with side chains. Computer Physics Communications, 147(1-2):625–628.

Lopes, H. (2008). “Evolutionary algorithms for the protein folding problem: a review and current trends.”. In Smolinski, T., Milanova, M., and Hassanien, A.-E., editors, Applications of Computational Intelligence in Bioinformatics and Biomedicine: Current Trends and Open Problems, volume I, pages 297–315, Heidelberg. Springer-Verlag.

Maruo, M., Lopes, H., and Delgado, M. (2005). Self-adapting evolutionary parameters: encoding aspects for combinatorial optimization problems. Lecture Notes in Computer Science, 3448:154–165.

Michalewicz, Z. (1996). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin, 3rd edition.

Scapin, M. and Lopes, H. (2008). “A hybrid genetic algorithm for the protein folding problem using the 2D-HP lattice model.”. In Yang, A., Shan, Y., and Thu, L., editors, Success in Evolutionary Computation, number 92 in Studies in Computational Intelligence, pages 205–224, Heidelberg. Springer-Verlag.

Yue, K. and Dill, K. (1993). Sequence-structure relationships in proteins and co-polymers. Physical Review E., 48(3):2267–2278.