Ab Initio Protein Structure Prediction Using Evolutionary Approach: A Survey

Lucas Siqueira, Sandra Venske

Abstract


Protein Structure Prediction (PSP) problem is to determine the three-dimensional structure of a protein only from its primary structure. Misfolding of a protein causes human diseases. Thus, the knowledge of the structure and functionality of proteins, combined with the prediction of their structure is a complex problem and a challenge for the area of computational biology. The metaheuristic optimization algorithms are naturally applicable to support in solving NP-hard problems.These algorithms are bio-inspired, since they were designed based on procedures found in nature, such as the successful evolutionary behavior of natural systems. In this paper, we present a survey on methods to approach the \textit{ab initio} protein structure prediction based on evolutionary computing algorithms, considering both single and multi-objective optimization. An overview of the works is presented, with some details about which characteristics of the problem are considered, as well as specific points of the algorithms used. A comparison between the approaches is presented and some directions of the research field are pointed out.


Keywords


Protein Structure Prediction; Evolutionary Algorithms; Ab Initio; Bioinformatics

Full Text:

PDF

References


RANGWALA, H.; KARYPIS, G. Introduction to protein structure prediction. In: . Introduction to Protein Structure Prediction. Nova Jersey: John Wiley & Sons, Ltd, 2010. cap. 1, p. 1–13.

NELSON, D. L.; COX, M. M. Lehninger Principles of Biochemistry. 4. ed. New York: W. H. Freeman, 2004.

TRAMONTANO, A. Protein Structure Prediction: Concepts and applications. Nova Jersey: John Wiley and Sons, 2006.

JANA, N. D.; DAS, S.; SIL, J. A Metaheuristic Approach to Protein Structure Prediction. [S.l.]: Springer, 2018. v. 31. (Emergence, Complexity and Computation, v. 31).

TRAMONTANO, A. The Ten Most Wanted Solutions in Protein Bioinformatics. Boca Raton: CRC Press, 2005. (Chapman & Hall/CRC Mathematical and Computational Biology).

NUNES, L. F. et al. An integer programming model for protein structure prediction using the 3d-hp side chain model. Discrete Applied Mathematics, Elsevier, Amsterda, v. 198, p. 206 – 214, 2016.

SILVA, R. S. P. R. S. A multistage simulated annealing for protein structure prediction using rosetta. In: Computer on the Beach. [S.l.]: Universidade do Vale do Itaja ́ı - UNIVALI, 2018. p. 850–859.

GENDREAU, M.; POTVIN, J.-Y. Handbook of Metaheuristics. 2. ed. Nova Iorque: Springer, 2010.

HOLLAND, J. H. Adaptation in Natural and Artificial Systems. 2. ed. Ann Arbor: University of Michigan Press, 1975.

KIRKPATRICK, S.; GELATT, C. D.; VECCHI, M. P. Optimization by simulated annealing. Science, American Association for the Advancement of Science, Washington, v. 220, n. 4598, p. 671–680, 1983.

KENNEDY, J.; EBERHART, R. C. Particle swarm optimization. In: INTERNATIONAL CONFERENCE ON NEURAL NETWORKS, 1995, Perth. Proceedings of the [...]. Piscataway: IEEE, 1995. p. 1942–1948.

DORIGO, M.; ST ̈UTZLE, T. Ant Colony Optimization. Holland: Bradford Company, 2004.

KARABOGA, D.; BASTURK, B. Artificial bee colony (ABC) optimization algorithm for solving constrained optimization problems. In: MELIN, P. et al. (Ed.). Foundations of Fuzzy Logic and Soft Computing. Berlin, Heidelberg: Springer-Verlag, 2007. p. 789–798.

GEEM, Z.; KIM, J.; LOGANATHAN, G. A new heuristic optimization algorithm: Harmony search. Simulation, SAGE Publications Ltd, Thousand Oaks, v. 76, n. 2, p. 60–68, jun. de 2001.

