Одержано 18.06.2020; Виправлено 29.06.2020; Прийнято 30.06.2020

Надруковано 24.07.2020; Вперше Online 27.07.2020

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

Попередня  |  Повний текст  |  Наступна

 

УДК 519.8

Генетичний алгоритм з жадібним стохастичним оператором схрещування для передбачення третинної структури білка

Л.Ф. Гуляницький ,   С.А. Чорножук ^*

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. Визначення просторової структури білків є важливою та актуальною проблемою біології. Розглянувши математичну модель поставленої задачі, можна зробити висновок, що вона зводиться до задачі комбінаторної оптимізації, а, отже, для знаходження розв’язку можуть бути використані генетичні та міметичні алгоритми. У статті пропонується генетичний алгоритм з  новим жадібним стохастичним оператором схрещування.

Мета роботи. Опис генетичного алгоритму з новим жадібним стохастичним оператором схрещування. В порівнянні пропонованого алгоритму з кращими відомими імплементаціями генетичних та міметичних алгоритмів, що використовуються для визначення просторової структури білка.  

Результат. Робота пропонованого алгоритму порівнюється з іншими на базі 10 відомих ланцюгів довжиною 48, для яких знайдений глобальний мінімум вільної енергії, вперше запропонованих у [13]. Алгоритм знайшов 9 із 10 просторових структур, на яких досягається глобальний мінімум вільної енергії, а також продемонстрував краще середнє значення розв’язків, ніж алгоритми з якими він порівнювався.

Висновок. Експериментально підтверджено якість роботи генетичного алгоритму з жадібним стохастичним оператором схрещування, тому перспективним є його подальше дослідження. Наприклад, дослідження підбору оптимальних параметрів алгоритму, підвищення швидкодії та якості знайдених розв’язків шляхом альтернативного кодування.

 

Ключові слова: третинна структура білка, комбінаторна оптимізація, генетичні алгоритми, оператор схрещування, стохастичність.

 

Цитувати так: Гуляницький Л.Ф., Чорножук С.А. Генетичний алгоритм з жадібним стохастичним оператором схрещування для передбачення третинної структури білка. Cybernetics and Computer Technologies. 2020. 2. С. 19–29. https://doi.org/10.34229/2707-451X.20.2.3

 

Список літератури

           1.     Dill K.A. Theory for the folding and stability of globular proteins. Biochemistry. 1985. 24. P. 1501–1509.

           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. Vol. 47. P. 1309–1314.

           3.     Чорножук C.A. Новий алгоритм імітаційного відпалу для передбачення структури білків. Компьютерная математика. 2018. C. 118–124.

           4.     Dorigo M., Stützle T. Ant colony optimization. Cambridge (MA): MIT Press, 2004.

           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.

           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.     Глибовець М.М., Гулаєва Н.М. Еволюційні алгоритми. К.: НаУ-КМА, 2013.

           8.     Whitley D. Next Generation Genetic Algorithms: A User’s Guide and Tutorial. Handbook of Metaheuristics. Springer Int. Publ. AG. 2019. P. 245–274.

           9.     Moscato P., Cotta C. An Accelerated Introduction to Memetic Algorithms. Handbook of Metaheuristics. Springer Int. Publ. AG. 2019. P. 275–309.

       10.     Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Видавничо-поліграфічний центр “Київський університет”, 2016. 142 c.

       11.     Krasnogor N., 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.

       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.

       14.     Custodio F.L., Barbosa H.J., Dardenne L.E. A multiple minima genetic algorithm for protein structure prediction. Applied Software Computing, Elsevier. 2014. P. 88–99.

       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. 16 p.

       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.

       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.

       18.     Гуляницкий Л.Ф., Рудык. В.А. Проблема предсказания структуры протеина: формализация с использованием кватернионов. Кибернетика и системный анализ. 2013. 49 (4). С. 130–136.

       19.     Nazmul R., Chetty M., Chowdhury A.R. Multimodal Memetic Framework for low-resolution protein structure prediction. Swarm and Evolutionary Computation. 2020. 52. 100608.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна