Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов

Рассматривается гидрофобно-полярная модель сворачивания протеина, предлагается и исследуется алгоритм прогнозирования третичной структуры белка, построенный на базе метода ОМК. Строится модель молекулы протеинов в трехмерной треугольной решетке. Разработаны методы априорной оценки позиции в решетке...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/85018
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов / В.А. Рудык // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 66-72. — Бібліогр.: 7 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85018
record_format	dspace
spelling	irk-123456789-850182015-07-19T03:02:11Z Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов Рассматривается гидрофобно-полярная модель сворачивания протеина, предлагается и исследуется алгоритм прогнозирования третичной структуры белка, построенный на базе метода ОМК. Строится модель молекулы протеинов в трехмерной треугольной решетке. Разработаны методы априорной оценки позиции в решетке и обновления матрицы феромонных путей, их эффективность подтверждена вычислительным экспериментом. Розглядається гідрофобно-полярна модель згортання протеїну, пропонується та досліджується алгоритм прогнозування третинної структури білка, розроблений на базі методу ОМК. Будується модель молекули протеїну в тривимірній трикутній решітці. Запропоновані методи апріорної оцінки позиції в решітці та поновлення матриці феромонних шляхів, їх ефективність підтверджена обчислювальним експериментом. The Hydrophobic-Hydrophilic protein folding model is examined, the algorithm based on ACO optimization method is proposed and analyzed for protein tertiary structure prediction. The molecule model is considered to be a chain whose monomers are placed on the vertices of 3D triangular lattice. The a priori position estimation method and pheromone trails updating method are deviced, computational experiment confirms their appropriateness. 2012 Article Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов / В.А. Рудык // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 66-72. — Бібліогр.: 7 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85018 519.21 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается гидрофобно-полярная модель сворачивания протеина, предлагается и исследуется алгоритм прогнозирования третичной структуры белка, построенный на базе метода ОМК. Строится модель молекулы протеинов в трехмерной треугольной решетке. Разработаны методы априорной оценки позиции в решетке и обновления матрицы феромонных путей, их эффективность подтверждена вычислительным экспериментом.
format	Article
title	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов
spellingShingle	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов Теорія оптимальних рішень
title_short	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов
title_full	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов
title_fullStr	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов
title_full_unstemmed	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов
title_sort	анализ эффективности алгоритмов омк для решения задачи о сворачивании протеинов
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
url	http://dspace.nbuv.gov.ua/handle/123456789/85018
citation_txt	Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов / В.А. Рудык // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 66-72. — Бібліогр.: 7 назв. — рос.
series	Теорія оптимальних рішень
first_indexed	2025-07-06T12:10:38Z
last_indexed	2025-07-06T12:10:38Z
_version_	1836899466861346816
fulltext	66 Теорія оптимальних рішень. 2012 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается гидрофобно-по- лярная модель сворачивания про- теина, предлагается и иссле- дуется алгоритм прогнозирования третичной структуры белка, построенный на базе метода ОМК. Строится модель молекулы протеинов в трехмерной треу- гольной решетке. Разработаны методы априорной оценки позиции в решетке и обновления матрицы феромонных путей, их эффектив- ность подтверждена вычисли- тельным экспериментом.  В.А. Рудык, 2012 ÓÄÊ 519.21 Â.À. ÐÓÄÛÊ ÀÍÀËÈÇ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÀËÃÎÐÈÒÌÎÂ ÎÌÊ ÄËß ÐÅØÅÍÈß ÇÀÄÀ×È Î ÑÂÎÐÀ×ÈÂÀÍÈÈ ÏÐÎÒÅÈÍÎÂ Введение. В современном мире в разных отраслях науки с открытием неизвестных ранее объектов возрастает необходимость разработки новых методов для их изучения. Важным становится обмен информации ме- жду различными науками для применения идей из одной сферы в другой. Так, напри- мер, в прикладной математике оказалось эффективным использование генетических алгоритмов и искусственных нейронных се- тей, которые имитируют процесс эволюции и процессы, протекающие в мозге, соответ- ственно. В то же время в биологии для по- нимания различных механизмов и процессов часто недостаточно исключительно экспе- риментальных данных. Это привело к появ- лению различных междисциплинарных ис- следований на стыке прикладной математи- ки, информатики, биологии и химии, таких как биоинформатика, математическая био- логия, вычислительная биология, биокибер- нетика, структурная геномика, биоинжене- рия. В настоящее время эти области являют- ся одними из наиболее перспективных и развивающихся. Среди открытых задач вычислительной биологии – определение третичной структу- ры протеина [1,2]. Разнообразие белковых молекул делает невозможным решение про- блемы путем проведения экспериментов, но построив на основе наблюдений математи- ческую модель сворачивания молекулы можно спрогнозировать ее форму. Ниже ис- пользуется одна из таких моделей – дис- кретная НР-модель Дилла [1]. АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ОМК ДЛЯ РЕШЕНЯ ЗАДАЧИ О СВОРАЧИВАНИИ… Теорія оптимальних рішень. 2012 67 1. Прогнозирование структуры протеина как задача комбинаторной оптимизации. Исходными данными для определения третичной структуры бел- ка – формы, которую принимает молекула в трехмерном пространстве – являет- ся его первичная структура, которая представляет собой линейную последова- тельность аминокислот. Одна из важных характеристик аминокислотных остат- ков – гидрофобность – выражает, насколько он предпочитает неполярное окру- жение (например, этанол в качестве растворителя или внутренность белка) по- лярному (например, воде). В зависимости от этой характеристики все аминокис- лоты делятся на два класса – гидрофобные и полярные (или гидрофильные). По- падая в воду белок, являя собой цепочку аминокислот, принимает ту форму, в которой площадь поверхности контакта воды с полярными аминокислотами максимизируется, а с гидрофобными минимизируется. Поскольку в результате взаимодействия образуется шарообразная структура, такие белки называют гло- булярными. Дискретной моделью формы молекулы протеина является путь без самопе- ресечений в некоторой дискретной решетке. В исследованиях чаще всего встре- чаются двумерная квадратная [2], треугольная [3] и трехмерная кубическая [2, 4] решетки, рассматриваются и другие виды решеток, а также дискретных нереше- точных структур [3,5]. Соседние в цепочке аминокислотные остатки располага- ются в соседних узлах решетки, таким образом соблюдается условие неразрыв- ности молекулы. Между гидрофобными остатками, которые располагаются в соседних узлах решетки, но не являются соседями в цепочке, образуются гидро- фобные связи. В модели Дилла в качестве значения свободной энергии структу- ры принято считать количество таких связей в ней со знаком минус. Соответст- вуя законам термодинамики, молекула образует структуру с минимальной сво- бодной энергией. Это дает возможность формализовать проблему как задачу комбинаторной оптимизации. Для представления пути в дискретной решетке можно использовать один из трех методов: последовательность координат узлов аминокислотных остатков, абсолютное и относительное кодирование [6]. Мы будем рассматривать послед- ние два представления, поскольку первое требует постоянных проверок нераз- рывности молекулы, а второе и третье обеспечивают связность автоматически. 2. Метод оптимизации муравьиными колониями (ОМК). Исследование дискретных моделей естественных процессов часто приводит к NP-сложным задачам; на практике это значит, что в общем случае найти решение за допусти- мое (полиномиальное) время невозможно (согласно гипотезе о том, что классы P и NP не равны). Одной из таких задач является сформулированная выше на ос- нове НР-модели задача комбинаторной оптимизации. Парадокс заключается в том, что прообразы в природе таких моделей часто решают ту же задачу практи- чески мгновенно – некоторые белки сворачиваются за миллионную долю секун- ды. Этот факт побуждает исследователей строить цепочку решения задачи по аналогии с некоторыми естесственными процессами. Кроме уже упомянутых генетических алгоритмов и нейронных сетей к алгоритмам, имеющим аналоги в В.А. РУДЫК 68 Теорія оптимальних рішень. 2012 природе, относятся метод имитации отжига, иммунные алгоритмы, алгоритм ОМК. Рассмотрим последний подробнее. В поисках пищи муравьи постоянно решают оптимизационную задачу – по- иск кратчайшего пути от муравейника до еды. Для этого они используют феро- моны, помечая ими свой путь. Выбирая направление движения, муравей ориен- тируется на феромонную дорожку, и чем она сильнее, тем вероятнее, что мура- вей последует по ней. В конечном итоге в большинстве случаев все рабочие му- равьи движутся по одному субоптимальному пути от муравейника до еды и об- ратно. В контексте задачи комбинаторной оптимизации это сводится к популя- ционному алгоритму, на каждой итерации которого все элементы популяции – агенты – пошагово строят решения задачи. Информация об оптимальности зна- чения целевой функции на этих решениях записывается в феромонную матрицу, которую учитывают агенты на следующей итерации. Алгоритмы метода ОМК целесообразно применять для поиска приближен- ных решений NP-сложных задач, в том числе и задачи о сворачивании протеина. Так, в [2] с его помощью строится структура молекулы в квадратной и кубиче- ской решетке, предложена процедура локального поиска для повышения показа- телей эффективности алгоритма. В [4] описано решение, использующее двухша- говое обновление феромонных путей на каждой итерации, рассматривается трехмерная кубическая решетка. Ниже предложен алгоритм для решения задачи в трехмерной кубической решетке. Разработан отличный от ранее описанных подход к обновлению феро- монной матрицы и подсчета априорных оценок. 3. Описание алгоритма. На вход задачи подается первичная структура про- теина, которая в терминах изложенной модели принимает вид 1 2... No o o , { , }io H P∈ , 1,i N= , где N обозначает количество аминокислот в молекуле, а H и P – гидрофобный и полярный остаток в цепочке соответственно. Для иссле- дования предлагается использовать трехмерную треугольную решетку [6]. У каждого узла такой решетки 12 соседей. В разработанном алгоритме можно применять как абсолютную, так и относительную кодировку. Закодированное решение имеет вид последовательности векторов 1 2 1... Nr r r − , ir A∈ , 1, 1i N= − , где A – множество значений элементов кода [6], зависящее от вида решетки и типа кодировки. Без ограничения общности можно рассматривать только коди- ровки −= 2 3 1... Nv r r r (без первого элемента), поскольку 1r определяет поворот структуры, а форма молекулы задается путем в решетке с точностью до поворо- та. Количество элементов множества A обозначим символом n , а сами элемен- ты – 1 2, ,..., ndir dir dir (от слова «direction» – направление). Обозначим феромонную матрицу символом Φ – в нашей формулировке за- дачи она будет иметь размер ( 2)n N× − . Схема алгоритма ОМК, разработанного и исследованного для нашей задачи, приведена на рис.1. В нем параметр PN за- дает размер популяции, а LSN – количество элементов, для которых использует- АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ОМК ДЛЯ РЕШЕНЯ ЗАДАЧИ О СВОРАЧИВАНИИ… Теорія оптимальних рішень. 2012 69 ся локальный поиск. Первый шаг – ИнициализироватьФеромоннуюМатрицу( Φ ) – инициализация матрицы случайными значениями в диапазоне от 0 до 1. procedure ACO() fold : ;= rec null ИнициализироватьФеромоннуюМатрицу( Φ ); while (not УсловиеЗавершения()) do for i = 1,…, PN do fold i :=ДопустимоеРешение( Φ ); end for; Отсортировать( fold i ); for i = 1,…, LSN do fold i :=Локальный поиск( fold i ); end for; fold rec :=ОптимальноеЗначение( fold rec , 1fold ,…, fold LSN ); ИспаритьФеромоннуюМатрицу( Φ ); for i = 1,…, PN do ОбновитьФеромоннуюМатрицу( Φ , fold i ); end for end while; return fold rec ; end procedure. Рис. 1. Схема алгоритма ОМК для задачи определения структуры протеина Процедура ДопустимоеРешение( Φ ), используя феромонную матрицу строит путь без самопересечений, пошагово добавляя к кодировке элементы с вероят- ностью: 2 3 1 2 3 1 1 [j,i-1] Est( ... , ) ( ) [j,i-1] Est( ... , ) − − = Φ = = Φ∑ i j i j n i j j r r r dir P r dir r r r dir α β α β , где α и β – параметры алгоритма, а 2 3 1Est( ... , )i jr r r dir− – априорная оценка. Для ее вычисления предполагается, что следующая аминокислота располагается по направлению jdir и подсчитывается количество гидрофобных ( Hn ) и полярных ( Pn ) остатков в соседних с ней узлах. Чтобы образовывались новые связи, гид- рофобные остатки целесообразно располагать рядом с гидрофобными или со свободными узлами (есть шанс заполнить их гидрофобными остатками при дальнейшем построении молекулы), а полярные не ставить рядом с гидрофоб- ными (оставляя место для возможных новых соединений). Такая интерпретация В.А. РУДЫК 70 Теорія оптимальних рішень. 2012 аналогична естественному поведению молекулы: полярные остатки стремятся к соседству с полярным окружением – водой или другими полярными остатками. Введем параметры 00 HP H HHest est est≤ < < , 0 1HP H HHest est est+ + = , 00 PH P PPest est est≤ < ≤ , 0 1PH P PPest est est+ + = , и определим оценку 2 3 1Est( ... , )i jr r r dir− следующим образом: + − + + + − − = =  + + − − = 0 1 2 3 1 0 1 * * ( ) * , , Est( ... , ) * * ( ) * , . P HP H HH P H H i i j P PP H PH P H P i n est n est n n n est o H r r r dir n est n est n n n est o P Приведенная оценка является обобщением известных ранее – в литературе часто встречается комбинация 0 1/ 3PH P PPest est est= = = , 0 0H HPest est= = , 1HHest = . Ниже для вычислительного эксперимента были выбраны значения 0.2PHest = , 0 0.4P PPest est= = , 0.15HPest = , 0 0.25Hest = , 0.6HHest = . Чтобы новые данные учитывались как более актуальными, используется процедура ИспаритьФеромоннуюМатрицу( Φ ), в которой каждый элемент мат- рицы умножается на параметр 0 1≤ ≤ρ , задающий степень испарения феромо- нов. Процедура ОбновитьФеромоннуюМатрицу( Φ , v ) в ее часто встречающей- ся реализации добавляет к каждому элементу, который соответствует направле- нию, содержащемся в структуре 2 3 1... −= N v r r r , значение, пропорциональное энергии v : 1 1[ , ] [ , ] ( ( )) , 1, 2,+ +Φ = Φ + − = − i i k i k i E v i N γ где i k определяется условием = ik i dir r , а 0>γ – параметр алгоритма. С учетом особенностей задачи предлагается альтернативный вариант об- новления феромонной матрицы. Его идея состоит в том, чтобы усиливать только те феромонные дорожки, которые влияют на энергию заданной молекулы. Для этого используется следующая процедура: введем массив φ длиной 2−N и заполним его нулями. Пусть l , m – номера остатков, образующих гидрофобную связь, <l m . В образовании этой связи принимают участие элементы 1 1, ,...,+ −l l m r r r . Подкорректируем массив φ для этой связи так: [ ] [ ] 1, max{1, 1},i i i l mφ φ= + = − и повторим эту операцию для всех гидрофобных связей в структуре 2 3 1... −= N v r r r , после чего обновим феромонную матрицу: 1 1[ , ] [ , ] [ ] , 1, 2+ +Φ = Φ + = − i i k i k i i i N γφ . Такая схема позволяет более точно учитывать приемлемость той или иной части структуры молекулы. 4. Вычислительный эксперимент. Для сравнения и проверки эффективно- сти разработанных алгоритмов был проведен вычислительный эксперимент. Из базы данных протеинов с известной структурой [7] было выбрано 11 примеров АНАЛИЗ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ ОМК ДЛЯ РЕШЕНЯ ЗАДАЧИ О СВОРАЧИВАНИИ… Теорія оптимальних рішень. 2012 71 размерностью от 52 до 302 аминокислот. Рассматривалось 8 вариантов алгорит- ма – с абсолютным и относительным кодированием структуры, без априорных оценок и с использованием вышеизложенного метода для их подсчета, с каждым из двух описанных способов обновления феромонной матрицы. Локальный по- иск не применялся. Учитывая стохастичность алгоритма, для каждой задачи бы- ло выполнено три рестарта. Предложенные модификации алгоритма доказали свою целесообразность как в случае с абсолютной кодировкой, так и с относи- тельной. Сравнительные результаты работы четырех вариантов алгоритма на базе относительной кодировки показаны на рис. 2. Рис. 2. Результаты вычислительного эксперимента На диаграмме модификации а и б не используют априорных оценок на этапе построения структуры, в отличие от в и г. Модификации б и г обновляют феро- монную матрицу первым из вышеописанных способов, а и в – вторым. По оси Х отложено количество аминокислот в исследуемой молекуле, по оси Y – усред- ненная (по трем запускам алгоритма) энергия оптимальной свертки, которая яв- ляется целевой функцией задачи. Выводы. Экспериментальные исследования подтверждают, что использо- вание априорных оценок и обновление феромонной матрицы по частям сущест- венно улучшают эффективность алгоритма метода ОМК по сравнению с вариан- тами без использования этих процедур. Открытыми остаются вопросы эффек- тивной настройки параметров алгоритма и схема внедрения процедуры локаль- ного поиска для нахождения более оптимальных решений. В.О. Рудик В.А. РУДЫК 72 Теорія оптимальних рішень. 2012 АНАЛІЗ ЕФЕКТИВНОСТІ АЛГОРИТМІВ ОМК ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО ЗГОРТАННЯ ПРОТЕЇНУ Розглядається гідрофобно-полярна модель згортання протеїну, пропонується та досліджується алгоритм прогнозування третинної структури білка, розроблений на базі методу ОМК. Будується модель молекули протеїну в тривимірній трикутній решітці. Запропоновані методи апріорної оцінки позиції в решітці та поновлення матриці феромонних шляхів, їх ефективність підтверджена обчислювальним експериментом. V.O. Rudyk ANT COLONY OPTIMIZATION ALGORITHMS FOR PROTEIN FOLDING PROBLEM ANALYSIS The Hydrophobic-Hydrophilic protein folding model is examined, the algorithm based on ACO optimization method is proposed and analyzed for protein tertiary structure prediction. The mole- cule model is considered to be a chain whose monomers are placed on the vertices of 3D triangular lattice. The a priori position estimation method and pheromone trails updating method are deviced, computational experiment confirms their appropriateness. 1. Dill K., Bromberg S., Yue K., Fiebig K., Yee D., Thomas P., Chan H. Principles of protein folding – a perspective from simple exact models // Protein Science..– 1995. – N 4. – P.561–602. 2. Shmygelska A, Hoos H. An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem // BMC Bioinformatics. – 2005. – N 6(30). – Р.30–52. 3. Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model / Agarwala R., Batzoglou S., Dancik V et al. // J. of Computational Biology. – 1997. – N 4. – P. 275–296. 4. Fidanova S., Lirkov I. Ant Colony System Approach for Protein Folding // Int. Conf. Multiconference on Computer Science and Information Technology. – 2008. – P.887–891. 5. Hart W., Istrail S. Lattice and Off-Lattice Side Chain Models of Protein Folding: Linear Time Structure Prediction Better Than 86% of Optimal // J. of Computational Biology.– 1997. – N 4. – P.241-259. 6. Рудык В. Представление структуры белка в трехмерных дискретных решетках произ- вольного типа // Теорія оптимальних рішень. − 2011. – №10. – С. 38–47. 7. Information Portal to Biological Macromolecular Structures: http://www.rcsb.org/ Получено 03.04.2012

Анализ эффективности алгоритмов ОМК для решения задачи о сворачивании протеинов

Репозитарії

Схожі ресурси