Задача поиска третичной структуры белка по его первичной аминокислотной последовательности (protein
folding problem, PFP) – важнейшая задача структурной биологии. К сожалению, даже такая грубая модель, как
HP-PFP-2, учитывающая только гидрофобные взаимодействия аминокислотных остатков на двумерной решетке,
является NP-сложной и может успешно решаться только эвристическими методами глобальной оптимизации,
например, муравьиным алгоритмом. В статье исследуются способы модификации и распараллеливания
муравьиного алгоритма для задачи фолдинга белков. Подробно описана программная реализация
параллельного муравьиного алгоритма на графических процессорах, обсуждаются результаты вычислительного
эксперимента.
Задача поиска третичной структуры белка по его первичной аминокислотной последовательности (protein
folding problem, PFP) – важнейшая задача структурной биологии. К сожалению, даже такая грубая модель, как
HP-PFP-2, учитывающая только гидрофобные взаимодействия аминокислотных остатков на двумерной решетке,
является NP-сложной и может успешно решаться только эвристическими методами глобальной оптимизации,
например, муравьиным алгоритмом. В статье исследуются способы модификации и распараллеливания
муравьиного алгоритма для задачи фолдинга белков. Подробно описана программная реализация
параллельного муравьиного алгоритма на графических процессорах, обсуждаются результаты вычислительного
эксперимента.
The task of finding the tertiary structure of the protein by its primary amino acid sequence (protein folding problem:
PFP) – is a major challenge for structural biology. Unfortunately, even such a crude model as HP-PFP-2, which takes
into account only hydrophobic interaction of amino acid residues on a two-dimensional lattice is NP-hard and can be
successfully solved only by heuristic methods of global optimization, for example, the ant colony optimization
algorithm. This article describres the methods of modification and parallelization of ant colony optimization algorithm
for the protein folding problem. It is described in detail the software implementation of parallel ant colony optimization
algorithm on the graphics processing units.
Oqsilni uchlamchi tuzilishini uning daslabki aminokislotali kеtma-kеtligi (protein folding problem: PFP) bo’yicha
izlash masalasi – strukturali biologiyaning eng muhim masalalaridan hisoblanadi. Afsuski, hattoki ikki o’lchovli
to’rdagi aminokislota qoldiqlarini gidrofob ta`sirinigina hisobga oluvchi HP-PFP-2 kabi mukammal bo’lmagan
modеlning ham murakkablik darajasi NP hisoblanadi va faqatgina global optimallashtirishning evristik usullari bilan
muvaffaqiyatli yechilishi mumkin, masalan, chumoli algoritmi yordamida. Maqolada oqsil foldingi masalasi uchun
chumoli algoritmini takomillashtirish va parallеllashtirish usullari o’rganilgan. Parallel chumoli algoritmini grafik
protsеssorlarga dasturiy tadbiqi to’liq tavsiflangan va hisoblash eksperimenti natijalari muhokama qilingan.
| № | Author name | position | Name of organisation |
|---|---|---|---|
| 1 | Bazarov R.k. | младший научный сотрудник | Toshkent axborot texnologiyalari universiteti |
| № | Name of reference |
|---|---|
| 1 | Levinthal C. How to Fold Graciously // Mossbauer Spectroscopy in Biological Systems: Proceedings of a meeting held at Allerton House, Monticello, Illinois. J.T.P. DeBrunner and E. Munck eds., University of Illinois Press. - № 41, 1969. - Рp. 22-24. |
| 2 | Mann, M., S. Will, and R. Backofen. CPSP-tools - Exact and complete algorithms for high-throughput 3D lattice protein studies.Bmc Bioinformatics. - № 9(1), 2008. - 230 p. |
| 3 | Thachuk, C., A. Shmygelska, and H.H. Hoos, A replica exchange Monte Carlo algorithm for protein folding in the HP model // Bmc Bioinformatics № 8, 2007. – 342 p. |
| 4 | Gordon S. The self-avoiding walk: a brief survey // Proceednigs of the 33rd SPA Conference. Surveys in Stochastic Processes. Berlin: European Math. Society, 2010. - Рp. 181–199. |
| 5 | Shmygelska, A. and H.H. Hoos. An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem // Bmc Bioinformatics. - № 6(1), 2005. – Рp. 30. |
| 6 | Thalheim T., Merkle D., Middendorf M. Protein folding in the HP-model solved with a hybrid population based ACO Algorithm // IAENG International Journal of Computer Science. - № 35 (3), 2008. - Рp. 291-300. |
| 7 | Xiao-Min Hu, Jun Zhang, Yun Li. Orthogonal methods based ant colony search for solving continious optimization problems // Journal of Computer Science and Technology. - № 23(1), 2008. - Рp. 2-18 (JCST_paper.pdf). |
| 8 | Stuzle T., Doringo M. A short convergence proof for a class of ACO algorithms // IEEE Transactions on Evolutionary Computation. – № 6(4), 2002. - Рp. 358-365. |
| 9 | Carvelli L., Sebastiani G. Some issues of aco algorithm convergence / Ant Colony Optimization - Methods and Applications, (Ed. A.Ostfeld) - InTech, 2011. - Рp. 39-52. |
| 10 | Гуляницкий Л. Рудык В. Анализ алгоритмов прогнозирования третичной структуры протеина на базе метода оптимизации муравьиными колониями // Problems of Computer Intellectualization (Eds. V.Velichko, O.Voloshin, K.Markov). – Kiev-Sofia: V.M.Glushkov Institute of Cybernetics, ITHEA, 2012. – Рp. 152-159. |
| 11 | Chu D., Till M., Zomaya A. Parallel ant colony optimization for 3D protein structure prediction using the HP lattice model // Proceedings 19th IEEE International Parallel and Distributed Processing Symposium. - № 07, 2005. - 193 p. |
| 12 | Chu D., Till M., Zomaya A. Parallel ant colony optimization for 3D protein structure prediction using the HP lattice model // Proceedings 19th IEEE International Parallel and Distributed Processing Symposium. - № 07, 2005. - 193 p. |
| 13 | Delisle P., Krajecki M., Gravel M., Gagne C. Parallel implementation of an ant colony optimization metaheuristic with OpenMP// Proceedings of the 3rd European Workshop on OpenMP (EWOMP'01), Barselona, 2001. - Рp. 8- 12. |
| 14 | Wen-mei W. Hwu. GPU computing gems emerald edition. - Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, 2011. – 886 p. |
| 15 | Бекмуратов Т.Ф., Мухамедиева Д.Т., Базаров Р., Ахмедов Д.Д. Параллельный муравьиный алгоритм оптимизации // Узб. журнал «Проблемы информатики и энергетики». – Ташкент, 2014. - № 1-2. - С. 11-15. |
| 16 | Базаров Р.К. Программный продукт: «Параллельная версия программы, реализующей муравьиный алгоритм сворачивания белоков на плоскости (АСО-HPPFP-2)» // АИС РУз. Свидетельство № DGU-02697. 26.12.2012 г. |
| 17 | Базаров Р.К. Программный продукт: «Реализация муравьиного алгоритма для изучения фолдинга белков на плоскости методами программных агентов (Agent-ACOHPPFP-2)» // АИС РУз. Свидетельство № DGU- 04104. 09.12.2016 г. |
| 18 | Базаров Р.К. Программный продукт: «Реализация муравьиного алгоритма для изучения фолдинга белков на плоскости с помощью графических процессоров (GPU-ACO-HPPFP-2)» // АИС РУз. Свидетельство № DGU-03215. 08.07.2015 г. |
| 19 | Базаров Р.К. Решение задачи фолдинга белков в распределенных вычислительных грид-системах // «Проблемы информационных и телекоммуникационных технологий»: Сб. докладов Републиканской научно-технической конференции. 10-11 марта 2016. - Ташкент, 2016. Ч.2. - С. 130-131. |
| 20 | CUDA Zone [Электронный ресурс] / NVIDIA Corporation. – Режим доступа: https://developer.nvidia.com/cuda-zone. |