PSPGA: A New Method for Protein Structure Prediction based on Genetic Algorithm

Subject Areas : Electrical Engineering

Arash Mazidi ¹ , Fahimeh Roshanfar ²

1 - Department of Computer Engineering, Faculty of Engineering, Golestan University, Gorgan, Iran.
2 - Department of Nanotechnology and Advanced Materials, Materials and Energy Research Center, Karaj, Iran

Received: 2020-01-25 Accepted : 2020-05-10 Published : 2020-06-01

Keywords: Genetic Algorithm, Evolutionary Algorithm, Protein Structure Prediction, HP Model,

Abstract :

Bioinformatics is a new science that uses algorithms, computer software and databases in order to solve biological problems, especially in the cellular and molecular areas. Bioinformatics is defined as the application of tools of computation and analysis to the capture and interpretation of biological data. Protein Structure Prediction (PSP) is one of the most complex and important issues in bioinformatics, and extensive researches has been done to solve this problem using evolutionary algorithms. In this paper, we propose a genetic based method in order to solve protein structure prediction problem with increasing the accuracy of prediction, using a crossover operator based on pattern mask. Further, we compare two genetic based method to evaluate the proposed method. The results of the implementation of our proposed algorithm on five standard test sequences show that the use of a pattern mask-based crossover operator in the genetic algorithm can significantly improve the accuracy compared to previous similar algorithms.

References:

[1]     A. Mazidi, F. Roshanfar, and V. Parvin Darabad, “A Review of Outliers: Towards a Novel Fuzzy Method for Outlier Detection ‎,” J. Appl. Dyn. Syst. Control, vol. 2, no. 1, pp. 7–17, Jun. 2019.

[2]     B. Patel, V. Singh, and D. Patel, “Structural Bioinformatics,” in Essentials of Bioinformatics, Volume I, Cham: Springer International Publishing, 2019, pp. 169–199.

[3]     A. Mazidi, M. Fakhrahmad, and M. Sadreddini, “A meta-heuristic approach to CVRP problem : local search optimization based on GA and ant colony,” J. Adv. Comput. Res., vol. 7, no. December, pp. 1–22, 2016.

[4]     A. Mazidi and E. Damghanijazi, “Meta-Heuristic Approaches for Solving Travelling Salesman Problem A meta-heuristic approach to CVRP problem View project Meta-Heuristic Approaches for Solving Travelling Salesman Problem View project Meta-Heuristic Approaches for Solving Travelling Salesman Problem,” Int. J. Adv. Res. Comput. Sci., vol. 8, no. 5.

[5]     B. Berger and T. Leighton, “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete, Mathematics Department and Laboratory for Computer Science,” 1998.

[6]     R. Unger and J. Moult, “Genetic algorithms for protein folding simulations,” J. Mol. Biol., vol. 231, no. 1, pp. 75–81, May 1993.

[7]     K. F. Lau and K. A. Dill, “A Lattice Statistical Mechanics Model of the Conformational and Sequence Spaces of Proteins,” Macromolecules, vol. 22, no. 10, pp. 3986–3997, Oct. 1989.

[8]     A. A. Tantar, N. Melab, E. G. Talbi, B. Parent, and D. Horvath, “A parallel hybrid genetic algorithm for protein structure prediction on the computational grid,” Futur. Gener. Comput. Syst., vol. 23, no. 3, pp. 398–409, Mar. 2007.

[9]     V. Cutello, G. Nicosia, M. Pavone, and J. Timmis, “An immune algorithm for protein structure prediction on lattice models,” IEEE Trans. Evol. Comput., vol. 11, no. 1, pp. 101–117, Feb. 2007.

[10]  R. Unger, “The Genetic Algorithm Approach to Protein Structure Prediction,” Springer, Berlin, Heidelberg, 2004, pp. 153–175.

[11]  H. D. D. Ziero, L. S. Buller, A. Mudhoo, L. C. Ampese, S. I. Mussatto, and T. F. Carneiro, “An overview of subcritical and supercritical water treatment of different biomasses for protein and amino acids production and recovery,” J. Environ. Chem. Eng., p. 104406, Sep. 2020.

[12]  A. Mazidi, E. Damghanijazi, and S. Tofighy, “An Energy-efficient Virtual Machine Placement Algorithm based Service Level Agreement in Cloud Computing Environments,” Circ. Comput. Sci., vol. 2, no. 6, pp. 1–6, 2017.

[13]  A. Mazidi, M. Golsorkhtabaramiri, and M. Y. Tabari, “Autonomic resource provisioning for multilayer cloud applications with K-nearest neighbor resource scaling and priority-based resource allocation,” Softw. Pract. Exp., Apr. 2020.

[14]  Sharapov RR, “Genetic Algorithms: Basic Ideas, Variants and Analysis,” 2007.

[15]  M. T. Hoque, M. Chetty, A. Lewis, A. Sattar, and V. M. Avery, “DFS-generated pathways in GA crossover for protein structure prediction,” Neurocomputing, vol. 73, no. 13–15, pp. 2308–2316, Aug. 2010.

[16]  A. Mazidi, M. Golsorkhtabaramiri, and M. Yadollahzadeh Tabari, “An autonomic risk- and penalty-aware resource allocation with probabilistic resource scaling mechanism for multilayer cloud resource provisioning,” Int. J. Commun. Syst., p. e4334, Feb. 2020.

[17]  I. S. Hart W, “HP Benchmarks,” 2005.

[18]  N. Lesh, M. Mitzenmacher, and S. Whitesides, “A complete and effective move set for simplified protein folding,” in Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB, 2003, pp. 188–195.