Реализация муравьиного алгоритма фолдинга белков методами программных агентов в распределенных системах

  • № 2(8) 2017

Страницы: 

103

 – 

113

Язык: русский

Открыть файл статьи
Открыть страницу статьи в Интернет

Аннотация

Проблема фолдинга белков, связанная с поиском третичной структуры белка по его первичной аминокислотной последовательности, является важнейшей в структурной биологии. К сожалению, даже такая грубая модель, как HP-PFP-2, учитывающая только гидрофобные взаимодействия аминокислотных остатков на двумерной решетке, описывает NP-полную задачу. Она успешно решается только эвристическими методами глобальной оптимизации, например, муравьиным алгоритмом. В статье исследуются способы модификации и распараллеливания муравьиного алгоритма для задачи фолдинга белков. Подробно описана программная реализация параллельного муравьиного алгоритма с использованием программных агентов, на платформе JADE в грид-системах. Обсуждаются результаты вычислительного эксперимента.

The protein folding problem associated with the search of the tertiary structure of the protein at the primary amino acid sequence, is important in structural biology. Unfortunately, even such a crude model as HP-PFP-2, taking 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.The article examines the methods of modification and parallelization of ant colony optimization algorithm for the problem of protein folding. The software implementation of parallel ant colony optimization algorithm on the JADE platform in grid systems described in detail The article discusses the results of computational experiment.

Dastlabki aminokislotali ketma-ketligi bo’yicha oqsil foldingining uchlamchi tuzilishini izlash strukturali bioligiya sohasining asosiy muammosi hisoblanadi. Afsuski, HP-PFP-2 tipdagi qo’pol modellar ham faqat ikki o’lchovli panjarada aminokislota qoldiqlarining gidrofobli ta’siri inobatga olingan, NP murakkab hisoblanadi va faqat evristik usulda global optimallashtirish orqali echimi olinadi. Masalan, chumoli algoritmi yordamida. Maqolada oqsil foldingi masalasi uchun chumoli algoritmini parallel hisoblash va takomillashtirish usullari tadqiq etilgan. Grid tizimi Jade platformasida chumoli algoritmini parallelashtirish dasturiy tatbiqi to’liq tavsiflangan. Hisoblash tajribalardan olingan natijalari muhokama etilgan.

