Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків
Запропоновано новий гібридний алгоритм, який дозволяє автоматично налаштовувати параметри алгоритму оптимізації мурашиними колоніями для розв'язування задачі передбачення третинної структури білка....
Gespeichert in:
| Datum: | 2019 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Schriftenreihe: | Теорія оптимальних рішень |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/161677 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків / Л.Ф. Гульницький, С.A. Чорножук // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 73-80. — Бібліогр.: 9 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-161677 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1616772019-12-19T01:25:10Z Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків Гульницький, Л.Ф. Чорножук, С.A. Запропоновано новий гібридний алгоритм, який дозволяє автоматично налаштовувати параметри алгоритму оптимізації мурашиними колоніями для розв'язування задачі передбачення третинної структури білка. Предложен новый гибридный алгоритм, который позволяет автоматически настраивать параметры алгоритма оптимизации муравьиными колониями для решения задачи предсказания структуры белка. A new hybrid algorithm is proposed, which allows to automatically adjust the parameters of ant colony optimization algorithm for solving protein structure prediction problem. 2019 Article Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків / Л.Ф. Гульницький, С.A. Чорножук // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 73-80. — Бібліогр.: 9 назв. — укр. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/161677 519.8 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Запропоновано новий гібридний алгоритм, який дозволяє автоматично налаштовувати параметри алгоритму оптимізації мурашиними колоніями для розв'язування задачі передбачення третинної структури білка. |
| format |
Article |
| author |
Гульницький, Л.Ф. Чорножук, С.A. |
| spellingShingle |
Гульницький, Л.Ф. Чорножук, С.A. Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків Теорія оптимальних рішень |
| author_facet |
Гульницький, Л.Ф. Чорножук, С.A. |
| author_sort |
Гульницький, Л.Ф. |
| title |
Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків |
| title_short |
Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків |
| title_full |
Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків |
| title_fullStr |
Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків |
| title_full_unstemmed |
Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків |
| title_sort |
гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/161677 |
| citation_txt |
Гібридний алгоритм оптимізації мурашиними колоніями для передбачення структури білків / Л.Ф. Гульницький, С.A. Чорножук // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 73-80. — Бібліогр.: 9 назв. — укр. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT gulʹnicʹkijlf gíbridnijalgoritmoptimízacíímurašinimikoloníâmidlâperedbačennâstrukturibílkív AT čornožuksa gíbridnijalgoritmoptimízacíímurašinimikoloníâmidlâperedbačennâstrukturibílkív |
| first_indexed |
2025-07-14T14:16:02Z |
| last_indexed |
2025-07-14T14:16:02Z |
| _version_ |
1837632127143772160 |
| fulltext |
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 73
ТЕОРIЯ
ОПТИМАЛЬНИХ
РIШЕНЬ
Запропоновано новий гібридний ал-
горитм, який дозволяє автома-
тично налаштовувати параме-
три алгоритму оптимізації мура-
шиними колоніями для розв'я-
зування задачі передбачення тре-
тинної структури білка.
Л.Ф. Гуляницький,
С.А. Чорножук, 2019
УДК 519.8
Л.Ф. ГУЛЯНИЦЬКИЙ, С.A.ЧОРНОЖУК
ГІБРИДНИЙ АЛГОРИТМ ОПТИМІЗАЦІЇ
МУРАШИНИМИ КОЛОНІЯМИ
ДЛЯ ПЕРЕДБАЧЕННЯ СТРУКТУРИ
БІЛКІВ
Вступ. Визначення просторової структури
білків є необхідним етапом для встановлення
взаємозв'язку між просторовою (третинною)
структурою та функцією білків. Відома
третинна структура білку дозволяє визначити
необхідне лікування важких хвороб генетич-
ного плану для конкретного індивідууму.
В 1960-х роках американський біохімік,
Нобелівський лауреат Крістіан Анфінсен
спостулював термодинамічну гіпотезу, згід-
но з якою атоми в молекулах білка уклада-
ються в природніх умовах у термодинамічно
стабільну конформацію, що відповідає
мінімуму вільної енергії системи [1]. Це
дозволяє розробляти математичні моделі для
передбачення просторової структури білків,
однією із найпоширеніших серед яких є
модель Ділла [2]. Знаходження оптимальної
третинної структури білка – задача із класу
NP, що обмежує можливість застосування
точних методів. На сьогодні в комбінаторній
оптимізації існує ряд підходів, що дозволя-
ють знаходити наближені до точних розв’яз-
ки за відносно високої швидкодії. Одним із
них є алгоритм оптимізації мурашиними
колоніями (ОМК), вперше запропонований
Марко Доріго [3, 4]. Але такі алгоритми
потребують тонкого налаштування значень
параметрів, що саме по собі є складною зада-
чею. В статті запропоновано гібридний
алгоритм, який дозволяє автоматично нала-
штовувати параметри алгоритму ОМК для
конкретної послідовності амінокислот.
https://uk.wikipedia.org/wiki/%D0%9A%D1%80%D1%96%D1%81%D1%82%D1%96%D0%B0%D0%BD_%D0%90%D0%BD%D1%84%D1%96%D0%BD%D1%81%D0%B5%D0%BD
Л.Ф. ГУЛЯНИЦЬКИЙ, С.A. ЧОРНОЖУК
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 74
1. Про математичну постановку задачі. Маємо , , , ,X P N V F кортеж,
який відображає ключові аспекти задачі комбінаторної оптимізації, що подає
проблему передбачення структури білка. Тут X область допустимих значень
структур, що подаються у вигляді маршрутів (ламаних без самоперетинів)
у заданій ґратці [5]; P предикат, що визначає допустимість маршруту; V та N –
послідовність амінокислот, що визначає білок, та її розмірність відповідно;
F цільова функція, яку потрібно мінімізувати.
Усі формальні означення компонент кортежу , , , ,X P N V F описані в [5].
Більш детальне обговорення питань формалізації подано в [6].
2. Пропонований алгоритм розв'язування. У процесі роботи розроблено
гібридний алгоритм, що поєднує у собі алгоритм детермінованого локального
пошуку та ОМК [7].
Для подальшого опису алгоритму необхідно ввести декілька позначень.
Нехай 1 2( , ,..., )nPars Pars Pars Pars деяка множина можливих наборів па-
раметрів ОМК, де iPars певний конкретний набір параметрів ОМК.
Для значень кожного параметру , 1,ip Pars i N введемо дискретну
ґратку можливих значень ( , , , ) ( , , 2 ,..., ),p p p p p p p p p pp s n s s s s n
де ps початкове значення параметра .p Нехай маємо певні два значення
1 2,p p
з ґратки ( , , , ).p p pp s n Тоді 2 1
( , , , ) 1 2
| |
( , )
p p pp s n
p p
D p p
відстань між двома
конкретними значеннями в ґратці ( , , , ).p p pp s n
Нехай у нас є фіксована кількість параметрів ОМК .parN Покладемо
1 2 ( , , , ) 1 2 1 1 2 2
1
( , ) ( , ), ,
par
i pi pi pi
N
p s n i i i i
i
par par D p p p par p par
,
де 1 2,par par Pars відстань між двома наборами параметрів ОМК 1 2,par par .
( ) { : ( , ) }r i j i jO par par par par r окіл параметрів ipar Pars з радіусом .r
У практичній реалізації алгоритма будемо використовувати окіл
1( )iO par
радіусу 1.r
Загальна обчислювальна схема пропонованого алгоритму показана на рис. 1.
ГІБРИДНИЙ АЛГОРИТМ ОПТИМІЗАЦІЇ МУРАШИНИМИ КОЛОНІЯМИ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 75
procedure DLSACO();
xOptimal = деякий припустимий варіант розв'язку;
parsOptimal = деякі припустимі параметри ОМК;
for each pars in Pars do
( )xCurrent ACO pars
if ( ) ( )f xCurrent F xOptimal then
xOptimal xCurrent
parsOptimal pars
endif
endfor
while не вичерпано весь окіл 1( )O parsOptimal do
pars Генерація Чергової Точки Околу 1( )O parsOptimal
( )xCurrent ACO pars
if ( ) ( )f xCurrent F xOptimal then
xOptimal xCurrent
parsOptimal pars
endif
endwhile
return { , }xOptimal parsOptimal
end
РИС. 1. Загальна схема гібридного алгоритму
3. Ключові аспекти метода оптимізації мурашиними колоніями. Загаль-
на схема ОМК для знаходження оптимальної структури білків базується на
алгоритмі з [8], але з урахуванням в функції пристосованості допоміжних
компонент, що враховують евристичну інформацію.
При реалізації алгоритму кожен конкретний набір par Pars складався
з таких параметрів:
G – кількість поколінь мурах, які не знайшли покращення розв’язку,
необхідних для зупинки алгоритму;
an – кількість мурах у поколінні;
– коефіцієнт випаровування феромонного сліду;
– коефіцієнт значущості феромонного сліду;
– коефіцієнт значущості основної евристичної інформації;
– коефіцієнт значущості допоміжної евристичної інформації;
– поріг випадковості переходу по ребру;
0 – нижня межа значення феромону на ребрі;
1 – верхня межа значення феромону на ребрі;
en – кількість розв’язків-маршрутів у одному поколінні, що використо-
вуються для оновлення глобальної пам’яті мурах;
Л.Ф. ГУЛЯНИЦЬКИЙ, С.A. ЧОРНОЖУК
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 76
dn – кількість розв’язків-маршрутів у одному поколінні, що використову-
ються демоном для покращення результатів.
Сама множина наборів параметрів Pars визначалася парою an та en при
фіксованих інших параметрах ОМК. Тобто
{(12, 200+ n , 0.1, 0.2, 0.8, 0.5, 0.6, 0.2, 0.8, 1+ n , 2)}a ePars ,
де n 400* , 0,5a i i та n 0,19e .
Така множина визначалася емпірично і показувала гарні результати роботи
алгоритму при відносно високій швидкодії.
Проаналізувавши [8], запропоновано таку схему переходу з додавання
наступного ребра до ланцюга (рис. 2).
procedure СhooseEdge();
for each ((1,0,0),( 1,0,0),(0,1,0),(0, 1,0),(0,0,1),(0,0, 1))ie do
, , ,
,
, , ,
((1,0,0),( 1,0,0),(0,1,0),(0, 1,0),(0,0,1),(0,0, 1))
( ) ( ) ( )
;
( ) ( ) ( )
i i i
i
j j j
j
e d e d e d
e d
e d e d e d
e
p
endfor
p = [0,1]random ;
if p > then
result = Обрати ребро з найбільшим значенням ,
ie dp ;
else then
result = Обрати одне з ребер, враховуючи ймовірності переходу ,ie dp ;
endif
return result;
end
РИС. 2. Схема алгоритму додавання ребра до ланцюга в ОМК
Тут кожен поворот ie [5] при фіксованій довжині ланцюга еквівалентний
ребру графу задачі ОМК, описаному в [4]. Надалі будемо вважати твердження
«обрати поворот ie при фіксованій довжині ланцюга» та «обрати і-те ребро при
фіксованій довжині ланцюга» еквівалентними.
Визначимо евристичну інформацію так: , ,
i
F
e d e де F – різниця значення
F при умові вибору і-го ребра та поточного значення F (при довжині ланцюга d);
,ie d – це значення феромонного сліду на і-му ребрі при поточній довжині
ланцюга d, а
1 1 1 1
,
1
( ) | [ ( ) / ] |
.
( )
i
jd d d
j i j j j
j j k j
e d N
j
j d
d N d N dist e e v e v
N v
ГІБРИДНИЙ АЛГОРИТМ ОПТИМІЗАЦІЇ МУРАШИНИМИ КОЛОНІЯМИ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 77
Як і в [5], ( , )dist x y – це евклідова відстань у просторі 3.Z
Варто зазначити, що така допоміжна евристична інформація для ОМК
запропонована вперше. Мотивацією для такого підходу стала фітнес-функція
для методу імітаційного відпалу [5]. Як і вищезгадана фітнес-функція,
,ie d слу-
гує для того, щоб далекі ізольовані гідрофобні амінокислоти (наприклад,
110110100000001) не віддалялися від групи інших гідрофобних амінокислот при
побудові чергового ланцюга.
Очевидно, що при запропонованій схемі вибору ребер під час конструю-
вання ланцюга можуть виникати самоперетини. Для того, щоб справлятися
з цим, запропоновано наступний алгоритм генерації ланцюга (рис. 3).
procedure GeneratePath();
dvisited – множина опрацьованих ребер при довжині ланцюга d ;
dvisited :={};
pnt :=(0,0,0);
path :={(0,0,0)};
while довжина ланцюга do
dpossible – множина допустимих ребер при довжині ланцюга d ;
dpossible :={};
for each ((1,0,0),( 1,0,0),(0,1,0),(0, 1,0),(0,0,1),(0,0, 1))ie do
if pnt + ie not in path then
Додати ie у dpossible ;
endif
if dpossible = {} then
dvisited :={};
pnt = pnt – dpath ;
Видалити останній елемент з path ;
d:=d –1;
else
Обрати ребро opte використовуючи процедуру СhooseEdge;
Додати opte у dvisited ;
pnt = pnt + opte ;
Додати opte у path ;
d:=d +1;
endif
endfor
endwhile
return path ;
end
РИС. 3. Схема алгоритму генерації ланцюга в ОМК
Л.Ф. ГУЛЯНИЦЬКИЙ, С.A. ЧОРНОЖУК
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 78
На кожній генерації мурах з ОМК отримуємо an різних можливих ланцю-
гів. На
dn найкращих ланцюгів ( dn ланцюгів з найменшим значенням F) діє
демон – в нашому випадку, детермінований локальний пошук з [5]. Після дії
демону для кожної мурахи вираховуємо внесок феромону по ребрах шляху, зге-
нерованого нею.
Як і в [7], внесок феромону мурахи обраховується за формулою
min
0
min
(1 ), 1,i a
f f
i n
f f
,
де min , ,f f f – мінімальне, середнє, поточне значення цільової функції F
у черговій генерації мурах. Тільки en найменших
i беруть участь в оновленні
феромону. Феромон оновлюється і випаровується, так як описано у [7].
Результати та висновки. Розроблені алгоритми тестувалися на 10 реальних
значеннях білків довжиною 48, які взяті із відомої бібліотеки [5]. Результати
обчислювального експерименту подані в таблиці, де ( )optF x , optx X , резуль-
туюче значення цільової функції у точці розв’язку, знайденої розробленим
алгоритмом.
ТАБЛИЦЯ. Результати обчислювального експерименту
Код білка ( )optF x
101100111101110011001011010110
011000100000000110
– 29
111101101111100100110010000001
001000100110011101
– 31
010110111111001010010110101000
100110011001010010
– 31
010110010111001101100011111001
011010100001001010
– 30
001000101111001111011011100101
010010000001101101
– 30
111000110101101101101000000010
100100010011111101
– 30
010000101110101111011011000101
000111001100110001
– 31
0110111011110011100000010110
01101000110101011000
– 30
010100001010100101111110011101
001011001011100001
– 30
011000000110001110100101100100
100110011111110011
– 29
ГІБРИДНИЙ АЛГОРИТМ ОПТИМІЗАЦІЇ МУРАШИНИМИ КОЛОНІЯМИ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 79
Гібридизація алгоритмів детермінованого локального пошуку та ОМК
дозволяє автоматично налаштувати параметри ОМК до кожної конкретної
структури білка, що разом із пропонованою допоміжною евристичною інфор-
мацією дозволяє знайти кращі значення цільової функції на реальних даних
середньої довжини (30 – 60). Проте цей підхід потребує і подальших досліджень,
серед яких зазначимо такі.
Питання вибору множини параметрів ОМК, за якими алгоритм виконує
детермінований локальний пошук, залишається відкритим. Пропонований набір
параметрів визначався емпірично, але подальші дослідження та інші підходи до
вибору цих значень можуть значно покращити як і отримувані результати, так
і швидкодію алгоритму.
Спосіб подання графу задачі для ОМК може бути об’єктом подальших
досліджень [6]. Зокрема, наприклад, можна враховувати поточне значення цільо-
вої функції при переході по ребру графа, що, можливо, дозволить зробити
роботу алгоритму більш ефективною.
Важливим напрямом підвищення ефективності запропонованого алгоритму
є розроблення його версій з розпаралелюванням обчислювальної схеми.
Доцільно також досліджувати питання вибору ґратки
( , , , ), , ,p p pp s n p pars pars Pars яка напряму впливає на ефективність
гібридного алгоритму.
Л.Ф. Гуляницкий, С.А. Черножук
ГИБРИДНЫЙ АЛГОРИТМ ОПТИМИЗАЦИИ МУРАВЬИНЫМИ КОЛОНИЯМИ
ДЛЯ ПРЕДСКАЗАНИЯ СТРУКТУРЫ БЕЛКОВ
Предложен новый гибридный алгоритм, который позволяет автоматически настраивать
параметры алгоритма оптимизации муравьиными колониями для решения задачи
предсказания структуры белка.
L.F. Hulianytskyi, S.A. Chornozhuk
THE HYBRID ANT COLONY OPTIMIZATION ALGORITHM FOR PREDICTING
THE PROTEIN STRUCTURE
A new hybrid algorithm is proposed, which allows to automatically adjust the parameters of ant
colony optimization algorithm for solving protein structure prediction problem.
Список літератури
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. 11 р.
2. Dill K.A. Theory for the folding and stability of globular proteins. Biochemistry. 1985. 24(6),
Р. 1501 – 1509.
Л.Ф. ГУЛЯНИЦЬКИЙ, С.A. ЧОРНОЖУК
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 80
3. Dorigo M., Stützle T. Ant colony optimization. Cambridge (MA): MIT Press. 2004.
4. Гуляницкий Л.Ф., Рудык В.А. 2012. Анализ алгоритмов прогнозирования третичной
структуры протеина на базе метода оптимизации муравьиными колониями. Problems
of Computer Intellectualization (Eds. V. Velichko, O. Voloshin, K. Markov). Kiev-Sofia:
V.M. Glushkov Institute of Cybernetics, ITHEA. 2012. Р. 152 – 159.
5. Чорножук С.А. Новий алгоритм імітаційного відпалу для передбачення структури білків.
Компьютерная математика. 2018. С. 118 – 124.
6. Гуляницкий Л.Ф., Рудык В.А. Проблема предсказания структуры протеина: формализа-
ция с использованием кватернионов. Кибернетика и системный анализ. 2013. № 4.
С. 130 – 136.
7. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації.
Видавничо-поліграфічний центр “Київський університет”. 2016.
8. Shmygelska A., Hoos H.H. An ant colony optimization algorithm for the 2D and 3D
hydrophobic polar protein folding problem. BMC Bioinformatics. 2016. N 6(30). Р. 30 – 52.
9. 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. 92(1).
Р. 325 – 329.
Одержано 19.03.2019
|