Прогнозування третинної структури білка на двомірній трикутній ґратці гібридним еволюційним алгоритмом
Date
2021-02-28
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Львівської політехніки
Lviv Politechnic Publishing House
Lviv Politechnic Publishing House
Abstract
Розглянуто завдання прогнозування третинної структури білка з урахуванням його первинної послідовності. Проблема в тому, що науковці, з усією своєю обчислювальною потужністю і набором експериментальних даних, не навчилися будувати моделі, які описують процес згортання молекул білка і прогнозують третинну структуру білка на основі його первинної структури. Однак неправильно вважати, що в цій галузі науки нічого не відбувається. Відомо закономірності
складання (згортання) білка, розроблено методи його моделювання. Аналіз поточного стану досліджень щодо цих проблем свідчить про наявність недоліків, пов'язаних із точністю прогнозування і часом, необхідним для отримання оптимального рішення. Отже, розроблення нових обчислювальних методів, позбавлених цих недоліків, є актуальним. Зосереджено увагу на моделі ґратки, що є особливим випадком відомого гідрофобно-полярного кропу. запропоновано конформацію білка за обраною моделлю, гібридні алгоритми клонального відбору, диференціал. Оскільки процеси згортання білка до кінця не вивчені, дослідники запропонували ряд спрощених моделей, заснованих на фізичних властивостях молекул, що призводить до проблем комбінаторної оптимізації. Як модель білка обрано гідрофобно-полярну спрощену модель на плоскій трикутній ґратці. З погляду задачі оптимізації, проблема фолдингу білка зводиться до пошуку конформації з мінімальною енергією. У ґратчастих моделях конформацію представлено у вигляді шляху, що не має самоперетинів. Для вирішення цієї проблеми запропоновано гібридну штучну імунну систему у формі комбінації алгоритмів клонального відбору та диференціальної еволюції. Розроблений гібридний алгоритм використовує спеціальні способи кодування та декодування індивідуумів, а також функцію афінності, що дають змогу зменшити кількість некоректних конформацій (рішень з самоперетинами). Доведено, що в цій рецептурі завдання складання білка є NP-повним. Тому загалом точні методи не здатні впоратися з поставленим завданням у прийнятний час. Для перевірки ефективності алгоритму проведено експериментальні дослідження на тестових послідовностях. Для тестування алгоритмів обрано гідрофобно-полярну модель Ділла на двомірній трикутній ґратці. Здійснено експериментальні дослідження на тестових послідовностях, які показали переваги розроблених алгоритмів перед іншими методами.
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-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.
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-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.
Description
Keywords
фолдинг білка, гідрофобно-полярна модель, клональний відбір, диференціальна еволюція, штучні імунні системи, гідрофобно-полярна модель, protein folding, hydrophobic-polar model, clonal selection, differential evolution, artificial immune systems, hydrophobic-polar model
Citation
Фефелова І. М. Прогнозування третинної структури білка на двомірній трикутній ґратці гібридним еволюційним алгоритмом / І. М. Фефелова, В. І. Литвиненко, А. О. Фефелов // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2021. — Том 3. — № 2. — С. 27–32.