Список использованных источников

  1.  DillK.A. Theory for the folding and stability of globular Proteins / Biochemistry № 24. - 1985. - Pр. 1501-1509.
  2.  Crescenzi P., Goldman D., Papadimitriou C., Piccolboni A., M. Yannakakis. On the complexity of protein folding. J Comp Bio, 5, 1998.
  3.  Shmygelska A. and H.H. Hoos. An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem // Bmc Bioinformatics. - 2005. - № 6(1). - 30 p.
  4.  A.S. Kolaskar and Sangeeta Sawant, Prediction of conformational states of amino acids using Ramachandran plot / International Journal of Peptide and Protein Research. 1996. - № 47. - Pр. 110-116.
  5.  C. Levinthal. How to fold graciously // Mössbaun Spectroscopy in Biological Systems Proceedings. Univ. of Illinois Bulletin. Vol.67. -1969. - № 41. - Pр. 22-24
  6.  Финкельштейн А.В., Птицын О.Б. Физика белка: Курс лекций с цветными и стереоскопическими иллюстрациями и задачами. - М.: КДУ, 2012. - 456 с.
  7.  Макеев А.В. Основы биологии. - М.: Мир, 1997. - 235 с.
  8.  Малышенко А.М. Математические основы теории систем: учебник для вузов. – Томск: Изд-во Томского политехнического университета, 2008. – 364 с.
  9.  Alberts B., Johnson A., Lewis J. Molecular Biology of the Cell. New York Garland Science, 2002. – Режим доступа: https://www.ncbi.nlm.nih.gov/books/NBK26830
  10.  Istrail S, Lam F. Combinatorial algorithms for protein folding in lattice models: a survey of mathematical results. Commun. Inf. Syst., 2009. - № 9(4). - Pр. 303–346.
  11.  Richards F.M. Areas, volumes, packing and protein structure / Annual Review of Biophysics and Bioengineering. - 1977. - Vol.6, № 1. - Pр. 151-176.
  12.  Dill К.А. Dominant forces in protein folding. Biochemistry, 29:7133-7155, 1990.
  13.  Таненбаум Э., М. ван Стеен. Распределенные системы. Принципы и парадигмы. – СПб.: Питер, 2003. – 877с. (Серия «Классика computer science»).
  14.  Бекмуратов Т.Ф., Мухамедиева Д.Т., Базаров Р., Ахмедов Д.Д. Параллельный муравьиный алгоритм оптимизации // Узб. журнал «Проблемы информатики и энергетики». – Ташкент, 2014. - № 1-2. - С.11-15.
  15.  Базаров Р.К. Реализация муравьиного алгоритма фолдинга белков на графических процессорах // Проблемы вычислительной и прикладной математики. - Ташкент, 2017. - № 1. - C. 86-91.
  16.  Карпенко A.П. Параллельные популяционные алгоритмы одно- и многоцелевой оптимизации. Режим доступа: http://agora.guru.ru/abrau2014/pdf/240.pdf
  17.  Bellifemine, Fabio; Poggi, Agostino; Rimassa, Giovanni. JADE: A FIPA-compliant Agent Framework ; In: Proceedings of PAAM’99, London, April 1999. - Pр. 97-108.
  18.  Boese, Joos-Hendrik; Feuerstack, Sebastian. Adaptive User Interfaces for Ubiquitous Access To Agent-based Services; In: Workshop on Human- Agent Interaction, Agentcities ID3; Barcelona, Spain, 2003.
  19.  Cao, J.; Kerbyson, D.J.; Nudd, G.R. Performance Evaluation of an Agent-Based Resource Management Infrastructure for Grid Computing. // Proceedings of 1st IEEE/ACM International Symposium on Cluster Computing and the Grid. -Brisbane, Australia, May 15-18 2001.- Pр. 311-318.
  20.  Senobari M., Drozdowicz M. , Paprzycki M., Kuranowski W., Ganzha M., Olejnik R., Lirkov I. Combining an JADE-agent-based Grid infrastructure with the Globus middleware—Initial Solution. // Proceedings of the CIMCA-IAWITC 2008 Conference, IEEE CS Press, Los Alamitos, CA, 2008. - Pр. 890-895.
  21.  Aversa R., Martino B., Rak M., Venticinque S. Cloud agency: A mobile agent based cloud system // Proc. Int Conf. Complex, Intelligent and Software Intensive Systems, 2010. - Pр. 132-137.
  22.  Cicirelli, F, Furfaro, A, Nigro, L, Pupo, F. Agents Over The Grid: An Experience Using The Globus Toolkit 4. // Proceedings of the 26th European Conference on Modelling and Simulation (ECMS'2012), 2012. - Pр. 78-85.
  23.  Corradini F., Merelli E. Hermes: agent-based middleware for mobile computing. / Lecture Notes in Computer Science, Vol 3465. Springer-Verlag, Berlin/Heidelberg, 2005. - Pр. 234-270.
  24.  S. Ilie and C, Badica, "Effectiveness of Solving Traveling Salesman Problem Using Ant Colony Optimization on Distributed Multi-Agent Middleware," // Proceedings of international Multiconference on Computer Science and Information Technology (IMCSIT), 2010. - Vol.5. - Рp.197-203.
  25.  González P.P.G., Beltrén H.I., Rojo-Domínguez A., Eduardo M., Gutiérrez S. Multi-Agent Systems Applied in the Modeling and Simulation of Biological Problems: A Case Study in Protein Folding. / World Academy of Science, Engineering & Technology. Issue 34. - 2009. - Pр. 128-137.
  26.  Cao, J.; Spooner, D.P.; Jarvis, S.A.; Nudd, G.R. Grid Load Balancing Using Intelligent Agents // Future Generation Computer Systems special issue on Intelligent Grid Environments: Principles and Applications. 21:1. 2005. - Pр. 135-149.
  27.  Cao J., Spooner D.P., Turner J.D., Jarvis S.A., Kerbyson D.J., Saini S., Nudd G.R. Agent-based Resource Management for Grid Computing // 2nd IEEE International Symposium on Cluster Computing and the Grid. - Berlin, Germany, May, 2002. - 350 р.
  28.  Adilova F.T., Ibragimov R.Sh., Bazarov R.K. Agent-based modeling and simulation: application in telemedicine // ICEIC-2008. Proceedings of 9th International Conference on Electronics, Information and Communication. - Tashkent, June 24-27 2008. - PS2-17. 2008. - P. 31.
  29.  Magda: A mobile Agent based Grid Infrastructure [Электронный ресурс ] / University of Neaples. Italy. - Режим доступа: http://parsec.unina2.it/~magda.
  30.  Bellifemine F., Poggi A., Rimassa G. JADE: A FIPA-compliant Agent Framework // Proceedings of PAAM’99, London, April 1999. - Pр. 97-108.
  31.  Globus Toolkit 4.0.7 Download [Электронный ресурс] / University of Chicago. - Режим доступа: http://toolkit.globus.org/toolkit/downloads/4.0.7
  32.  Bellifemine F., Caire G., Greenwood D. Developing Multi-Agent Systems with JADE. Willey, 2007. - 286 p.
  33.  Базаров Р.К. Реализация муравьиного алгоритма для изучения фолдинга белков на плоскости методами программных агентов (Agent-ACOHPPFP-2) // Агентство по интеллектуальной собственности РУз. Свидетельство № DGU-04104. 09.12.2016 г.

Список всех публикаций, цитирующих данную статью