Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Natural Computing

11-08-2022

A self-adaptive evolutionary algorithm using Monte Carlo Fragment insertion and conformation clustering for the protein structure prediction problem

Authors: Rafael Stubs Parpinelli, Nilcimar Neitzel Will, Renan Samuel da Silva

Published in: Natural Computing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The Protein Structure Prediction Problem is one of the most important and challenging open problems in Computer Science and Structural Bioinformatics. Accurately predicting protein conformations would significantly impact several fields, such as understanding proteinopathies and developing smart protein-based drugs. As such, this work has as its primary goal to improve the prediction power of ab initio methods by utilizing a self-adaptive evolutionary algorithm using Monte Carlo based fragment insertion and conformational clustering. A meta-heuristic is used as the core of the conformation sampling process with fragment insertion, feeding domain-specific information into the process. The online parameter control routines allow the method to adapt to a protein’s structure specificity and behave dynamically in different stages of the optimization process. The results obtained by the proposed method were compared to results obtained from several other algorithms found in the literature. It is possible to conclude that the proposed method is highly competitive in terms of free-energy and RMSD for the protein set used in the experiments.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
 
3
Only physical cores were considered. No virtual (Hyper-threading) core was involved in the computations.
 
6
For the readers with a black and white copy, the predicted conformation is in a light shade of grey, while the native conformation is in dark grey.
 
