Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

A Multi-objective Cluster-based Biased Random-Key Genetic Algorithm with Online Parameter Control Applied to Protein Structure Prediction

,

DOI: http://dx.doi.org/10.15439/2022F21

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 337–346 ()

Full text

Abstract. The protein structure prediction problem is one of the most important bioinformatics problems. Computational methods can be used to approach this problem and de novo methods are able to generate protein structures without the need of having known similar structures to the predicted protein. These methods transform the prediction problem into an optimization problem, using optimization models that combine different energy functions and high-level information. These models usually have only a single optimization objective. However, it is known that this single objective optimization approach may harm the optimization search due to the existence of conflicts between the different terms that compose the optimization objective. The proposed model has three objectives: energy function, secondary structure, and contact maps. A multi-objective Biased Random-Key Genetic Algorithm (BRKGA) with online parameter control, named MOBO, is proposed as the optimizer. The final predictor comprises two phases of the MOBO algorithm and selects a final structure using the MUFOLD-CL clustering method. Results obtained demonstrated that the proposed predictor generated highly competitive results with the literature.

References

  1. R. Garret and C. Grisham, “Biochemistry 4ed,” University of Virginia, Boston, MA, 2010.
  2. K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, “The protein folding problem,” Annu. Rev. Biophys., vol. 37, pp. 289–316, 2008.
  3. J. Gu and P. E. Bourne, Structural bioinformatics. Hoboken: John Wiley & Sons, 2009, vol. 44.
  4. J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko et al., “Highly accurate protein structure prediction with alphafold,” Nature, vol. 596, no. 7873, pp. 583–589, 2021.
  5. A. David, S. Islam, E. Tankhilevich, and M. J. Sternberg, “The alphafold database of protein structures: A biologist’s guide,” Journal of Molecular Biology, vol. 434, no. 2, p. 167336, 2022.
  6. M. Dorn, M. B. e Silva, L. S. Buriol, and L. C. Lamb, “Three-dimensional protein structure prediction: Methods and computational strategies,” Computational biology and chemistry, vol. 53, pp. 251–276, 2014.
  7. A. E. Márquez-Chamorro, G. Asencio-Cortés, C. E. Santiesteban-Toca, and J. S. Aguilar-Ruiz, “Soft computing methods for the prediction of protein tertiary structures: A survey,” Applied Soft Computing, vol. 35, pp. 398–410, 2015.
  8. R. S. Silva and R. S. Parpinelli, “A self-adaptive differential evolution with fragment insertion for the protein structure prediction problem,” in International Workshop on Hybrid Metaheuristics. Springer, 2019, pp. 136–149.
  9. N. N. Will and R. S. Parpinelli, “Comparing best and quota fragment picker protocols applied to protein structure prediction.” in HIS, 2020, pp. 669–678.
  10. V. Cutello, G. Narzisi, and G. Nicosia, “A multi-objective evolutionary approach to the protein structure prediction problem,” Journal of The Royal Society Interface, vol. 3, no. 6, pp. 139–151, 2006.
  11. D. Kalyanmoy and K. Deb, “Multi-objective optimization using evolutionary algorithms,” West Sussex, England: John Wiley, 2001.
  12. F. Marchi and R. S. Parpinelli, “A multi-objective approach to the protein structure prediction problem using the biased random-key genetic algorithm,” in 2021 IEEE Congress on Evolutionary Computation (CEC). New York: IEEE, 2021, pp. 1070–1077.
  13. J. F. Gonçalves and M. G. Resende, “Biased random-key genetic algorithms for combinatorial optimization,” Journal of Heuristics, vol. 17, no. 5, pp. 487–525, 2011.
  14. S. M. Venske, R. A. Gonçalves, E. M. Benelli, and M. R. Delgado, “Ademo/d: An adaptive differential evolution for protein structure prediction problem,” Expert Systems with Applications, vol. 56, pp. 209–226, 2016.
  15. S. Gao, S. Song, J. Cheng, Y. Todo, and M. Zhou, “Incorporation of solvent effect into multi-objective evolutionary algorithm for improved protein structure prediction,” IEEE/ACM transactions on computational biology and bioinformatics, vol. 15, no. 4, pp. 1365–1378, 2017.
  16. S. Song, S. Gao, X. Chen, D. Jia, X. Qian, and Y. Todo, “Aimoes: Archive information assisted multi-objective evolutionary strategy for ab initio protein structure prediction,” Knowledge-Based Systems, vol. 146, pp. 58–72, 2018.
  17. S. Song, J. Ji, X. Chen, S. Gao, Z. Tang, and Y. Todo, “Adoption of an improved pso to explore a compound multi-objective energy function in protein structure prediction,” Applied Soft Computing, vol. 72, pp. 539–551, 2018.
  18. P. H. Narloch, M. J. Krause, and M. Dorn, “Multi-objective differential evolution algorithms for the protein structure prediction problem,” in 2020 IEEE Congress on Evolutionary Computation (CEC). New York: IEEE, 2020, pp. 1–8.
  19. G. K. Rocha, K. B. Dos Santos, J. S. Angelo, F. L. Custodio, H. J. Barbosa, and L. E. Dardenne, “Inserting co-evolution information from contact maps into a multiobjective genetic algorithm for protein structure prediction,” in 2018 IEEE Congress on Evolutionary Computation (CEC). New York: IEEE, 2018, pp. 1–8.
  20. A. B. Zaman, P. V. Parthasarathy, and A. Shehu, “Using sequence-predicted contacts to guide template-free protein structure prediction,” in Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics, ser. BCB ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 154–160. [Online]. Available: https://doi.org/10.1145/3307339. 3342175
  21. X. Chen, S. Song, J. Ji, Z. Tang, and Y. Todo, “Incorporating a multiobjective knowledge-based energy function into differential evolution for protein structure prediction,” Information Sciences, vol. 540, pp. 69–88, 2020.
  22. L. de Lima Corrêa and M. Dorn, “A multi-objective swarm-based algorithm for the prediction of protein structures,” in International Conference on Computational Science. Cham: Springer, 2019, pp. 101–115.
  23. J. C. C. Tudela and J. O. Lopera, “Parallel protein structure prediction by multiobjective optimization,” in 2009 17th Euromicro International Conference on Parallel, Distributed and Network-based Processing. New York: IEEE, 2009, pp. 268–275.
  24. C. A. Rohl, C. E. Strauss, K. M. Misura, and D. Baker, “Protein structure prediction using rosetta,” Methods in enzymology, vol. 383, pp. 66–93, 2004.
  25. D. T. Jones, “Protein secondary structure prediction based on position-specific scoring matrices,” Journal of molecular biology, vol. 292, no. 2, pp. 195–202, 1999.
  26. W. Kabsch and C. Sander, “Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features,” Biopolymers: Original Research on Biomolecules, vol. 22, no. 12, pp. 2577–2637, 1983.
  27. J. Ma, S. Wang, Z. Wang, and J. Xu, “Protein contact prediction by integrating joint evolutionary coupling analysis and supervised learning,” Bioinformatics, vol. 31, no. 21, pp. 3506–3513, 2015.
  28. K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” IEEE transactions on evolutionary computation, vol. 6, no. 2, pp. 182–197, 2002.
  29. R. Parpinelli, G. Plichoski, R. Silva, and P. Narloch, “A review of techniques for online control of parameters in swarm intelligence and evolutionary computation algorithms,” International Journal of Bio-Inspired Computation, vol. 13, pp. 1–20, 2019.
  30. J. Zhang and D. Xu, “Fast algorithm for population-based protein structural model analysis,” Proteomics, vol. 13, no. 2, pp. 221–229, 2013.
  31. V. N. Maiorov and G. M. Crippen, “Significance of root-mean-square deviation in comparing three-dimensional structures of globular proteins,” Journal of molecular biology, vol. 235, no. 2, pp. 625–634, 1994.
  32. H. El-Rewini and M. Abd-El-Barr, Advanced computer architecture and parallel processing. Hoboken, New Jersey: John Wiley & Sons, 2005, vol. 42.