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

Bazarov  D K; Bazarov  R K; Bekmuratov T F

557

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

Журнал номиHisoblash va amaliy matematika muammolari
Нашр номи№2(8) 2017
Кўришлар сони 557

Internet ҳавола

DOI

UzSCI тизимида яратилган сана 20-12-2019

Ўқишлар сони 534

Нашр санаси 18-04-2017

Мақола тилиRus

Саҳифалар сони103 -113

Калит сўзлар

фолдинг белков

алгоритм оптимизации муравьиной колонии

агентские системы

Русский

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

Калит сўзлар

фолдинг белков

алгоритм оптимизации муравьиной колонии

агентские системы

English

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.

Калит сўзлар

the ant colony optimization algorithm

protein folding problem

agent systems

Ўзбек

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.

Калит сўзлар

oqsil foldingi

chumolilar koloniyasini optimallashtirish algoritmi

agent tizimlari

№ Муаллифнинг исми Лавозими Ташкилот номи

1 Bazarov D.K. младший научный сотрудник Toshkent axborot texnologiyalari universiteti

2 Bazarov R.K. младший научный сотрудник Toshkent axborot texnologiyalari universiteti

3 Bekmuratov T.F. главный научный сотрудник Toshkent axborot texnologiyalari universiteti

№ Ҳавола номи

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

Кутилмоқда

№	Муаллифнинг исми	Лавозими	Ташкилот номи
1	Bazarov D.K.	младший научный сотрудник	Toshkent axborot texnologiyalari universiteti
2	Bazarov R.K.	младший научный сотрудник	Toshkent axborot texnologiyalari universiteti
3	Bekmuratov T.F.	главный научный сотрудник	Toshkent axborot texnologiyalari universiteti

№	Ҳавола номи
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 г.