Literature
Alford RF, Leaver-Fay A, Jeliazkov JR, O’Meara MJ, DiMaio FP, Park H, Shapovalov MV, Renfrew PD, Mulligan VK, Kappel K et al (2017) The Rosetta all-atom energy function for macromolecular modeling and design. J Chem Theory Comput 13(6):3031–3048CrossRef
Álvarez Ó, Fernández-Martínez JL, Cernea A, Fernández-Muñiz Z, Kloczkowski A (2018) Protein tertiary structure prediction via svd and pso sampling. In: International conference on bioinformatics and biomedical engineering. Springer, pp 211–220
Anfinsen CB (1973) Principles that govern the folding of protein chains. Science 181(4096):223–230CrossRef
Berger B, Leighton T (1998) Protein folding in the hydrophobic-hydrophilic (hp) model is np-complete. J Comput Biol 5(1):27–40CrossRef
Blum C, Puchinger J, Raidl GR, Roli A (2011) Hybrid metaheuristics in combinatorial optimization: a survey. Appl Soft Comput 11(6):4135–4151MATHCrossRef
Boiani M, Parpinelli RS (2020) A GPU-based hybrid jDE algorithm applied to the 3D-AB protein structure prediction. Swarm Evol Comput 58:100711CrossRef
Borguesan B, e Silva MB, Grisci B, Inostroza-Ponta M, Dorn M (2015) Apl: an angle probability list to improve knowledge-based metaheuristics for the three-dimensional protein structure prediction. Comput Biol Chem 59:142–157CrossRef
Borguesan B, Narloch PH, Inostroza-Ponta M, Dorn M (2018) A genetic algorithm based on restricted tournament selection for the 3d-psp problem. In: 2018 IEEE congress on evolutionary computation (CEC). IEEE, IEEE, Rio de Janeiro, Brazil, pp 1–8. https://​doi.​org/​10.​1109/​CEC.​2018.​8477721
Brooks BR, Brooks CL III, Mackerell AD Jr, Nilsson L, Petrella RJ, Roux B, Won Y, Archontis G, Bartels C, Boresch S et al (2009) Charmm: the biomolecular simulation program. J Comput Chem 30(10):1545–1614CrossRef
Correa L, Borguesan B, Farfan C, Inostroza-Ponta M, Dorn M (2016) A memetic algorithm for 3-D protein structure prediction problem. IEEE/ACM Trans Comput Biol Bioinf 15:690CrossRef
Correa LDL, Dorn M (2018) A knowledge-based artificial bee colony algorithm for the 3-d protein structure prediction problem. In: 2018 IEEE congress on evolutionary computation (CEC). IEEE, Rio de Janeiro, Brazil, pp 1–8
David A, Islam S, Tankhilevich E, Sternberg MJ (2022) The AlphaFold database of protein structures: a biologist’s guide. J Mol Biol 434(2):167336CrossRef
de Oliveira SH, Law EC, Shi J, Deane CM (2017) Sequential search leads to faster, more efficient fragment-based de novo protein structure prediction. Bioinformatics 34(7):1132–1140CrossRef
Dorn M, e Silva MB, Buriol LS, Lamb LC (2014) Three-dimensional protein structure prediction: methods and computational strategies. Comput Biol Chem 53:251–276CrossRef
Eichenberger AP, Allison JR, Dolenc J, Geerke DP, Horta BA, Meier K, Oostenbrink C, Schmid N, Steiner D, Wang D et al (2011) Gromos++ software for the analysis of biomolecular simulation trajectories. J Chem Theory Comput 7(10):3379–3390CrossRef
Frishman D, Argos P (1995) Knowledge-based protein secondary structure assignment. Proteins Struct Funct Bioinf 23(4):566–579CrossRef
Gao S, Song S, Cheng J, Todo Y, Zhou M (2018) Incorporation of solvent effect into multi-objective evolutionary algorithm for improved protein structure prediction. IEEE/ACM Trans Comput Biol Bioinf 15(4):1365–1378CrossRef
Garza-Fabre M, Kandathil SM, Handl J, Knowles J, Lovell SC (2016) Generating, maintaining, and exploiting diversity in a memetic algorithm for protein structure prediction. Evol Comput 24(4):577–607CrossRef
Geng L, Shen H (2017) A protein structure refinement method using bi-objective particle swarm optimization algorithm. Image and Signal Processing. In: BioMedical Engineering and Informatics (CISP-BMEI), 2017 10th international congress on. IEEE, Shanghai, China, pp 1–5
Gront D, Kulp DW, Vernon RM, Strauss CE, Baker D (2011) Generalized fragment picking in Rosetta: design, protocols and applications. PloS One 6(8):e23294CrossRef
Gunn JR (1997) Sampling protein conformations using segment libraries and a genetic algorithm. J Chem Phys 106(10):4270–4281CrossRef
Hao X, Zhang G (2017) Double estimation of distribution guided sampling algorithm for de-novo protein structure prediction. In: Control Conference (CCC). 2017 36th Chinese. IEEE, Dalian, China, pp 9853–9858
Hao XH, Zhang GJ, Zhou XG (2017) Conformational space sampling method using multi-subpopulation differential evolution for de novo protein structure prediction. IEEE Trans Nanobiosci 16(7):618–633CrossRef
Hart WE, Istrail S (1997) Robust proofs of np-hardness for protein folding: general lattices and energy potentials. J Comput Biol 4(1):1–22CrossRef
Higgs T, Stantic B, Hoque MT, Sattar A (2010) Genetic algorithm feature-based resampling for protein structure prediction. In: Evolutionary computation (CEC). 2010 IEEE congress on. IEEE, Barcelona, Spain, pp 1–8
Jumper J, Evans R, Pritzel A, Green T, Figurnov M, Ronneberger O, Tunyasuvunakool K, Bates R, Žídek A, Potapenko A et al (2021) Highly accurate protein structure prediction with AlphaFold. Nature 596(7873):583–589CrossRef
Kandathil SM, Garza-Fabre M, Handl J, Lovell SC (2018) Improved fragment-based protein structure prediction by redesign of search heuristics. Sci Rep 8(1):13694CrossRef
Karafotias G, Hoogendoorn M, Eiben ÁE (2015) Parameter control in evolutionary algorithms: trends and challenges. IEEE Trans Evol Comput 19(2):167–187CrossRef
Kaufmann KW, Lemmon GH, DeLuca SL, Sheehan JH, Meiler J (2010) Practically useful: what the Rosetta protein modeling suite can do for you. Biochemistry 49(14):2987–2998CrossRef
Kim DE, Blum B, Bradley P, Baker D (2009) Sampling bottlenecks in de novo protein structure prediction. J Mol Biol 393(1):249–260CrossRef
Lee J, Freddolino PL, Zhang Y (2017) Ab initio protein structure prediction. In: From protein structure to function with bioinformatics. Springer, Berlin, Germany, pp 3–35
Li B, Chiong R, Lin M (2015) A balance-evolution artificial bee colony algorithm for protein structure optimization based on a three-dimensional AB off-lattice model. Comput Biol Chem 54:1–12MathSciNetCrossRef
Li Z, Scheraga HA (1987) Monte Carlo-minimization approach to the multiple-minima problem in protein folding. Proc Natl Acad Sci 84(19):6611–6615MathSciNetCrossRef
Lopes HS (2008) Evolutionary algorithms for the protein folding problem: a review and current trends. In: Computational intelligence in biomedicine and bioinformatics. Springer, pp 297–315
McGuffin LJ, Bryson K, Jones DT (2000) The PSIPRED protein structure prediction server. Bioinformatics 16(4):404–405CrossRef
Narloch PH, Dorn M (2019) A knowledge based self-adaptive differential evolution algorithm for protein structure prediction. In: International conference on computational science. Springer, pp 87–100
Narloch PH, Parpinelli RS (2016) Diversification strategies in differential evolution algorithm to solve the protein structure prediction problem. In: International conference on intelligent systems design and applications. Springer, Porto, Portugal, pp 125–134
Narloch PH, Parpinelli RS (2017) The protein structure prediction problem approached by a cascade differential evolution algorithm using rosetta. In: 2017 Brazilian conference on intelligent systems (BRACIS). IEEE, Uberlandia, Brazil, pp 294–299
Nunes LF, Galvão LC, Lopes HS, Moscato P, Berretta R (2016) An integer programming model for protein structure prediction using the 3D-HP side chain model. Discret Appl Math 198:206–214MathSciNetMATHCrossRef
Oliveira M, Borguesan B, Dorn M (2017) Sade-spl: a self-adapting differential evolution algorithm with a loop structure pattern library for the psp problem. In: Evolutionary computation (CEC). 2017 IEEE Congress on. IEEE, Donostia - San Sebastián, Spain, pp 1095–1102
Olson B, Shehu A (2012) Efficient basin hopping in the protein energy surface. Bioinformatics and Biomedicine (BIBM). In: 2012 IEEE International conference on. IEEE, USA, pp 1–6
Parpinelli RS, Plichoski GF, Da Silva RS, Narloch PH (2019) A review of technique for on-line control of parameters in swarm intelligence and evolutionary computation algorithms. Int J Bio-Inspir Comput 13:1–20CrossRef
Prentiss MC, Wales DJ, Wolynes PG (2008) Protein structure prediction using basin-hopping. J Chem Phys 128(22):06B608CrossRef
Qin AK, Huang VL, Suganthan PN (2009) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13(2):398–417CrossRef
Qin AK, Suganthan PN (2005) Self-adaptive differential evolution algorithm for numerical optimization. In: Evolutionary Computation, 2005, vol 2. The 2005 IEEE Congress on. IEEE, Edinburgh, Scotland, pp 1785–1791
Ramyachitra D, Ajeeth A (2017) Modcsa-ca: a multi objective diversity controlled self adaptive cuckoo algorithm for protein structure prediction. Gene Rep 8:100–106CrossRef
Rohl CA, Strauss CE, Misura KM, Baker D (2004) Protein structure prediction using rosetta. In: Methods in enzymology, vol. 383. Elsevier, New York, USA, pp 66–93
Salomon-Ferrer R, Case DA, Walker RC (2013) An overview of the amber biomolecular simulation package. Wiley Interdiscip Rev Comput Mol Sci 3(2):198–210CrossRef
Silva RS, Parpinelli RS (2018) A multistage simulated annealing for protein structure prediction using Rosetta. Anais do Computer on the Beach pp 850–859
Silva RS, Parpinelli RS (2019) A self-adaptive differential evolution with fragment insertion for the protein structure prediction problem. In: International workshop on hybrid metaheuristics. Springer, pp 136–149
Simoncini D, Schiex T, Zhang KY (2017) Balancing exploration and exploitation in population-based sampling improves fragment-based de novo protein structure prediction. Proteins Struct Funct Bioinf 85(5):852–858CrossRef
Sinha A, Malo P, Deb K (2018) A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Trans Evol Comput 22(2):276–295CrossRef
Song S, Ji J, Chen X, Gao S, Tang Z, Todo Y (2018) Adoption of an improved PSO to explore a compound multi-objective energy function in protein structure prediction. Appl Soft Comput 72:539–551CrossRef
Sudha S, Baskar S, Amali SMJ, Krishnaswamy S (2015) Protein structure prediction using diversity controlled self-adaptive differential evolution with local search. Soft Comput 19(6):1635–1646CrossRef
Varela D, Santos J (2019) Crowding differential evolution for protein structure prediction. In: International work-conference on the interplay between natural and artificial computation. Springer, pp. 193–203
Vlachakis D, Bencurova E, Papangelopoulos N, Kossida S (2014) Current state-of-the-art molecular dynamics methods and applications. In: Advances in protein chemistry and structural biology, vol. 94. Elsevier, New York, USA, pp 269–313
Walsh G (2002) Proteins: biochemistry and biotechnology. John Wiley & Sons
Wilk MB, Shapiro S (1968) The joint assessment of normality of several independent samples. Technometrics 10(4):825–839CrossRef
Zaman AB, Shehu A (2019) Balancing multiple objectives in conformation sampling to control decoy diversity in template-free protein structure prediction. BMC Bioinf 20(1):211CrossRef
Zemla A (2003) LGA: a method for finding 3D similarities in protein structures. Nucleic Acids Res 31(13):3370–3374CrossRef
Metadata
Title
A self-adaptive evolutionary algorithm using Monte Carlo Fragment insertion and conformation clustering for the protein structure prediction problem
Authors
Rafael Stubs Parpinelli
Nilcimar Neitzel Will
Renan Samuel da Silva
Publication date
11-08-2022
Publisher
Springer Netherlands
Published in
Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-022-09916-z

Premium Partner

    Image Credits