Diversity Control in Genetic Algorithms for Protein Structure Prediction

• Vinicius Tragante do Ó USP
• Renato Tinós USP

Abstract

In recent years, there is a growing interest in using Genetic Algorithms (GAs) in the protein structure prediction problem. However, the search space in this problem is very complex, what results in premature convergence of the GAs in their standard form, as the population generally gets trapped into local optima. Based on this fact, the use of two different strategies that can help GAs to maintain or increase the diversity of the population in the protein structure prediction problem are investigated in this paper. These strategies are Hypermutation and Random Immigrants. A new form of codification of the protein structure in the GA using sorted angles database is still proposed. Experimental results with Crambin (PDB code 1CRN), Met-Enkephalin (PDB code 1PLW), and DNA-Ligand (PDB code 1ENH) show that strategies to increase or maintain the population diversity are interesting for the protein structure prediction problem.

Keywords: Genetic Algorithms, Hypermutation, Random Immigrants, Protein Structure Prediction

References

Bindewald, E., Hesser, J., Manner, R. (1998) “Implementing genetic algorithms with sterical constrains for protein structure prediction”, In Proceedings of International Conference on Parallel Problem Solving from Nature (PPSN V), 959–967, Amsterdam, Netherlands.

Cobb, H.G., Grefenstette, J.J. (1993) “Genetic algorithms for tracking changing environments”, In 5th International Conference on Genetic Algorithms, Morgan Kaufmann, 523-530.

Cui, Y., Chen, R., Wong, W. (1998) “Protein Folding Simulation With Genetic Algorithm and Supersecondary Structure Constraints”, PROTEINS: Structure, Function, and Genetics, 31:247–257.

Fukuyama, Y., Chiang, H., Miu, K. (1996) “Parallel genetic algorithm for service restoration in electric power distribution systems”, International Journal of Electrical Power and Energy Systems, 18(2):111–119.

Gabriel, P., Lima, T., Delbem, A., Faccioli, R., Silva, I. (2007) “Pure ab initio evolutionary approach to protein structure prediction”, In International Symposium on Mathematical and Computation Biology. BIOMAT 2007.

Kaiser Jr., C.E., Lamont, G.B., Merkle, L.D., Gates Jr., G.H., Patcher, R. (1997) “Polypeptide structure prediction: Real-valued versus binary hybrid genetic algorithms”, In Proceedings of the ACM Symposium on Applied Computing (SAC), pages 279–286, San Jose, CA.

Lehninger, A.L., Nelson, D.L., Cox, M.M. (2005) Principles of Biochemistry 4 ed., Freeman, New York.

Linden, R. (2006) Algoritmos Genéticos. Ed. Brasport, Brasil.

M. Mitchell. (1996) An Introduction to Genetic Algorithms. Bradford Books.

Nicosia, G., Stracquadanio, G. (2008) “Generalized Pattern Search Algorithm for Peptide Structure Prediction”, Biophysical Journal 95(10):4988 - 4999.

Pedersen, J., Moult, J. (1996) “Genetic algorithms for protein structure prediction”, Current Opinion in Structural Biology, 6(2):227–231.

Pierce, N.A., Winfree, E. (2002) “Protein Design is NP-hard”, Protein Engineering, 15 (10):779-782.

Ponder, J. et al. (1998) TINKER: Software Tools for Molecular Design. Department of Biochemistry and Molecular Biophysics, Washington University School of Medicine, St. Louis, MO.

Ramachandran, G.N., Sasisekharan, V. (1968) “Conformation of polypeptides and proteins”, Advances in Protein Chemistry 23:283-438.

Schulze-Kremer, S. (1993) “Genetic Algorithms for Protein Tertiary Structure Prediction”, Lecture Notes in Computer Science: Machine Learning: ECML-93, 262279.

Sheik, S.S.; Ananthalakshmi, P.; Bhargavi, G.R.; Sekar, K. (2003) “CADB: Conformation Angles DataBase of proteins”, Nucleic Acids Research 31(1):448-451.

Taniguchi, E., Noritake, M., Yamada, T., Izumitani, T. (1999) “Optimal size and location planning of public logistics terminals”, Transportation Research Part E, 35(3):207–222.

Tragante, V., Tinós, R. (2008) “Impact of Database Sorting on the Efficiency of Genetic Algorithms in Protein Structure Prediction”, In International Symposium on Mathematical and Computation Biology (BIOMAT’2008), Campos do Jordão, Brazil.

Tuffery, P., Etchebest, C., Hazout, S., Lavery, R. (1991) “A new approach to the rapid determination of protein side chain conformations”, Journal of Biomolecular Structure & Dynamics, 8(6):1267–89.

Vavak, F., Fogarty, T.C. (1996) “A comparative study of steady state and generational genetic algorithms for use in nonstationary environments”, In AISB Workshop on Evolutionary Computing, Lecture Notes in Computer Science, Springer, 1143:297–304.

Yang, J., Honavar V. (1998) “Feature subset selection using a genetic algorithm”, In: Feature Extraction, Construction and Selection: a data mining perspective, 117-136. Kluwer.