Abstract
This work applies the methodology of the Universal Evolutionary Global Optimization, UEGO, to solve the protein structure optimization problem based on the HP model. The UEGO algorithm was initially designed to solve problems whose solutions were codified as real vectors. However, in this work the HP protein folding solutions have been defined as means of conformations encoded by relative coordinates. Consequently several main concepts in UEGO have been re-defined, i.e. the representation of a solution, the distance concept, the computation of a middle point, etc. In addition, a new efficient local optimizer has been designed based on the characteristics of the protein model. This work develops the adaptation and implementation of UEGO to the HP model and analyzes the UEGO solutions of HP protein folding for different 3D problems. Finally, obtained HP solutions are converted into all-atom models so that comparison with real proteins can be carried out, and a good agreement is obtained for small size proteins.
Similar content being viewed by others
References
A. Arkhangel’skii, General Topology I: Basic Concepts and Constructions Dimension Theory (Encyclopaedia of Mathematical Sciences) (Springer, Berlin, 2011)
A. Arrondo, J. Fernández, J. Redondo, P. Ortigosa, An approach for solving competitive location problems with variable demand using multicore systems. Optim. Lett. 8, 555–567 (2013)
R. Backofen, S. Will, A constraint-based approach to fast and exact structure prediction in three-dimensional protein models. Constraints 11(1), 5–30 (2006)
B. Berger, T. Leighton, Protein folding in the hydrophobic–hydrophilic (hp) model is np-complete. J. Comput. Biol. 5(1), 27–40 (1998). doi:10.1089/cmb.1998.5.27
H.M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, H. Weissig, I.N. Shindyalov, P.E. Bourne, The protein data bank. Nucleic Acids Res. 28(1), 235–242 (2000)
T.N. Bui, G. Sundarraj, An efficient genetic algorithm for predicting protein tertiary structures in the 2D hp model, in Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, GECCO ’05 ACM, (New York, NY, USA, 2005), pp. 385–392
F. Custodio, H. Barbosa, L. Dardenne, Investigation of the threedimensional lattice HP protein folding model using a genetic algorithm. Genet. Mol. Biol. 27(4), 611–615 (2004)
W.L. DeLano, The PyMOL Molecular Graphics System (DeLano Scientific LLC, San Carlos, CA, 2002)
K.A. Dill, S. Bromberg, K. Yue, H.S. Chan, K.M. Ftebig, D.P. Yee, P.D. Thomas, Principles of protein folding a perspective from simple exact models. Protein Sci. 4(4), 561–602 (1995)
K.A. Dill, J.L. MacCallum, The protein-folding problem, 50 years on. Science 338(6110), 1042–1046 (2012)
S. Fidanova, I. Lirkov, Ant colony system approach for protein folding. in IMCSIT, pp. 887–891. IEEE (2008)
J. García-Martínez, E. Garzón, P. Ortigosa, A GPU implementation of a hybrid evolutionary algorithm: GPuEGO. J. Supercomput. 1–12 (2014). doi:10.1007/s11227-014-1136-7
T.A. Halgren, Merck molecular force field. i. basis, form, scope, parameterization, and performance of mmff94. J. Comput. Chem. 17(5–6), 490–519 (1996)
M. Jelásity, P. Ortigosa, I. García, UEGO, an abstract clustering technique for multimodal global optimization. J. Heuristics 7(3), 215–233 (2001)
F. Khatib, S. Cooper, D. Tyka, All: Algorithm discovery by protein folding game players. PNAS 108 (47) (2011). http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3223433/pdf/pnas.1115898108
I. Kondov, Protein structure prediction using distributed parallel particle swarm optimization. Nat. Comput. 12(1), 29–41 (2013)
C. Lin, S. Su, Protein 3D hp model folding simulation using a hybrid of genetic algorithm and particle swarm optimization. Int. J. Fuzzy Syst. 13(2), 140–147 (2011)
J. Liu, G. Li, J. Yu, Y. Yao, Heuristic energy landscape paving for protein folding problem in the three-dimensional HP lattice model. Comput. Biol. Chem. 38, 17–26 (2012)
P. Ortigosa, I. García, M. Jelásity, Reliability and performance of UEGO, a clustering-based global optimizer. J. Global Optim. 19(3), 265–289 (2001)
P. Ortigosa, J. Redondo, I. García, J. Fernández, A population global optimization algorithm to solve the image alignment problem in electron crystallography. J. Global Optim. 37(4), 527–539 (2007)
S. Ozkan, G.A. W., J. Chodera, K. Dill, Protein folding by zipping and assembly. PNAS 104 (29) (2007). http://www.pnas.org/content/104/29/11987.full+html?with-ds=yes
J. Peña, J. Cecilia, H. Pérez-Sánchez, Application of ant colony optimization in a hybrid coarse-grained and all-atom based protein structure prediction strategy. in 13th International Conference on Computational and Mathematical Methods in Science and Engineering, CMMSE 2013, pp. 1154–1156 (2013)
J. Redondo, J. Fernández, A. Arrondo, I. García, P. Ortigosa, Fixed or variable demand? Does it matter when locating a facility? Omega 40(1), 9–20 (2012)
J. Redondo, J. Fernández, A. Arrondo, I. García, P. Ortigosa, A two-level evolutionary algorithm for solving the facility location and design (\(1|1\))-centroid problem on the plane with variable demand. J. Global Optim. 56(3), 983–1005 (2013)
J. Redondo, J. Fernández, I. García, P. Ortigosa, Parallel algorithms for continuous competitive location problems. Optim. Methods Softw. 23(5), 779–791 (2008)
J. Redondo, J. Fernández, I. García, P. Ortigosa, A robust and efficient global optimization algorithm for planar competitive location problems. Ann. Oper. Res. 167, 87–106 (2009)
P. Rotkiewicz, J. Skolnick, Fast procedure for reconstruction of full-atom protein models from reduced representations. J. Comput. Chem. 29(9), 1460–1465 (2008)
A. Schug, W. Wenzel, An evolutionary strategy for all-atom folding of the 60-amino-acid bacterial ribosomal protein L20. Biophys. J. 90(12), 4273–4280 (2006)
A. Shmygelska, R. Aguirre-Hernndez, H.H. Hoos, An ant colony optimization algorithm for the 2D hp protein folding problem. in Proceedings of the 16th Canadian Conference Artificial Intelligence, (Springer, 2002), pp. 400–417
T. Strunk, M. Wolf, W. Wenzel, Peptide structure prediction using distributed volunteer computing networks. J. Math. Chem. 50(2), 421–428 (2012)
R., Unger, J. Moult, A genetic algorithm for 3D protein folding simulations. in Proceedings of the Fifth Annual International Conference on Genetic Algorithms, (Kaufmann, San Francisco, 1993) , p. 581–588
R. Unger, J. Moult, Genetic algorithms for protein folding simulations. J. Mol. Biol. 231(1), 75–81 (1993)
Acknowledgments
This work has been funded by grants from the Spanish Ministry of Science and Innovation (TIN2012-37483-C03-03), Junta de Andalucía (P10-TIC-6002 and P12-TIC301), Fundación Séneca (The Agency of Science and Technology of the Region of Murcia, 00003/CS/10, 15254/PI/10 and 18946/JLI/13) and by the Nils Coordinated Mobility under Grant 012-ABEL-CM-2014A, in part financed by the European Regional Development Fund (ERDF).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
García-Martínez, J.M., Garzón, E.M., Cecilia, J.M. et al. An efficient approach for solving the HP protein folding problem based on UEGO. J Math Chem 53, 794–806 (2015). https://doi.org/10.1007/s10910-014-0459-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10910-014-0459-1