Prediction of the tertiary structure of a protein on a two-dimensional triangular lattice by a hybrid evolutionary algorithm

2021;
: 27-32
https://doi.org/10.23939/ujit2021.02.027
Received: November 07, 2021
Accepted: November 23, 2021
1
Kherson National Technical University, Kherson, Ukraine
2
Kherson National Technical University, Kherson, Ukraine
3
Kherson National Technical University, Kherson, Ukraine

This work discusses the problem of forecasting the tertiary structure of a protein, based on its primary sequence. The problem is that science, with all its computing power and a set of experimental data, has not learned to build models that describe the process of protein molecule coagulation and predict the tertiary structure of a protein, based on its primary structure. However, it is wrong to assume that nothing is happening in this field of science. The regularities of folding (convolution) of the protein are known, methods for its modelling have been developed. Analysis of the current state of research in the field of these problems indicates the presence of shortcomings associated with the accuracy of forecasting and the time necessary to obtain the optimal solution. Consequently, the development of new computational methods, deprived of these shortcomings, seems relevant. In this work, the authors focused on the lattice model, which is a special case of the known hydrophobic-polar dill. protein conformation according to the chosen model, hybrid algorithms of cloning selection, differential are proposed. Since the processes of protein coagulation have not been fully understood, the researchers proposed several simplified models based on the physical properties of molecules and which leads to problems of combinatorial optimization. A hydrophobic-polar simplified model on the planar triangular lattice is chosen as a protein model. From the point of view of the optimization problem, the problem of protein folding comes down to finding a conformation with minimal energy. In lattice models, the conformation is represented as a non-self-cutting pathway. A hybrid artificial immune system in the form of a combination of clonal selection and differential evolution algorithms is proposed to solve this problem. The paper proposes a hybrid method and algorithm to solve the protein folding problem using the HP model on a planar triangular lattice. In this paper, a hybrid method and algorithm for solving the protein folding problem using the HP model on a planar triangular lattice are proposed. The developed hybrid algorithm uses special methods for encoding and decoding individuals, as well as the affinity function, which allows reducing the number of incorrect conformations (self-cutting solutions). Experimental studies on test hp-sequences were conducted to verify the effectiveness of the algorithm. The results of these experiments showed some advantages of the developed algorithm over other known methods. Experiments have been taught to verify the effectiveness of the proposed approach.

The results labelled "Best" show the minimum energy values achieved over 30 runs, while the results labelled "Medium" show the robustness of the algorithm to achieve minima. Regarding robustness, the hybrid algorithm also offers an advantage, showing higher results. A comparative analysis of the performance results of the proposed algorithm on test sequences with similar results of other published methods allows us to conclude the high efficiency of the developed method. In particular, the result is more stable, and, in some cases, conformations with lower energy are obtained.

  1. Berger, B., & Leighton, T. (1998). Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. J. of Computational Biology, 5(1), 27-40. https://doi.org/10.1089/cmb.1998.5.27
  2. Boumedine, N., & Bouroubi, S. (2021). A new hybrid genetic algorithm for protein structure prediction on the 2D triangular lattice. Turkish J. Electr. Eng. Comput. Sci., 29, 499-513. https://doi.org/10.3906/elk-1909-31
  3. Cutello, V., Niscosia, G., Pavone, M., & Timmis, J. (2007). An immune algorithm for protein structure prediction on lattice models. IEEE Transactions on Evolutionary Computation, 11(1), pp. 101–117. https://doi.org/10.1109/TEVC.2006.880328
  4. De Castro, L. N., & Von Zuben, F. J. (2002). Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation, 6(3), 239–251. https://doi.org/10.1109/TEVC.2002.1011539
  5. Dill, K. A. (1985). "Theory for the folding and stability of globular proteins," Biochemistry, 24(6), 1501-1509. https://doi.org/10.1021/bi00327a032
  6. Fidanova, S., & Lirkov, I. (2008). Ant colony system approach for protein folding, 2008 International Multiconference on Computer Science and Information Technology, 887–891. https://doi.org/10.1109/IMCSIT.2008.4747347
  7. Gulyanitskiy, L. F., & Rudyik, V. A. (2010). Simulation of protein coagulation in space. Computer mathematics, 1, 128-137. [In Russian].
  8. Krasnogor, N., Blackburne, B. P., Burke, E. K., & Hirst, J. D. (2002). Multimeme algorithms for protein structure prediction. In Proc. Int. Conf. Parallel Problem Solving from Nature (PPSN VII), Granada, Spain, Sep. 2002, 769-778. https://doi.org/10.1007/3-540-45712-7_74
  9. Liu, J., Sun, Y., Li, G., Song, B., & Huang, W. (2013). Heuristic-based tabu search algorithm for folding two-dimensional AB off-lattice model proteins. Computational biology and chemistry, 47, 142-148. https://doi.org/10.1016/j.compbiolchem.2013.08.011
  10. Storn R., & Price, K. V. (1997). Price Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359. https://doi.org/10.1023/A:1008202821328
  11. Su, S. C., Lin, C. J. & Ting, C. K. (2011). An effective hybrid of hill climbing and genetic algorithm for 2D triangular protein structure prediction. Proteome Sci, 9, S19. https://doi.org/10.1186/1477-5956-9-S1-S19
  12. Yang, C. H., Lin, Y. S., Chuang, L. Y., & Chang, H. W. (2017). A Particle Swarm Optimization-Based Approach with Local Search for Predicting Protein Folding. Journal of computational biology: a journal of computational molecular cell biology, 24(10), 981-994. https://doi.org/10.1089/cmb.2016.0104
  13. Yang, C. H., Wu, K. C., Lin, Y. S. et al. (2018). Protein folding prediction in the HP model using ions motion optimization with a greedy algorithm. BioData Mining, 11, 17. https://doi.org/10.1186/s13040-018-0176-6