2020, випуск 3, c. 59-73

Одержано 21.08.2020; Виправлено 15.09.2020; Прийнято 23.10.2020

Надруковано 27.10.2020; Вперше Online 05.11.2020

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

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

 

УДК 519.8

Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка

С.А. Чорножук

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

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

 

Вступ. Згортка просторової білкової структури – важлива та актуальна проблема обчислювальної біології. Розглядаючи математичну модель задачі, можна легко зробити висновок, що передбачення оптимального положення білків у трьохвимірній ґратці – це NP-складна задача. Отже, для вирішення цієї проблеми можна використовувати деякі методи навчання з підкріпленням, такі як Q-learning. У статті пропонується нове геометричне подання простору «стан-дія», яке відрізняється від усіх альтернативних існуючих способів подання, що використовуються для розв’язку цієї задачі.

Мета роботи. Аналіз існуючих підходів щодо подання просторів станів та дій, що використовуються для алгоритму Q-learning для задачі передбачення третинної структури білків, виявлення їх переваг та недоліків, застосування нового геометричного представлення простору «стан-дія», порівняння існуючих та запропонованого підходів, окреслення можливих майбутніх кроків подальших досліджень.

Результат. Робота запропонованого алгоритму порівнюється з іншими на основі 10 відомих ланцюгів довжиною 48, вперше запропонованих у [16]. Для кожного з ланцюгів алгоритм Q-learning з запропонованим поданням простору «стан-дія» перевершував той самий алгоритм Q-learning з альтернативними існуючими поданнями простору «стан-дія» як з точки зору середніх, так і мінімальних величин цільової функції енергії отриманих ланцюгів у ґратці. Крім того, левова частина способів існуючого подання використовується для передбачення вторинної структури білків. Однак під час експериментів як існуючі, так і запропонований способи подання були дещо змінені для вирішення цієї ж проблеми в 3D, що є більш обчислювально складним завданням.

Висновок. Якість алгоритму Q-learning з запропонованим геометричним представленням простору «стан-дія» – експериментально підтверджена. Отже, доведено, що подальші дослідження на цю тему – перспективні. Більш того, вже висвітлено кілька кроків майбутніх досліджень, таких як поєднання запропонованого підходу з методами глибокого машинного навчання.

 

Ключові слова: просторова структура білка, комбінаторна оптимізація, відносне кодування, машинне навчання, Q-learning, рівняння Беллмана, простір станів, простір дій, базис у трьохвимірному просторі.

 

Цитувати так: Чорножук С.А. Нове геометричне подання простору «станів-дій» Q-learning алгоритму в проблемі передбачення третинної структури білка. Cybernetics and Computer Technologies. 2020. 3. С. 59–73. https://doi.org/10.34229/2707-451X.20.3.6

 

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

           1.     Dill K.A. Theory for the folding and stability of globular proteins. Biochemistry. 1985. 24 (6). P. 1501–1509. https://doi.org/10.1021/bi00327a032

           2.     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. https://doi.org/10.1007/978-3-540-24653-4_1

           3.     Custodio F.L., Barbosa H.J., Dardenne L.E. A multiple minima genetic algorithm for protein structure prediction. Applied Software Computing, Elsevier. 2014. 15. P. 88–99. https://doi.org/10.1016/j.asoc.2013.10.029

           4.     Boscovic B., Brest J. Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hydrophobic-polar model and cubic lattice. Applied Soft Computing. 2016. 45. P. 61–70. https://doi.org/10.1016/j.asoc.2016.04.001

           5.     Morshedian A., Razmara J., Lotfi S. A novel approach for protein structure prediction based on estimation of distribution algorithm. Software computing. 2019. 23. P. 4777–4788. https://doi.org/10.1007/s00500-018-3130-0

           6.     Nazmul R., Chetty M., Chowdhury A.R. Multimodal Memetic Framework for low-resolution protein structure prediction. Swarm and Evolutionary Computation, Elsevier. 2020. 52. https://doi.org/10.1016/j.swevo.2019.100608

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

           8.     Chornozhuk S.A. The new simulated annealing algorithm for a protein structure folding problem. Komp’uternaa matematika. 2018. 1. P. 118–124. http://dspace.nbuv.gov.ua/handle/123456789/161856

           9.     Jafari R., Javidi M.M. Solving the protein folding problem in hydrophobic-polar model using deep reinforcement learning. SN Applied Sciences, Springer. 2020. 2 (259). https://doi.org/10.1007/s42452-020-2012-0

       10.     Czibula G., Bocicor M., Czibula I. A reinforcement learning model for solving the folding problem. Int J Computational Technology Applied. 2011. 2. P. 171–182.

       11.     Li Y., Kang H., Ye K., Yin S. FoldingZero: protein folding from scratch in hydrophobic-polar model. Deep reinforcement learning workshop (Oral) of NIPS. 2018. https://arxiv.org/abs/1812.00967

       12.     Dogan B., Olmez T. A novel state space representation for the solution of 2D-HP protein folding problem using reinforcement learning methods. Applied Soft Computing, Elsevier. 2015. 26. P. 213–223. https://doi.org/10.1016/j.asoc.2014.09.047

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

       14.     Гуляницкий Л.Ф., Рудык В.А. Проблема предсказания структуры протеина: формализация с использованием кватернионов. Кибернетика и системный анализ. 2013. 49 (4). С. 130–136. https://doi.org/10.1007/s10559-013-9546-8

       15.     Sutton R.S., Barto A.G. Reinforcement Learning: An Introduction. MIT Press, 1998. 9 (5). P. 1054. https://doi.org/10.1109/TNN.1998.712192

       16.     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. 92 (1). P. 325–329. https://doi.org/10.1073/pnas.92.1.325

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

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

 

 

 

© Вебсайт та оформлення. 2019-2022,

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

Національна академія наук України.