Новий алгоритм імітаційного відпалу для передбачення структури білків

Новий алгоритм імітаційного відпалу для передбачення структури білків

Розглянуто формальну постановку задачі передбачення структури білків, класичні підходи для розв’язання задачі та вперше запропонована модифікація класичних алгоритмів. Рассмотрено формальную постановку задачи предсказания структуры белков, классические подходы для решения задачи и впервые предложена...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Компьютерная математика
Дата:2018
Автор: Чорножук, С.A.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Теми:
Математические модели в биологии и медицине
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/161856
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Новий алгоритм імітаційного відпалу для передбачення структури білків / С.A. Чорножук // Компьютерная математика. — 2018. — № 1. — С. 118-124. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-161856
record_format dspace
spelling Чорножук, С.A.
2019-12-24T21:51:13Z
2019-12-24T21:51:13Z
2018
Новий алгоритм імітаційного відпалу для передбачення структури білків / С.A. Чорножук // Компьютерная математика. — 2018. — № 1. — С. 118-124. — Бібліогр.: 6 назв. — укр.
2616-938Х
https://nasplib.isofts.kiev.ua/handle/123456789/161856
519.8
Розглянуто формальну постановку задачі передбачення структури білків, класичні підходи для розв’язання задачі та вперше запропонована модифікація класичних алгоритмів.
Рассмотрено формальную постановку задачи предсказания структуры белков, классические подходы для решения задачи и впервые предложена модификация классических алгоритмов.
The formal statement of the protein structure prediction problem is considered. The classic approaches are investigated as well as the modification of the classic algorithms is firstly presented.
uk
Інститут кібернетики ім. В.М. Глушкова НАН України
Компьютерная математика
Математические модели в биологии и медицине
Новий алгоритм імітаційного відпалу для передбачення структури білків
Новый алгоритм имитации отжига для предсказания структуры белков
A new algorithm for simulating the annealing for predicting the protein structure
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Новий алгоритм імітаційного відпалу для передбачення структури білків
spellingShingle Новий алгоритм імітаційного відпалу для передбачення структури білків
Чорножук, С.A.
Математические модели в биологии и медицине
title_short Новий алгоритм імітаційного відпалу для передбачення структури білків
title_full Новий алгоритм імітаційного відпалу для передбачення структури білків
title_fullStr Новий алгоритм імітаційного відпалу для передбачення структури білків
title_full_unstemmed Новий алгоритм імітаційного відпалу для передбачення структури білків
title_sort новий алгоритм імітаційного відпалу для передбачення структури білків
author Чорножук, С.A.
author_facet Чорножук, С.A.
topic Математические модели в биологии и медицине
topic_facet Математические модели в биологии и медицине
publishDate 2018
language Ukrainian
container_title Компьютерная математика
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Новый алгоритм имитации отжига для предсказания структуры белков
A new algorithm for simulating the annealing for predicting the protein structure
description Розглянуто формальну постановку задачі передбачення структури білків, класичні підходи для розв’язання задачі та вперше запропонована модифікація класичних алгоритмів. Рассмотрено формальную постановку задачи предсказания структуры белков, классические подходы для решения задачи и впервые предложена модификация классических алгоритмов. The formal statement of the protein structure prediction problem is considered. The classic approaches are investigated as well as the modification of the classic algorithms is firstly presented.
issn 2616-938Х
url https://nasplib.isofts.kiev.ua/handle/123456789/161856
citation_txt Новий алгоритм імітаційного відпалу для передбачення структури білків / С.A. Чорножук // Компьютерная математика. — 2018. — № 1. — С. 118-124. — Бібліогр.: 6 назв. — укр.
work_keys_str_mv AT čornožuksa noviialgoritmímítacíinogovídpaludlâperedbačennâstrukturibílkív
AT čornožuksa novyialgoritmimitaciiotžigadlâpredskazaniâstrukturybelkov
AT čornožuksa anewalgorithmforsimulatingtheannealingforpredictingtheproteinstructure
first_indexed 2025-11-24T11:38:42Z
last_indexed 2025-11-24T11:38:42Z
_version_ 1850845811884163072
fulltext 118 ISSN 2616-938Х. Компьютерная математика. 2018, № 1 Математические модели в биологии и медицине Розглянуто формальну постановку задачі передбачення структури білків, класичні підходи для розв’я- зання задачі та вперше запропоно- вана модифікація класичних алго- ритмів.  С.А. Чорножук, 2018 УДК 519.8 С.A. ЧОРНОЖУК НОВИЙ АЛГОРИТМ ІМІТАЦІЙНОГО ВІДПАЛУ ДЛЯ ПЕРЕДБАЧЕННЯ СТРУКТУРИ БІЛКІВ Вступ. Передбачення структури білків – комп'ютерне моделювання третинної (про- сторової) структури білка, яке базується на його амінокислотній послідовності (первин- ній структурі). Ця задача є однією з най- важливіших проблем у сучасній біоінфор- матиці. Прогрес у розвитку методів для передбачення структури білків оцінюється в рамках всесвітнього експерименту CASP, що проводиться раз у два роки, починаючи з 1994 р. В 1960-х роках американський біо- хімік, Нобелівський лауреат Крістіан Анфін- сен спостулював термодинамічну гіпотезу, згідно з якою атоми в молекулах білка укладаються в природніх умовах у термо- динамічно стабільну конформацію, що відпо- відає мінімуму вільної енергії системи [1]. Іншими словами, білок приймає певну про- сторову форму в результаті обмежень, що диктуються композицією і фізико-хімічними властивостями амінокислот, що його фор- мують. У свою чергу, білкові молекули із подібною просторовою структурою зазвичай відіграють і схожу біологічну роль у проце- сах клітинного рівня. Таким чином, струк- тура білка може розглядатися як перехідна кладка між його хімічним складом (пер- винною структурою) і функцією, наприклад, як проект генетики людини (Human Genome Project). Як зазначено в [2], методи експери- ментального визначення структури білка є технологічно складними, коштовними і силь- но (більш ніж на два порядки) відстають у продуктивності від методів визначення НОВИЙ АЛГОРИТМ ІМІТАЦІЙНОГО ВІДПАЛУ ДЛЯ ПЕРЕДБАЧЕННЯ СТРУКТУРИ БІЛКІВ ISSN 2616-938Х. Компьютерная математика. 2018, № 1 119119 хімічного складу. Видається, що заповнити прогалину між кількістю послідовностей і структур білків можна лише шляхом теоретичного моделювання структури білків. Розв’язання цієї проблеми відкриває широкий шлях до впровадження і вдосконалення різноманітних біотехнологій. У наш час є багато прикладів, коли комп’ютерні моделі білків практично використовуються в біології і меди- цині, зокрема для розробки ліків. Так, знання структури білка може підказати потенційних партнерів для білкової взаємодії і тим самим підштовхнути дослідників до розробки чи вдосконалення нових ензимів чи антитіл або, напри- клад, пояснити фенотипи проведених мутацій чи, альтернативно, допомогти у визначенні місця для проведення мутацій з метою зміни певних фенотипів. Передбачення структури білків – це складна задача з багатьох причин. По- перше, кількість можливих просторових конфігурацій білків є дуже великою. По-друге, фізичні засади структуроутворення білків і їхньої стабільності є ще не до кінця зрозумілими. Всі ці проблеми детально описуються в [3]. Для досягнення успіху в побудові моделі методи з передбачення структури мають реалізовувати певний стратегічний план для ефективного обходу простору можливих структур і вибору найбільш ймовірних кандидатів на нативну структуру. На даний час існують два головні, концептуально різні типи методів для звуження простору пошуку структурних конформацій білків [4]: інформаційні методи, що базуються на знанні, почерпнутому з експериментально визначених структур (knowledge-based methods), та фізичні методи, що ґрунтуються на основних принципах молекулярної динаміки (modeling from the first principles або англ. ab initio modeling). Методи першого типу використовують припущення, що шукана структура білка може бути схожою до однієї або кількох відомих структур білків, чи, принаймні, бути складеною з елементарних конструкційних блоків таких білків. Методи другого типу не використовують інформації з відомих структур, а базуються переважно на спрощених енергетичних потенціалах та викори- стовують для моделювання наближені стратегії пошуку мінімуму енергетичного ландшафту [5]. 1. Математична постановка задачі. Позначимо Z множину цілих чисел. Структурою білка будемо вважати його подання у вигляді маршруту, що включає точки з цілочисловими координатами у тривимірному просторі 3Z . Позначимо , , , ,X P N V F  кортеж, який подає задачу комбінаторної опти- мізації за таких позначень. 1 2 1( , ,..., )NX e e e  , {(1,0,0), ( 1,0,0),(0,1,0), (0, 1,0),(0,0,1), (0,0, 1)};ie     : {0,1}P X  – предикат, який визначає допустимість структури білка; 1 2( , ,..., )Nx x x x , де 1 1i i ix x e   , 2,i N , 1 (0,0,0)x  ; ( ) 0P x  , якщо серед компонент x існують однакові елементи; ( ) 1P x  , якщо у x не існує однакових елементів; 1 2( , ,..., ), {0,1}N iV v v v v  – послідовність значень амінокислот. С.A. ЧОРНОЖУК 120 ISSN 2616-938Х. Компьютерная математика. 2018, № 1 Цільова функція задачі матиме вигляд: ( )F x =   ,  1, 1 , N i j i j i j i j D x x v v      , де     1,  якщо ,  1 ( ,  ) , 0, якщо   ,  1 d x y D x y d x y      , d x y – евклідова відстань у просторі 3.Z Задача полягає у тому щоб знайти такий     ,optx X що   arg min ( ),opt x X x F x   за умови ( ) 1optP x  . Алгоритми розв’язування. У процесі роботи розроблені алгоритми комбінаторної оптимізації на основі методів детермінований локального пошуку та імітаційного відпалу (із класу стохастичного локального пошуку). Крім того, вперше запропоновано алгоритм імітаційного відпалу на основі введення спеціальної фітнес-функції, що значно покращило результати роботи алгоритму при передбаченні структури білків певної розмірності. Перш ніж перейти до деталей алгоритмів, необхідно ввести ще декілька визначень. Нехай   ,      ,x y X  ,hD x y – відстань Геммінга між двома структурами білків,      {  : ,  }r hO x y D x y r  – окіл структури х радіуса  r , F(x) – цільова функція. У подальших алгоритмах використано окіл 2  ( )O x радіусу r = 2. Далі наведено псевдокод реалізованих алгоритмів, починаючи з DLS (рис. 1). Загальна схема алгоритму детермінованого локального пошуку. Варто зазначити, що для генерації чергової точки околу був використаний кільцевий генератор (точки в околі вважаються певним чином упорядкованими й після переходу до нової ітерації продовжується перебір точок, починаючи з наступної відповідно до зазначеного упорядкування [4]). procedure DLS(); xOptimal = деякий припустимий варіант розв'язку; while не вичерпано весь окіл 2  ( )O xOptimal do x: = Генерація Чергової Точки Околу 2  ( )O xOptimal ; if P(x) = 0 then перейти до наступної ітерації циклу; if F(x) < F(xOptimal) then xOptimal = x; endwhile return xOptimal; end РИС. 1. Схема алгоритму детермінованого локального пошуку НОВИЙ АЛГОРИТМ ІМІТАЦІЙНОГО ВІДПАЛУ ДЛЯ ПЕРЕДБАЧЕННЯ СТРУКТУРИ БІЛКІВ ISSN 2616-938Х. Компьютерная математика. 2018, № 1 121121 Метод імітаційного відпалу. Алгоритми стохастичного локального пошуку є одними з поширених метаевристичних методів оптимізації траєкторного типу. Їх обчислювальна схема базується на процедурі локального пошуку, в якій на кож- ній ітерації також досліджується окіл поточного розв’язку, але головною особ- ливістю є те, що при переході до наступної ітерації з певною ймовірністю може прийматися розв’язок, який погіршує значення цільової функції, причому не обо- в’язково з поточного околу. Термін стохастичний відображає ту обставину, що обчислювальна схема базується на використанні рандомізованих процедур (рис. 2). Тут   – параметр, що характеризує швидкість спадання температури, [0,1]random – генератор випадкових чисел на проміжку [0,1] з рівномірним роз- поділом. Як критерій завершення для імітаційного відпалу була вибрана умова 0.5.T  У свою чергу для визначення рівноваги при заданій температурі використано такий підхід: для кожних нових 400 значень цільової функції раху- валося середнє. Якщо з точністю до 0.0001 таке значення вже зустрічалося, то наставала температурна рівновага, після чого змінювалася поточна температура. Значення λ було рівним 0.9999. procedure SA(); xOptimal = деякий припустимий варіант розв'язку; T:= <початкова температура>; x= xOptimal; while не виконується умова завершення do while не досягнута рівновага do y:= Генерація Чергової Точки Околу 2  ( )O x ; if P(y) = 0 then перейти до наступної ітерації циклу; p: =    [ ]/  }min{1,  F y F x Te  ; tr: = [0,1]random ; if p >= tr then if F(y) < F(xOptimal) then xOptimal := y; x:= y; endif endwhile   : λT T ; endwhile return xOptimal; end РИС. 2. Схема алгоритму імітаційного відпалу Необхідно зауважити, що параметри для алгоритму імітаційного відпалу потребували тонкого налаштування та були встановлені емпірично. С.A. ЧОРНОЖУК 122 ISSN 2616-938Х. Компьютерная математика. 2018, № 1 Пропонований алгоритм імітаційного відпалу. Перш, ніж перейти до де- талей, варто описати мотивацію покращення алгоритму. Незважаючи на те, що з налаштованими параметрами (значення яких подано вище) алгоритм імітаційного відпалу демонстрував (як і в інших задачах комбінаторної оптимізації) значно кращі результати, ніж детермінований локальний пошук, все ж таки була поміченою тенденція до поганого «згортання» білків, деякі гідрофобні амінокислоти яких суттєво віддалялися від інших гідрофобних амінокислот (наприклад, …011010100000001). Внаслідок цього, запропоновано ввести в обчислювальну схему алгоритма допоміжну фітнес-функцію, яка визначалася наступним чином:   1, 1 2, 2 , 3 1 ( , )(max{ }, ( , ),..., ( , )i i i N i Nx v x v x vFit x G G G      – 1, 1 2, 2 ,( , ), (mi , ),..., (n{ , )} 1),i i N i Nx v x vG vG G x    де , якщо 1, ( , ) ,якщо 1, G x y x y y     , якщо 1, ( , ) ,якщо 1, G x y x y y     ,i jx – j -а координата i -го елементу ,x .x X Це дало змогу певним чином зменшити вплив цільової функції на ранніх етапах, коли він не сприяє прагненню гідрофобних часток бути ближчими один до одної, що, в свою чергу, покращило роботу алгоритму для певних розмір- ностей коду білка (рис. 3). procedure SA(); xOptimal = деякий припустимий варіант розв'язку; T:= < початкова температура >; x= xOptimal; while не виконується умова завершення do while не досягнута рівновага do y:= Генерація Чергової Точки Околу 2  ( )O x ; if P(y) = 0 then перейти до наступної ітерації циклу; p: =         min{1,  } / F y F x Te Fit y Fit x   ; tr: = [0,1]random ; if p ≥ tr then if F(y) < F(xOptimal) then xOptimal := y; x:= y; endif endwhile T:= λT; endwhile return xOptimal; end РИС. 3. Схема алгоритму імітаційного відпалу із фітнес-функцією НОВИЙ АЛГОРИТМ ІМІТАЦІЙНОГО ВІДПАЛУ ДЛЯ ПЕРЕДБАЧЕННЯ СТРУКТУРИ БІЛКІВ ISSN 2616-938Х. Компьютерная математика. 2018, № 1 123123 Решта умов та параметрів, окрім фітнес-функції, співпадають із описаними у попередньому алгоритмі. Результати та висновки. Розроблені алгоритми тестувалися на 10 реальних значеннях білків довжиною 48, які взяті із відомої бібліотеки [6]. Результати обчислювального експерименту подані в таблиці, де   ( )optF x – результуюче зна- чення цільової функції у точці розв'язку   ,optx X знайденої відповідним алгоритмом. ТАБЛИЦЯ. Значення цільової функції Код білка Детерміно- ваний локальний пошук Стандартний алгоритм імітаційного відпалу Алгоритм імітаційного відпалу із фітнес-функцією 101100111101110011001011 010110011000100000000110 –20 –26 –28 111101101111100100110010 000001001000100110011101 –18 –30 –31 010110111111001010010110 101000100110011001010010 –21 –31 –31 010110010111001101100011 111001011010100001001010 –18 –29 –30 001000101111001111011011 100101010010000001101101 –20 –28 –31 111000110101101101101000 000010100100010011111101 –21 –30 –30 010000101110101111011011 000101000111001100110001 –22 –27 –28 011011101111001110000001 011001101000110101011000 –17 –28 –29 010100001010100101111110 011101001011001011100001 –22 –30 –31 011000000110001110100101 100100100110011111110011 –21 –26 –31 Підхід до розробки алгоритмів імітаційного відпалу для передбачення третинної структури білків на основі використання спеціальної фітнес-функції виглядає перспективним напрямом підвищення їх ефективності. Розроблений алгоритм спромігся знайти покращене значення цільової функції на всіх реальних даних середньої довжини (48). Проте цей підхід потребує і подальших досліджень, адже у ході експерименту також було відмічено і деякі проблеми. С.A. ЧОРНОЖУК 124 ISSN 2616-938Х. Компьютерная математика. 2018, № 1 1. На більш довгих послідовностях амінокислот запропонований алгоритм імітаційного відпалу не завжди давав кращі результати, ніж реалізований за звичайною обчислювальною схемою, адже описана фітнес-функція погано масштабується. 2. Для масштабованих фітнес-функцій швидкодія алгоритму знижується. Отже, доречно продовжити вивчення запропонованого підходу для пошуку більшого ступеню масштабованості фітнес-функції, який дозволив би за прий- нятних втрат швидкодії досягати підвищення точності розроблюваних алгорит- мів передбачення третинної структури білків. С.А. Черножук НОВЫЙ АЛГОРИТМ ИМИТАЦИИ ОТЖИГА ДЛЯ ПРЕДСКАЗАНИЯ СТРУКТУРЫ БЕЛКОВ Рассмотрено формальную постановку задачи предсказания структуры белков, классические подходы для решения задачи и впервые предложена модификация классических алгоритмов. S.A. Chornozhuk A NEW ALGORITHM FOR SIMULATING THE ANNEALING FOR PREDICTING THE PROTEIN STRUCTURE The formal statement of the protein structure prediction problem is considered. The classic approaches are investigated as well as the modification of the classic algorithms is firstly presented. Список літератури 1. Simoni K.N., Hill R.D., Hill R.L. The thermodynamic hypothesis of protein folding: the work of Christian Anfinsen. Journal of Biological Chemistry. 2006. 281.14: e11-e11. 2. Gueorguiev V., Kuttel M. Implementation, Validation and Profiling of a Genetic Algorithm for Molecular Conformational Optimization. Proceedings of the Annual Conference of the South African Institute of Computer Scientists and Information Technologists. ACM, 2016. 16 p. 3. Lipinski-Paes T.A. Multiagent Ab Initio Protein Structure Prediction Tool for Novices and Experts. International Symposium on Bioinformatics Research and Applications. Cham: Springer, 2016. P. 163 – 174. 4. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. К.: Видавничо-поліграфічний центр “Київський університет”, 2016. 142 c. 5. Hulianytskyi L.F., Rudyk V.O. Protein structure prediction problem: formalization using quaternions. Cybernetics and Systems Analysis. 2013. 49, N 4. P. 597 – 602. 6. 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. P. 325 – 329. Одержано 07.05.2018 Про автора: Чорножук Сергій Анатолійович, аспірант Інституту кібернетики імені В.М. Глушкова НАН України.

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