Прогнозування третинної структури білка на двомірній трикутній ґратці гібридним еволюційним алгоритмом

dc.citation.epage32
dc.citation.issue2
dc.citation.journalTitleУкраїнський журнал інформаційних технологій
dc.citation.spage27
dc.citation.volume3
dc.contributor.affiliationХерсонський національний технічний університет
dc.contributor.affiliationKherson National Technical University
dc.contributor.authorФефелова, І. М.
dc.contributor.authorЛитвиненко, В. І.
dc.contributor.authorФефелов, А. О.
dc.contributor.authorFefelova, I. M.
dc.contributor.authorLytvynenko, V. I.
dc.contributor.authorFefelov, A. O.
dc.coverage.placenameЛьвів
dc.coverage.placenameLviv
dc.date.accessioned2024-03-27T07:28:32Z
dc.date.available2024-03-27T07:28:32Z
dc.date.created2021-02-28
dc.date.issued2021-02-28
dc.description.abstractРозглянуто завдання прогнозування третинної структури білка з урахуванням його первинної послідовності. Проблема в тому, що науковці, з усією своєю обчислювальною потужністю і набором експериментальних даних, не навчилися будувати моделі, які описують процес згортання молекул білка і прогнозують третинну структуру білка на основі його первинної структури. Однак неправильно вважати, що в цій галузі науки нічого не відбувається. Відомо закономірності складання (згортання) білка, розроблено методи його моделювання. Аналіз поточного стану досліджень щодо цих проблем свідчить про наявність недоліків, пов'язаних із точністю прогнозування і часом, необхідним для отримання оптимального рішення. Отже, розроблення нових обчислювальних методів, позбавлених цих недоліків, є актуальним. Зосереджено увагу на моделі ґратки, що є особливим випадком відомого гідрофобно-полярного кропу. запропоновано конформацію білка за обраною моделлю, гібридні алгоритми клонального відбору, диференціал. Оскільки процеси згортання білка до кінця не вивчені, дослідники запропонували ряд спрощених моделей, заснованих на фізичних властивостях молекул, що призводить до проблем комбінаторної оптимізації. Як модель білка обрано гідрофобно-полярну спрощену модель на плоскій трикутній ґратці. З погляду задачі оптимізації, проблема фолдингу білка зводиться до пошуку конформації з мінімальною енергією. У ґратчастих моделях конформацію представлено у вигляді шляху, що не має самоперетинів. Для вирішення цієї проблеми запропоновано гібридну штучну імунну систему у формі комбінації алгоритмів клонального відбору та диференціальної еволюції. Розроблений гібридний алгоритм використовує спеціальні способи кодування та декодування індивідуумів, а також функцію афінності, що дають змогу зменшити кількість некоректних конформацій (рішень з самоперетинами). Доведено, що в цій рецептурі завдання складання білка є NP-повним. Тому загалом точні методи не здатні впоратися з поставленим завданням у прийнятний час. Для перевірки ефективності алгоритму проведено експериментальні дослідження на тестових послідовностях. Для тестування алгоритмів обрано гідрофобно-полярну модель Ділла на двомірній трикутній ґратці. Здійснено експериментальні дослідження на тестових послідовностях, які показали переваги розроблених алгоритмів перед іншими методами.
dc.description.abstractThis 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-polardill. 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 representedas 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.
dc.format.extent27-32
dc.format.pages6
dc.identifier.citationФефелова І. М. Прогнозування третинної структури білка на двомірній трикутній ґратці гібридним еволюційним алгоритмом / І. М. Фефелова, В. І. Литвиненко, А. О. Фефелов // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2021. — Том 3. — № 2. — С. 27–32.
dc.identifier.citationenFefelova I. M. Prediction of the tertiary structure of a protein on a twodimensional triangular lattice by a hybrid evolutionary algorithm / I. M. Fefelova, V. I. Lytvynenko, A. O. Fefelov // Ukrainian Journal of Information Technology. — Lviv : Lviv Politechnic Publishing House, 2021. — Vol 3. — No 2. — P. 27–32.
dc.identifier.issn2707-1898
dc.identifier.urihttps://ena.lpnu.ua/handle/ntb/61538
dc.language.isouk
dc.publisherВидавництво Львівської політехніки
dc.publisherLviv Politechnic Publishing House
dc.relation.ispartofУкраїнський журнал інформаційних технологій, 2 (3), 2021
dc.relation.ispartofUkrainian Journal of Information Technology, 2 (3), 2021
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[7] Gulyanitskiy, L. F., & Rudyik, V. A. (2010). Simulation of protein coagulation in space. Computer mathematics, 1, 128-137. [In Russian].
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.references[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[7] Gulyanitskiy, L. F., & Rudyik, V. A. (2010). Simulation of protein coagulation in space. Computer mathematics, 1, 128-137. [In Russian].
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.referencesen[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
dc.relation.urihttps://doi.org/10.1089/cmb.1998.5.27
dc.relation.urihttps://doi.org/10.3906/elk-1909-31
dc.relation.urihttps://doi.org/10.1109/TEVC.2006.880328
dc.relation.urihttps://doi.org/10.1109/TEVC.2002.1011539
dc.relation.urihttps://doi.org/10.1021/bi00327a032
dc.relation.urihttps://doi.org/10.1109/IMCSIT.2008.4747347
dc.relation.urihttps://doi.org/10.1007/3-540-45712-7_74
dc.relation.urihttps://doi.org/10.1016/j.compbiolchem.2013.08.011
dc.relation.urihttps://doi.org/10.1023/A:1008202821328
dc.relation.urihttps://doi.org/10.1186/1477-5956-9-S1-S19
dc.relation.urihttps://doi.org/10.1089/cmb.2016.0104
dc.relation.urihttps://doi.org/10.1186/s13040-018-0176-6
dc.rights.holder© Національний університет “Львівська політехніка”, 2021
dc.subjectфолдинг білка
dc.subjectгідрофобно-полярна модель
dc.subjectклональний відбір
dc.subjectдиференціальна еволюція
dc.subjectштучні імунні системи
dc.subjectгідрофобно-полярна модель
dc.subjectprotein folding
dc.subjecthydrophobic-polar model
dc.subjectclonal selection
dc.subjectdifferential evolution
dc.subjectartificial immune systems
dc.subjecthydrophobic-polar model
dc.titleПрогнозування третинної структури білка на двомірній трикутній ґратці гібридним еволюційним алгоритмом
dc.title.alternativePrediction of the tertiary structure of a protein on a twodimensional triangular lattice by a hybrid evolutionary algorithm
dc.typeArticle

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
2021v3n2_Fefelova_I_M-Prediction_of_the_tertiary_27-32.pdf
Size:
1.75 MB
Format:
Adobe Portable Document Format
Thumbnail Image
Name:
2021v3n2_Fefelova_I_M-Prediction_of_the_tertiary_27-32__COVER.png
Size:
1.61 MB
Format:
Portable Network Graphics

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.85 KB
Format:
Plain Text
Description: