Received 18.06.2020; Revised 29.06.2020; Accepted 30.06.2020

Published 24.07.2020; First Online 27.07.2020

https://doi.org/10.34229/2707-451X.20.2.3

Previous  |  Full text (in Ukrainian)  |  Next

 

UDC 519.8

Genetic Algorithm with New Stochastic Greedy Crossover Operator for Protein Structure Folding Problem

Leonid Hulianytskyi ,   Sergii Chornozhuk ^*

V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. The spatial protein structure folding is an important and actual problem in biology. Considering the mathematical model of the task, we can conclude that it comes down to the combinatorial optimization problem. Therefore, genetic and mimetic algorithms can be used to find a solution. The article proposes a genetic algorithm with a new greedy stochastic crossover operator, which differs from classical approaches with paying attention to qualities of possible ancestors.

The purpose of the article is to describe a genetic algorithm with a new greedy stochastic crossover operator, reveal its advantages and disadvantages, compare the proposed algorithm with the best-known implementations of genetic and memetic algorithms for the spatial protein structure prediction, and make conclusions with future steps suggestion afterward.

Result. The work of the proposed algorithm is compared with others on the basis of 10 known chains with a length of 48 first proposed in [13]. For each of the chain, a global minimum of free energy was already precalculated. The algorithm found 9 out of 10 spatial structures on which a global minimum of free energy is achieved and also demonstrated a better average value of solutions than the comparing algorithms.

Conclusion. The quality of the genetic algorithm with the greedy stochastic crossover operator has been experimentally confirmed. Consequently, its further research is promising. For example, research on the selection of optimal algorithm parameters, improving the speed and quality of solutions found through alternative coding or parallelization. Also, it is worth testing the proposed algorithm on datasets with proteins of other lengths for further checks of the algorithm’s validity.

 

Keywords: spatial protein structure, combinatorial optimization, genetic algorithms, crossover operator, stochasticity.

 

Cite as: Hulianytskyi L., Chornozhuk S. Genetic Algorithm with New Stochastic Greedy Crossover Operator for Protein Structure Folding Problem. Cybernetics and Computer Technologies. 2020. 2. P. 19–29. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.2.3

 

References

           1.     Dill K.A. Theory for the folding and stability of globular proteins. Biochemistry. 1985. 24. P. 1501–1509. https://doi.org/10.1021/bi00327a032

           2.     Anfinsen C.B., Haber E., Sela M., White Jr.F.H. The kinetics of formation of native ribonuclease during oxidation of the reduced polypeptide chain. In Proceedings of the National Academy of Sciences of the USA. 1961. 47. P. 1309–1314. https://doi.org/10.1073/pnas.47.9.1309

           3.     Chornozhuk S.A. The new simulated annealing algorithm for a protein structure folding problem. Komp’uternaa matematika, 2018. 1. P. 118–124. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/161856

           4.     Dorigo M., Stützle T. Ant colony optimization. Cambridge (MA): MIT Press, 2004. https://doi.org/10.7551/mitpress/1290.001.0001

           5.     Shmygelska A., Hoos H.H. An ant colony optimization algorithm for the 2D and 3Dhydrophobic polar protein folding problem. BMC Bioinformatics. 2005. 6 (30). P. 30–52. https://doi.org/10.1186/1471-2105-6-30

           6.     Hulianytskyi L.F., Rudyk V.O. Development and analysis of the parallel ant colony optimization algorithm for solving the protein tertiary structure prediction problem. Information Theories and Applications. 2014. 21 (4). P. 392–397.

           7.     Hlybovets M.M., Huliaeva N.M. Evolutional algorithms. К.: NaU-KMA, 2013. (in Ukrainian)

           8.     Whitley D. Next Generation Genetic Algorithms: A User’s Guide and Tutorial. Handbook of Metaheuristics. Springer Int. Publ. AG. 2019. P. 245–274. https://doi.org/10.1007/978-3-319-91086-4_8

           9.     Moscato P., Cotta C. An Accelerated Introduction to Memetic Algorithms. Handbook of Metaheuristics. Springer Int. Publ. AG. 2019. P. 275-309. https://doi.org/10.1007/978-3-319-91086-4_9

       10.     Hulianytskyi L.F., Mulesa O.Y. The applied methods of combinatorial optimization. К.: Kyivskyi universytet, 2016. (in Ukrainian)

       11.     N. Krasnogor, Smith J. A memetic algorithm with self-adaptive local search: TSP as a case study. In GECCO 2000: Proceedings of the Genetic and Evolutionary Computation Conference, 2000. P. 987–994.

       12.     Bazzoli A., Tettamanzi A.G.B. A Memetic Algorithm for Protein Structure Prediction in a 3D-Lattice HP Model. Applications of Evolutionary Computing. 2004. 3005. P. 1–10. https://doi.org/10.1007/978-3-540-24653-4_1

       13.     Yue K., Fiebig K.M., Thomas P.D., Chan H.S., Shakhnovich E.I., Dill K.A. A Test of Lattice Protein Folding Algorithms. Proceedings of the National Academy of Sciences. 1995. P. 325–329. https://doi.org/10.1073/pnas.92.1.325

       14.     Custodio F.L., Barbosa H.J., Dardenne L.E. A multiple minima genetic algorithm for protein structure prediction. Applied Software Computing. 2014. P. 88–99. https://doi.org/10.1016/j.asoc.2013.10.029

       15.     Gueorguiev V., Kuttel M. Implementation, Validation and Profiling of a Genetic Algorithm for Molecular Conformational Optimization. Proceedings of the Annual Conference of the South African Institute of Computer Scientists and Information Technologists. ACM, 2016. https://doi.org/10.1145/2987491.2987529

       16.     Mahmood A.R., Sumaiya I., Firas K., Tamjidul M.H., Abdul S. Guided macro-mutation in a graded energy based genetic algorithm for protein structure prediction. Computational biology and chemistry. 2016. 61. P. 162–177. https://doi.org/10.1016/j.compbiolchem.2016.01.008

       17.     Morshedian A., Razmara J., Lotfi S. A novel approach for protein structure prediction based on estimation of distribution algorithm. Software computing. 2018. P. 1–12. https://doi.org/10.1007/s00500-018-3130-0

       18.     Hulianytskyi L.F., Rudyk V.A. Protein structure folding problem: the formalization using quaternion approach. Cybernetics and System Analysis. 2013. 49 (4). P. 130–136. https://doi.org/10.1007/s10559-013-9546-8

       19.     Nazmul R., Chetty M., Chowdhury A.R. Multimodal Memetic Framework for low-resolution protein structure prediction. Swarm and Evolutionary Computation. 2020. 52. 100608. https://doi.org/10.1016/j.swevo.2019.100608

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next