Розглянуто завдання прогнозування третинної структури білка з урахуванням його первинної послідовності. Проблема в тому, що науковці, з усією своєю обчислювальною потужністю і набором експериментальних даних, не навчилися будувати моделі, які описують процес згортання молекул білка і прогнозують третинну структуру білка на основі його первинної структури. Однак неправильно вважати, що в цій галузі науки нічого не відбувається. Відомо закономірності складання (згортання) білка, розроблено методи його моделювання. Аналіз поточного стану досліджень щодо цих проблем свідчить про наявність недоліків, пов'язаних із точністю прогнозування і часом, необхідним для отримання оптимального рішення. Отже, розроблення нових обчислювальних методів, позбавлених цих недоліків, є актуальним. Зосереджено увагу на моделі ґратки, що є особливим випадком відомого гідрофобно-полярного кропу. запропоновано конформацію білка за обраною моделлю, гібридні алгоритми клонального відбору, диференціал. Оскільки процеси згортання білка до кінця не вивчені, дослідники запропонували ряд спрощених моделей, заснованих на фізичних властивостях молекул, що призводить до проблем комбінаторної оптимізації. Як модель білка обрано гідрофобно-полярну спрощену модель на плоскій трикутній ґратці. З погляду задачі оптимізації, проблема фолдингу білка зводиться до пошуку конформації з мінімальною енергією. У ґратчастих моделях конформацію представлено у вигляді шляху, що не має самоперетинів. Для вирішення цієї проблеми запропоновано гібридну штучну імунну систему у формі комбінації алгоритмів клонального відбору та диференціальної еволюції. Розроблений гібридний алгоритм використовує спеціальні способи кодування та декодування індивідуумів, а також функцію афінності, що дають змогу зменшити кількість некоректних конформацій (рішень з самоперетинами). Доведено, що в цій рецептурі завдання складання білка є NP-повним. Тому загалом точні методи не здатні впоратися з поставленим завданням у прийнятний час. Для перевірки ефективності алгоритму проведено експериментальні дослідження на тестових послідовностях. Для тестування алгоритмів обрано гідрофобно-полярну модель Ділла на двомірній трикутній ґратці. Здійснено експериментальні дослідження на тестових послідовностях, які показали переваги розроблених алгоритмів перед іншими методами.
- 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
- 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
- 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
- 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
- Dill, K. A. (1985). "Theory for the folding and stability of globular proteins," Biochemistry, 24(6), 1501-1509. https://doi.org/10.1021/bi00327a032
- 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
- Gulyanitskiy, L. F., & Rudyik, V. A. (2010). Simulation of protein coagulation in space. Computer mathematics, 1, 128-137. [In Russian].
- 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
- 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
- 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
- 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
- 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
- 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