YANG, X.-S.; DEB, S. Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimisation, Inderscience Publishers, Gen`eve, v. 1, n. 4, p. 330–343, 2010.

STORN, R.; PRICE, K. Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, Kluwer Academic Publishers, Hingham, MA, USA, v. 11, n. 4, p. 341–359, 1997.

HUNT, J. E.; COOKE, D. E. Learning using an artificial immune system. Journal of Network and Computer Applications, Elsevier, v. 19, n. 2, p. 189 – 212, 1996.

GUJRATHI, A.; BABU, B. Evolutionary computation: Techniques and applications. Nova Jersey: Apple Academic Press, 2016.

XU, Y.; XU, D.; LIANG, J. Computational Methods for Protein Structure Prediction and Modeling: Volume 1: Basic characterization. Nova Iorque: Springer, 2006.

HARRISON, J. et al. Review of force fields and intermolecular potentials used in atomistic computational materials research. Applied Physics Reviews, College Park, v. 5, p. 031104, set. de 2018.

XU, P. et al. Advancement of polarizable force field and its use for molecular modeling and design. In: . Advance in Structural Bioinformatics. Dordrecht: Springer Netherlands, 2015. p. 19–32.

SNEHA, P.; George Priya Doss, C. Chapter seven - molecular dynamics: New frontier in personalized medicine. In: DONEV, R. (Ed.). Personalized Medicine. Cambridge: Academic Press, 2016, (Advances in Protein Chemistry and Structural Biology, v. 102). p. 181–224.

BROOKS, B. R. et al. CHARMM: A program for macromolecular energy, minimization, and dynamics calculations. Journal of Computational Chemistry, Cambridge, v. 4, n. 2, p. 187–217, 1983.

MACKEREL, A. D. et al. CHARMM: The energy function and its parameterization with an overview of the program. In: . Chichester: John Wiley & Sons, 1998. v. 1, p. 271–277.

JORGENSEN, W. L.; TIRADO-RIVES, J. The OPLS [optimized potentials for liquid simulations] potential functions for proteins, energy minimizations for crystals of cyclic peptides and crambin. Journal of the American Chemical Society,Washington, v. 110 6, p. 1657–66, 1988.

JORGENSEN, W. L.; MAXWELL, D. S.; TIRADO-RIVES, J. Development and Testing of the OPLS All-Atom Force Field on Conformational Energetics and Properties of Organic Liquids. Journal of the American Chemical Society,Washington, v. 118, p. 11225–11236, 1996.

CORNELL, W. D. et al. A second generation force field for the simulation of proteins, nucleic acids, and organic molecules. Journal of The American Chemical Society, v. 117, p. 5179–5197, 1995.

GUNSTEREN, W. F. van; BERENDSEN. Groningen Molecular Simulation (GROMOS) Library Manual. Groningen: Biomos, 1987.

CUTELLO, V.; NARZISI, G.; NICOSIA, G. A multi-objective evolutionary approach to the protein structure prediction problem. Journal of the Royal Society Interface, v. 3, n. 6, p. 139–151, 2006.

GAO, S. et al. Incorporation of solvent effect into multi-objective evolutionary algorithm for improved protein structure prediction. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Piscataway, v. 15, n. 4, p. 1365–1378, jul. de 2018.

SHAIK, N. et al. Essentials of Bioinformatics: Volume i: Understanding bioinformatics: Genes to proteins. Nova Iorque: Springer International Publishing, 2019.

PEVSNER, J. Bioinformatics Genomics and Functional. 3. ed. Hoboken: Wiley Blackwell, 2015.

BERG, J.; TYMOCZKO, J.; STRYER, L. Biochemistry. New York: W. H. Freeman, 2007. (Biochemistry (Berg)).

LI, D.; HWANG, K.; HUANG, Y. Coarse grained modeling of biopolymers and proteins: Methods and applications. International Journal of Applied Mechanics, New Jersey, v. 1, n. 1, p. 113–136, mar. de 2009.

KMIECIK, S. et al. Coarse-grained protein models and their applications. Chemical Reviews, Washington, v. 116, n. 14, p. 7898–7936, 2016.

MOSS, D.; JELASKA, S.; PONGOR, S. Essays in Bioinformatics. Amsterd ̃a: IOS Press, 2005. v. 368. (NATO Science Series: Life and Behavioural Sciences, v. 368).

ZEMLA, A. Lga: A method for finding 3d similarities in protein structures. Nucleic Acids Research, Oxford, v. 31, n. 13, p. 3370–3374, jul. de 2003.

DEZA, M.; DEZA, E. Encyclopedia of Distances. Berlin: Springer-Verlag, 2014.

ZHANG, Y.; SKOLNICK, J. Scoring function for automated assessment of protein structure template quality. Proteins: Structure, Function, and Bioinformatics, Hoboken, v. 57, n. 4, p. 702–710, 2004.

HAN, X.; LI, L.; LU, Y. Selecting near-native protein structures from predicted decoy sets using ordered graphlet degree similarity. Genes, Basel, v. 10, n. 2, 2019.

ENGELBRECHT, A. P. Computational Intelligence: An introduction. 2. ed. Hoboken: Wiley Publishing, 2007.

LIU, Y.-L.; TAO, L. An improved parallel simulated annealing algorithm used for protein structure prediction. In: INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, 2006, Dalian. Proceedings of the [...]. Piscataway: IEEE, 2006. p. 2335–2338.

NICOSIA, G.; STRACQUADANIO, G. Generalized pattern search and mesh adaptive direct search algorithms for protein structure prediction. In: INTERNATIONAL CONFERENCE ON ALGORITHMS IN BIOINFORMATICS, 7., Philadelphia, PA. Proceedings of the [...]. Berlin, Heidelberg: Springer-Verlag, 2007. (WABI’07), p. 183–193.

YOUSEF, M.; ABDELKADER, T.; ELBAHNASY, K. A hybrid model to predict proteins tertiary structure. In: INTERNATIONAL CONFERENCE ON COMPUTER ENGINEERING AND SYSTEMS (ICCES), 12., Cairo. Proceedings of the [...]. Piscataway: IEEE, 2017. p. 85–91.

CUST ́ODIO, F. L.; BARBOSA, H. J. C.; DARDENNE, L. E. Full-atom ab initio protein structure prediction with a genetic algorithm using a similarity-based surrogate model. In: IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, 2010, Barcelona. Proceedings of the [...]. Piscataway: IEEE, 2010. p. 1–8.

VENKATESAN, A. et al. Computational approach for protein structure prediction. Healthcare Informatics Research, Seoul, v. 19, n. 2, p. 137–147, 2013.

BECERRA, D. et al. A parallel multi-objective ab initio approach for protein structure prediction. In: IEEE INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICINE (BIBM), 2010, Hong Kong. Proceedings of the [...]. Piscataway: IEEE, 2011. p. 137–141.

DAVIS, L. (Ed.). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991.

GONG, M.; JIAO, L.; ZHANG, L. Baldwinian learning in clonal selection algorithm for optimization. Information Sciences, Elsevier, Amsterd ̃a, v. 180, n. 8, p. 1218–1236, 2010.

ANILE, A. M. et al. Determination of protein structure and dynamics combining immune algorithms and pattern search methods. Natural Computing, Basingstoke, v. 6, n. 1, p. 55–72, 2007.

CUTELLO, V.; NARZISI, G.; NICOSIA, G. A class of pareto archived evolution strategy algorithms using immune inspired operators for ab-initio protein structure prediction. In: WORKSHOPS ON APPLICATIONS OF EVOLUTIONARY COMPUTATION (EVOWORKSHOPS), 3., 2005, Lausanne, Switzerland. Proceedings of the [...]. Berlin, Heidelberg: Springer-Verlag, 2005. (Lecture Notes in Computer Science (LNCS), v. 3449), p. 54–63.

CUTELLO, V.; NARZISI, G.; NICOSIA, G. Computational studies of peptide and protein structure prediction problems via multiobjective evolutionary algorithms. In: KNOWLES, J. et al. (Ed.). Multiobjective Problem Solving from Nature. [S.l.]: Springer-Verlag, 2008, (Natural Computing Series). p. 93–114.

ANGELINE, P. J. et al. (Ed.), 1999, Washington. The Pareto Archived Evolution Strategy: A new baseline algorithm for pareto multiobjective optimisation, v. 1. Congress on Evolutionary Computation, Piscataway: IEEE Press, 2002. 98–105 p.

SUDHA, S.; BASKAR, S.; KRISHNASWAMY, S. Protein tertiary structure prediction using evolutionary algorithms. International Journal of Emerging Technologies in Computational and Applied Sciences (IJETCAS), IASIR, Georgia, USA, v. 3, n. 3, p. 338–348–595, 2013.

SUDHA, S. et al. Protein structure prediction using diversity controlled self-adaptive differential evolution with local search. Soft Computing, Nova Iorque, v. 19, n. 6, p. 1635–1646, jun. de 2015.

NARLOCH, P. H.; PARPINELLI, R. S. Diversification strategies in differential evolution algorithm to solve the protein structure prediction problem. In: MADUREIRA, A. M. et al. (Ed.). Intelligent Systems Design and Applications. Cham: Springer International Publishing, 2017. p. 125–134.

HAO, X.; ZHANG, G.; ZHOU, X. Guiding exploration in conformational feature space with lipschitz underestimation for ab-initio protein structure prediction. Computational Biology and Chemistry, v. 73, p. 105 – 119, abr. de 2018.

RAKHSHANI, H. et al. Speed up differential evolution for computationally expensive protein structure prediction problems. Swarm and Evolutionary Computation, v. 50, p. 100493, 2019.

VENSKE, S. M.; GONC ̧ ALVES, R. A.; DELGADO, M. R. Differential evolution to multi-objective protein structure prediction. In: BIOINFORMATICS 2012 - INTERNATIONAL CONFERENCE ON BIOINFORMATICS MODELS, METHODS AND ALGORITHMS, 2012, Vilamoura. Proceedings of the [...]. Set ́ubal: SciTePress - Science and Technology Publications, 2012. p. 295–298.

VENSKE, S. M. et al. ADEMO/D: An adaptive differential evolution for protein structure prediction problem. Expert Systems with Applications, Amsterd ̃a, v. 56, p. 209 – 226, 2016.

YANG, X.; DEB, S. Cuckoo search via l ́evy flights. In: WORLD CONGRESS ON NATURE BIOLOGICALLY INSPIRED COMPUTING (NABIC), 2009, Coimbatore. Proceedings of the [...]. Piscataway: IEEE, 2010. p. 210–214.

BEYER, H.-G.; SCHWEFEL, H.-P. Evolution strategies: A comprehensive introduction. Natural Computing, Nova Iorque, v. 1, p. 3–52, mar. de 2002.

FACCIOLI, R. et al. A mono-objective evolutionary algorithm for protein structure prediction in structural and energetic contexts. In: IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, 2012, Brisbane. Proceedings of the [...]. Piscataway: IEEE, 2012. p. 1–7.

OLSON, B.; JONG, K. D.; SHEHU, A. Off-lattice protein structure prediction with homologous crossover. In: ANNUAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION, 15., 2013, Amsterdam, The Netherlands. Proceedings of the [...]. New York, NY, USA: ACM, 2013. (GECCO ’13), p. 287–294.

CALVO, J.; ORTEGA, J.; ANGUITA, M. PITAGORAS-PSP: Including domain knowledge in a multi-objective approach for protein structure prediction. Neurocomputing, Amsterda, v. 74, n. 16, p. 2675 – 2682, 2011.

BRASIL, C. R. S.; DELBEM, A. C. B.; SILVA, F. L. B. da. Multiobjective evolutionary algorithm with many tables for purely ab initio protein structure prediction. Journal of Computational Chemistry, v. 34, n. 20, p. 1719–1734, 2013.

RAMYACHITRA, D.; AJEETH, A. Modcsa-ca: A multi objective diversity controlled self adaptive cuckoo algorithm for protein structure prediction. Gene Reports, Amsterda, v. 8, p. 100 – 106, 2017.

SONG, Z. et al. A preference-based multi-objective evolutionary strategy for ab initio prediction of proteins. In: INTERNATIONAL CONFERENCE ON PROGRESS IN INFORMATICS AND COMPUTING (PIC), 2017, Nanjing. Proceedings of the [...]. Piscataway: IEEE, 2017. p. 7–12.

SONG, S. et al. AIMOES: Archive information assisted multi-objective evolutionary strategy for ab initio protein structure prediction. Knowledge-Based Systems, v. 146, p. 58 – 72, 2018.

SONG, S. et al. Adoption of an improved PSO to explore a compound multi-objective energy function in protein structure prediction. Applied Soft Computing, v. 72, p. 539 – 551, nov. 2018.

ISHIBUCHI, H.; TSUKAMOTO, N.; NOJIMA, Y. Evolutionary many-objective optimization: A short review. In: IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (IEEE WORLD CONGRESS ON COMPUTATIONAL INTELLIGENCE), 2008, Hong Kong. Proceedings of the [...]. Piscataway: IEEE, 2008. p. 2419–2426.

SHATABDA, S. et al. How good are simplified models for protein structure prediction? Advances in Bioinformatics, Londres, v. 2014, apr 2014.




DOI: https://doi.org/10.22456/2175-2745.111993

Copyright (c) 2021 Lucas Siqueira, Sandra Venske

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Indexing databases:
        

Acknowledgments: