Проблема предсказания структуры протеина: формализация с использованием кватернионов
Розглянуто питання формалізації задачі прогнозування третинної структури протеїнів, що базується на НР-моделі Ділла. Вивчено тривимірні дискретні решітки і підходи до подання шляхів у них. Запропоновано і досліджено два варіанти кодування шляхів в решітках, один з яких базується на використанні апар...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2013 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/86260 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Проблема предсказания структуры протеина: формализация с использованием кватернионов / Л.Ф. Гуляницкий, В.А. Рудык // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 130-136. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-86260 |
|---|---|
| record_format |
dspace |
| spelling |
Гуляницкий, Л.Ф. Рудык, В.А. 2015-09-11T17:11:18Z 2015-09-11T17:11:18Z 2013 Проблема предсказания структуры протеина: формализация с использованием кватернионов / Л.Ф. Гуляницкий, В.А. Рудык // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 130-136. — Бібліогр.: 18 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86260 519.8 Розглянуто питання формалізації задачі прогнозування третинної структури протеїнів, що базується на НР-моделі Ділла. Вивчено тривимірні дискретні решітки і підходи до подання шляхів у них. Запропоновано і досліджено два варіанти кодування шляхів в решітках, один з яких базується на використанні апарату кватерніонів. The authors discuss the formalization of protein tertiary structure prediction problem based on Dill’s HP-model. Three-dimensional discrete lattices and different approaches to representing paths on them are the subjects of investigation. Two ways of path encoding are proposed and formalized, one of which is based on quaternion tools. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Проблема предсказания структуры протеина: формализация с использованием кватернионов Проблема передбачення структури протеїну: формалізація з використанням кватерніонів Protein structure prediction problem: Formalization using quaternion tools Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Проблема предсказания структуры протеина: формализация с использованием кватернионов |
| spellingShingle |
Проблема предсказания структуры протеина: формализация с использованием кватернионов Гуляницкий, Л.Ф. Рудык, В.А. Системный анализ |
| title_short |
Проблема предсказания структуры протеина: формализация с использованием кватернионов |
| title_full |
Проблема предсказания структуры протеина: формализация с использованием кватернионов |
| title_fullStr |
Проблема предсказания структуры протеина: формализация с использованием кватернионов |
| title_full_unstemmed |
Проблема предсказания структуры протеина: формализация с использованием кватернионов |
| title_sort |
проблема предсказания структуры протеина: формализация с использованием кватернионов |
| author |
Гуляницкий, Л.Ф. Рудык, В.А. |
| author_facet |
Гуляницкий, Л.Ф. Рудык, В.А. |
| topic |
Системный анализ |
| topic_facet |
Системный анализ |
| publishDate |
2013 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Проблема передбачення структури протеїну: формалізація з використанням кватерніонів Protein structure prediction problem: Formalization using quaternion tools |
| description |
Розглянуто питання формалізації задачі прогнозування третинної структури протеїнів, що базується на НР-моделі Ділла. Вивчено тривимірні дискретні решітки і підходи до подання шляхів у них. Запропоновано і досліджено два варіанти кодування шляхів в решітках, один з яких базується на використанні апарату кватерніонів.
The authors discuss the formalization of protein tertiary structure prediction problem based on Dill’s HP-model. Three-dimensional discrete lattices and different approaches to representing paths on them are the subjects of investigation. Two ways of path encoding are proposed and formalized, one of which is based on quaternion tools.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/86260 |
| citation_txt |
Проблема предсказания структуры протеина: формализация с использованием кватернионов / Л.Ф. Гуляницкий, В.А. Рудык // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 130-136. — Бібліогр.: 18 назв. — рос. |
| work_keys_str_mv |
AT gulânickiilf problemapredskazaniâstrukturyproteinaformalizaciâsispolʹzovaniemkvaternionov AT rudykva problemapredskazaniâstrukturyproteinaformalizaciâsispolʹzovaniemkvaternionov AT gulânickiilf problemaperedbačennâstrukturiproteínuformalízacíâzvikoristannâmkvaterníonív AT rudykva problemaperedbačennâstrukturiproteínuformalízacíâzvikoristannâmkvaterníonív AT gulânickiilf proteinstructurepredictionproblemformalizationusingquaterniontools AT rudykva proteinstructurepredictionproblemformalizationusingquaterniontools |
| first_indexed |
2025-11-25T22:20:09Z |
| last_indexed |
2025-11-25T22:20:09Z |
| _version_ |
1850562719948734464 |
| fulltext |
ÓÄÊ 519.8
Ë.Ô. ÃÓËßÍÈÖÊÈÉ, Â.À. ÐÓÄÛÊ
ÏÐÎÁËÅÌÀ ÏÐÅÄÑÊÀÇÀÍÈß ÑÒÐÓÊÒÓÐÛ ÏÐÎÒÅÈÍÀ:
ÔÎÐÌÀËÈÇÀÖÈß Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÊÂÀÒÅÐÍÈÎÍÎÂ
Êëþ÷åâûå ñëîâà: ñâåðòûâàíèå ïðîòåèíà, òðåòè÷íàÿ ñòðóêòóðà ìîëåêóëû
áåëêà, äèñêðåòíûå ðåøåòêè, êâàòåðíèîíû.
ÂÂÅÄÅÍÈÅ
 ïîñëåäíåå âðåìÿ îäíîé èç ñàìûõ âàæíûõ è èññëåäóåìûõ ïðîáëåì â âû÷èñ-
ëèòåëüíîé áèîëîãèè ÿâëÿåòñÿ çàäà÷à ïðîãíîçèðîâàíèÿ òðåòè÷íîé ñòðóêòóðû
ìîëåêóëû áåëêà, èìåíóåìàÿ åùå çàäà÷åé î ñâåðòûâàíèè ïðîòåèíà. Ýòà ñòðóê-
òóðà èãðàåò êëþ÷åâóþ ðîëü â îïðåäåëåíèè ôóíêöèîíàëüíûõ ñâîéñòâ ïðîòåè-
íîâ è ÿâëÿåòñÿ èñòî÷íèêîì èíôîðìàöèè, âàæíîé äëÿ ïîëó÷åíèÿ ôóíäàìåí-
òàëüíûõ è ïðèêëàäíûõ ðåçóëüòàòîâ â ðàçëè÷íûõ ñôåðàõ íàóêè è òåõíîëîãèé,
ñðåäè êîòîðûõ áèîèíôîðìàòèêà, ìåäèöèíà, ôàðìàöåâòèêà, âû÷èñëèòåëüíàÿ
ãåîìåòðèÿ, íàíîòåõíîëîãèè.
Ñóòü ïðîáëåìû ïðåäñêàçàíèÿ òðåòè÷íîé ñòðóêòóðû çàêëþ÷àåòñÿ â òîì, ÷òî-
áû, èñõîäÿ èç ëèíåéíîé ïîñëåäîâàòåëüíîñòè ýëåìåíòîâ, ñîñòàâëÿþùèõ ìîëåêó-
ëó, îïðåäåëèòü åå ïðîñòðàíñòâåííóþ ôîðìó. Äëÿ ðåøåíèÿ ýòîé ïðîáëåìû èñ-
ïîëüçóþò èçâåñòíûå ýêñïåðèìåíòàëüíûå ïîäõîäû (ðåíòãåíîêðèñòàëëîãðàôèþ,
ìàãíèòíî-ðåçîíàíñíóþ ñïåêòðîñêîïèþ), îäíàêî îíè íå òîëüêî äîðîãîñòîÿùèå
è äëèòåëüíûå, íî è íå âñåãäà ïîçâîëÿþò íà ïðàêòèêå ïîëó÷àòü óäîâëåòâîðèòåëü-
íûå ðåçóëüòàòû. Ïîýòîìó â ïîñëåäíèå ãîäû ïðè èçó÷åíèè ñòðóêòóðû ìîëåêóë
øèðîêî ïðèìåíÿþò ìàòåìàòè÷åñêèå ìåòîäû èññëåäîâàíèé.
Íàèáîëåå èçó÷åíà áèîôèçè÷åñêàÿ ÍÐ-ìîäåëü ñâåðòûâàíèÿ ïðîòåèíà, ïðåäëî-
æåííàÿ Ê. Äèëëîì â 1985 ã.: èùåòñÿ ñòðóêòóðà ìîëåêóëû, ìèíèìèçèðóþùàÿ
ýíåðãåòè÷åñêèé ïîòåíöèàë [1–3]. Ìàòåìàòè÷åñêèì ðåøåíèåì çàäà÷è ÿâëÿåòñÿ íå-
êîòîðàÿ íåðàçðûâíàÿ äâóõìåðíàÿ èëè òðåõìåðíàÿ êðèâàÿ áåç ñàìîïåðåñå÷åíèé.
Ïîäàâëÿþùåå áîëüøèíñòâî èçâåñòíûõ ìîäåëåé ñòðóêòóðû áåëêà äèñêðåòíû, ïî-
ñêîëüêó ôîðìà ìîëåêóëû ïðåäñòàâëÿåòñÿ â âèäå ïóòè â íåêîòîðîé äèñêðåòíîé ðå-
øåòêå. Âàæíî îòìåòèòü, ÷òî äàæå ïðè ñóùåñòâåííûõ óïðîùåíèÿõ õèìèêî-áèîëî-
ãè÷åñêèõ ñâîéñòâ áåëêà ïðè ìàòåìàòè÷åñêîì ìîäåëèðîâàíèè âîçíèêàþò
îïòèìèçàöèîííûå çàäà÷è, êîòîðûå îòíîñÿòñÿ ê NP-ñëîæíûì [4].
×àùå âñåãî äëÿ óïðîùåíèÿ ìîäåëè ðàññìàòðèâàþòñÿ äâóõìåðíûå èëè òðåõ-
ìåðíûå êóáè÷åñêèå ðåøåòêè [5–11], õîòÿ â êîíòåêñòå äàííîé ïðîáëåìû îíè èìå-
þò íåäîñòàòêè. Ïðè ïåðåõîäå ê áîëåå ñëîæíûì ðåøåòêàì âîçíèêàåò íåîáõîäè-
ìîñòü çàêîäèðîâàòü ïóòü â âèäå íåêîòîðîãî ìàòåìàòè÷åñêîãî îáúåêòà, ìàêñè-
ìàëüíî îòîáðàæàþùåãî åãî õàðàêòåðèñòèêè, ñðåäè ýòèõ îáúåêòîâ è áóäåò
îñóùåñòâëÿòüñÿ ïîèñê ñ ïîìîùüþ ðàçëè÷íûõ àëãîðèòìîâ îïòèìèçàöèè.
Âàæíûì óñëîâèåì óñïåøíîãî ïðèìåíåíèÿ ìåòîäîâ ìîäåëèðîâàíèÿ ïðî-
ñòðàíñòâåííîé ñòðóêòóðû áåëêà ÿâëÿåòñÿ âûáîð àäåêâàòíîãî ìàòåìàòè÷åñêîãî
àïïàðàòà äëÿ ôîðìàëüíîãî îïèñàíèÿ çàäà÷è.  íàñòîÿùåé ñòàòüå êðàòêî èçëîæå-
íû ïðèíöèïû, íà êîòîðûõ îñíîâàíà ìîäåëü Äèëëà. Ïðèâåäåíû ñâîéñòâà ðåøåòîê
êàê ìàòåìàòè÷åñêèõ îáúåêòîâ, â ÷àñòíîñòè, èíâàðèàíòíîñòü îòíîñèòåëüíî ïåðå-
íîñîâ è âðàùåíèé, à òàêæå ñîñåäñòâî óçëîâ.
Ïðåäëîæåíû äâà ïîäõîäà ê êîäèðîâêå ïóòåé â òðåõìåðíûõ ðåøåòêàõ, èìåþ-
ùèå ðàçëè÷íûå ñâîéñòâà ïðè èõ ïîñòðîåíèè è èñïîëüçîâàíèè â àëãîðèòìàõ ïðåä-
130 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
� Ë.Ô. Ãóëÿíèöêèé, Â.À. Ðóäûê, 2013
ñêàçàíèÿ ñòðóêòóðû áåëêà. Îñîáîå âíèìàíèå óäåëåíî ïðèìåíåíèþ àïïàðàòà
êâàòåðíèîíîâ äëÿ ïîñòðîåíèÿ q-êîäèðîâîê.
ÌÎÄÅËÜ ÄÈËËÀ
Ìîëåêóëû áåëêà ñîñòîÿò èç àìèíîêèñëîò ïîñëåäîâàòåëüíî ñâÿçàííûõ ïåïòèä-
íîé ñâÿçüþ. Öåïî÷êó àìèíîêèñëîò íàçûâàþò ïåðâè÷íîé ñòðóêòóðîé ïðîòåèíà.
Ïðè âçàèìîäåéñòâèè âíóòðè ìîëåêóëû ôîðìèðóþòñÿ âîäîðîäíûå ñâÿçè, â ðå-
çóëüòàòå êîòîðûõ ÷àñòè öåïè ñâîðà÷èâàþòñÿ â ïðîñòðàíñòâåííûå ñòðóêòóðû:
�-ñïèðàëè, �-ëèñòû è äðóãèå ôðàãìåíòû, ñîñòàâëÿþùèå âòîðè÷íóþ ñòðóêòóðó
áåëêà [12, 13]. Äàëåå èç ýòèõ ýëåìåíòîâ ôîðìèðóåòñÿ íåêîòîðàÿ ïðîñòðàí-
ñòâåííàÿ ôîðìà — òðåòè÷íàÿ ñòðóêòóðà áåëêà. Âñå àìèíîêèñëîòû â çàâèñè-
ìîñòè îò ñâîèõ ñâîéñòâ äåëÿòñÿ íà äâà êëàññà: ãèäðîôîáíûå è ïîëÿðíûå. Ïðè
ñâîðà÷èâàíèè ìîëåêóëû â ïîëÿðíîé ñðåäå (âîäå) ïîëÿðíûå àìèíîêèñëîòû ïå-
ðåìåùàþòñÿ íà ïîâåðõíîñòü ìîëåêóëû, à ãèäðîôîáíûå — âîâíóòðü. Ìåæäó
áëèçêî ðàñïîëîæåííûìè ãèäðîôîáíûìè àìèíîêèñëîòàìè âîçíèêàþò ãèäðîôîá-
íûå ñâÿçè, èìåííî îíè èãðàþò ãëàâíóþ ðîëü ïðè ôîðìèðîâàíèè òðåòè÷íîé
ñòðóêòóðû ïðîòåèíà. Ñâÿçè, ñóùåñòâóþùèå âíóòðè ìîëåêóëû, îïðåäåëÿþò åå
ýíåðãèþ. Ñîãëàñíî òåðìîäèíàìè÷åñêîé ãèïîòåçå áåëîê ïðèíèìàåò òó ñòðóêòó-
ðó, êîòîðàÿ ìèíèìèçèðóåò åãî ñâîáîäíóþ ýíåðãèþ. Ýòó ñòðóêòóðó íàçûâàþò
íàòèâíîé êîíôîðìàöèåé.
Ïðè èçó÷åíèè áåëêà ïîëüçóþòñÿ äîãìîé «ïîñëåäîâàòåëüíîñòü–ñòðóêòó-
ðà–ôóíêöèîíàëüíîñòü». Èìååòñÿ â âèäó, ÷òî ôóíêöèè áåëêà íàïðÿìóþ çàâèñÿò îò
åãî ôîðìû â ïðîñòðàíñòâå, êîòîðàÿ â ñâîþ î÷åðåäü îäíîçíà÷íî îïðåäåëÿåòñÿ åãî
ïåðâè÷íîé ñòðóêòóðîé [12]. Îäíàêî ñóùåñòâóþò òàêæå è áåëêè-êîíôîðìåðû, êî-
òîðûì ïðèñóùè äâå íàòèâíûå êîíôîðìàöèè. Îáû÷íî â òàêèõ ñëó÷àÿõ èõ ýíåðãèÿ
îòëè÷àåòñÿ íåçíà÷èòåëüíî.
Ïîä çàäà÷åé ïðîãíîçèðîâàíèÿ òðåòè÷íîé ñòðóêòóðû áåëêà ïîíèìàþò îïðå-
äåëåíèå åãî ôîðìû â ïðîñòðàíñòâå ïî çàäàííîé ïîñëåäîâàòåëüíîñòè àìèíîêèñ-
ëîò. Ìåòîäû åå ðåøåíèÿ äåëÿòñÿ íà äâà êëàññà: ñòàòèñòè÷åñêèå è de novo. Ñòà-
òèñòè÷åñêèå ìåòîäû áàçèðóþòñÿ íà òîì, ÷òî ïîõîæèå ÷àñòè ïåðâè÷íîé ïîñëåäî-
âàòåëüíîñòè ñâîðà÷èâàþòñÿ â ïîõîæèå òðåõìåðíûå ôîðìû. Àíàëèçèðóåòñÿ áàçà
äàííûõ èçâåñòíûõ áåëêîâ íà ñõîæåñòü ñ çàäàííûì, â ðåçóëüòàòå ÷åãî ñòðîèòñÿ
òðåòè÷íàÿ ñòðóêòóðà. Ñ ïîìîùüþ òàêîãî ïîäõîäà ìîæíî äîñòè÷ü óäîâëåòâîðè-
òåëüíîé òî÷íîñòè, íî ïðîáëåìà â òîì, ÷òî äàëåêî íå äëÿ âñåõ ïåðâè÷íûõ ïîñëå-
äîâàòåëüíîñòåé óäàåòñÿ íàéòè èì ïîäîáíûå.  òàêèõ ñëó÷àÿõ ïðèìåíÿþòñÿ
ìåòîäû de novo, íå èñïîëüçóþùèå äîïîëíèòåëüíîé èíôîðìàöèè, êðîìå
ïåðâè÷íîé ñòðóêòóðû, è ñòàâèòñÿ çàäà÷à ìèíèìèçàöèè ýíåðãèè.
Èìåííî ê ìåòîäàì de novo îòíîñèòñÿ ãèäðîôîáíî-ïîëÿðíàÿ ìîäåëü Äèëëà.
 íåé ïåðâè÷íàÿ ñòðóêòóðà áåëêà çàäàåòñÿ ïîñëåäîâàòåëüíîñòüþ S n� � � �1 2� ,
� i H P�{ }, i n�1, , ãäå H , P — ãèäðîôîáíàÿ è ïîëÿðíàÿ àìèíîêèñëîòû ñîîòâå-
òñòâåííî, n — êîëè÷åñòâî àìèíîêèñëîò â ìîëåêóëå. Òðåòè÷íàÿ ñòðóêòóðà ïðåä-
ñòàâëÿåòñÿ êàê ïóòü áåç ñàìîïåðåñå÷åíèé ñîîòâåòñòâóþùåé äëèíû â îïðåäåëåí-
íîé äèñêðåòíîé ðåøåòêå. Â êàæäîì óçëå ïóòè ïîñëåäîâàòåëüíî ðàñïîëàãàþòñÿ
àìèíîêèñëîòíûå îñòàòêè. Ñ÷èòàåòñÿ, ÷òî ìåæäó ãèäðîôîáíûìè îñòàòêàìè, ðàñ-
ïîëîæåííûìè â ñîñåäíèõ óçëàõ (íî íå ñîñåäíèõ â ïåðâè÷íîé ïîñëåäîâàòåëüíîñ-
òè), âîçíèêàþò ãèäðîôîáíûå ñâÿçè. Ýíåðãèÿ ñòðóêòóðû — êîëè÷åñòâî ñâÿçåé
â íåé ñî çíàêîì ìèíóñ. Ñòàâèòñÿ çàäà÷à íàéòè ñòðóêòóðó ñ ìèíèìàëüíîé ýíåðãè-
åé. Áîëåå ôîðìàëüíî, åñëè àìèíîêèñëîòå � i â ñòðóêòóðå S ñîîòâåòñòâóåò óçåë
U i( )� , ýíåðãèÿ îïðåäåëÿåòñÿ ïî ôîðìóëå
E S I U U h hi j
i j n
i j( ) ( ( ), ( )) ( ) ( )� �
� � � � �
� � � � �
1 2 2
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 131
ãäå
I U U
U U
( , )
, ,
1 2
1 21
0
�
�
åñëè óçëû è ñîñåäíèå
h
H
P
( )
, ,
, .
�
�
�
�
�
�
�
1
0
åñëè
åñëè
ÐÅØÅÒÊÈ
Òåðìèí «ðåøåòêà» èñïîëüçóåòñÿ â ðàçëè÷íûõ îáëàñòÿõ ìàòåìàòèêè.  òåîðèè
ãðóïï ðåøåòêà L â åâêëèäîâîì ïðîñòðàíñòâå �
n îïðåäåëÿåòñÿ êàê äèñêðåòíàÿ
ïîäãðóïïà �
n [14]. Åå ìîæíî ïðåäñòàâèòü êàê ìíîæåñòâî âåêòîðîâ
L a e ai i
i
m
i� �
�
�
�
�
�
1
| � , ãäå B e e em
n� �{ }1 2, , ,� � — íåêîòîðûé áàçèñ, à � —
ìíîæåñòâî öåëûõ ÷èñåë. Îòìåòèì, ÷òî ðàçëè÷íûå áàçèñû ìîãóò ïîðîæäàòü
îäèíàêîâûå ðåøåòêè. Äàëåå ðàññìîòðèì ðåøåòêè â òðåõìåðíîì åâêëèäîâîì
ïðîñòðàíñòâå, èõ ýëåìåíòû íàçîâåì óçëàìè.
Áóäåì ãîâîðèòü, ÷òî ðåøåòêà èíâàðèàíòíà îòíîñèòåëüíî îòîáðàæåíèÿ
f n n: � �� , åñëè äëÿ ëþáûõ v L� âûïîëíÿåòñÿ f v L( ) � . Ïîñêîëüêó ðåøåòêà ÿâ-
ëÿåòñÿ ïîäãðóïïîé â �
n , îíà èíâàðèàíòíà îòíîñèòåëüíî ïàðàëëåëüíîãî ïåðåíîñà
íà ëþáîé âåêòîð v L� .
Ñîñåäñòâî â ðåøåòêå. Äëÿ ôîðìàëèçàöèè ïîíÿòèÿ ïóòè â ðåøåòêå íåîáõî-
äèìî ââåñòè ïîíÿòèå ñîñåäñòâà ìåæäó óçëàìè. Äëÿ ýòîãî ñëåäóåò çàäàòü áèíàð-
íîå îòíîøåíèå ñîñåäñòâà R L L� � : óçåë v L� áóäåò ñîñåäíèì ñ óçëîì u L� òîãäà
è òîëüêî òîãäà, êîãäà ( , )u v R� . Ñîñåäñòâî â ðåøåòêå èíâàðèàíòíî îòíîñèòåëüíî
îòîáðàæåíèÿ f n n: � �� , åñëè ðåøåòêà èíâàðèàíòíà îòíîñèòåëüíî f è äëÿ
äâóõ ñîñåäíèõ óçëîâ u v L, � ñîñåäíèìè òàêæå ÿâëÿþòñÿ óçëû f u( ) è f v( ). Åñëè
îòíîøåíèå ñîñåäñòâà èíâàðèàíòíî îòíîñèòåëüíî ïàðàëëåëüíîãî ïåðåíîñà íà ëþ-
áîé âåêòîð v L� , òî åãî ìîæíî îïðåäåëèòü ñ ïîìîùüþ íåêîòîðîãî ìíîæåñòâà
âåêòîðîâ ñîñåäñòâàV v v Ls� �{ }1, ,� : óçåë c L1 � áóäåò ñîñåäíèì ñ óçëîì c L2 �
òîãäà è òîëüêî òîãäà, êîãäà c c V1 2� � . È íàîáîðîò, åñëè ñîñåäñòâî çàäàíî îïè-
ñàííûì îáðàçîì, îíî èíâàðèàíòíî îòíîñèòåëüíî ïàðàëëåëüíîãî ïåðåíîñà íà ëþ-
áîé âåêòîð v L� . ×òîáû îòíîøåíèå ñîñåäñòâà áûëî ñèììåòðè÷íûì, äîëæíî âû-
ïîëíÿòüñÿ óñëîâèå v V v V� � � � .
Ïóòåì äëèíû m â ðåøåòêå L c ñîñåäñòâîì R áóäåì íàçûâàòü ïîñëåäîâàòåëü-
íîñòü c c c cm m( ) � 1 2 � òàêóþ, ÷òî c Li � , i m�1, , è âûïîëíÿåòñÿ óñëîâèå
( , )c c Ri i� �1 , i m� �1 1, (óñëîâèå ñâÿçíîñòè). Îòìåòèì, ÷òî ïóòü íå ñîäåðæèò ñà-
ìîïåðåñå÷åíèé, åñëè èç óñëîâèÿ c ci j� ñëåäóåò, ÷òî i j� , i j m, ,�1 .
ÊÎÄÈÐÎÂÊÈ
Ïðè ðåøåíèè çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè, ïðîñòðàíñòâîì ðåøåíèé êî-
òîðûõ ÿâëÿþòñÿ ïóòè â íåêîòîðîé äèñêðåòíîé ðåøåòêå, ÷àñòî áûâàåò íåýôôåê-
òèâíî ïðåäñòàâëÿòü ïóòü íåïîñðåäñòâåííî â âèäå ïîñëåäîâàòåëüíîñòè êîîðäè-
íàò óçëîâ ðåøåòêè, ïîñêîëüêó íå êàæäàÿ òàêàÿ ïîñëåäîâàòåëüíîñòü óäîâëåòâî-
ðÿåò óñëîâèþ ñâÿçíîñòè ïóòè. Àëüòåðíàòèâíûì ïðåäñòàâëåíèåì ìîãóò ñëóæèòü
äðóãèå ñïîñîáû êîäèðîâêè ïóòåé.
Ïóñòü � — ìíîæåñòâî íàòóðàëüíûõ ÷èñåë. Ïîä êîäèðîâêîé ïóòè c c cm1 2� ,
îáîçíà÷åííîé Enc ( ... )c c c s s sm k1 2 1 2� � , äàëåå áóäåì ïîíèìàòü ïîñëåäîâàòåëü-
132 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
â ïðîòèâíîì ñëó÷àå;
íîñòü s s sm p1 2� � , s Si � , i m p� �1, , ãäå S — íåêîòîðûé àëôàâèò êîäèðîâêè,
a p �� — ïàðàìåòð êîäèðîâêè, åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:
— äëÿ ëþáûõ m �� è s s s Sm p1 2, , ,� � � ñóùåñòâóþò c c c Lm1 2, , ,� � òàêèå,
÷òî ñïðàâåäëèâî ðàâåíñòâî Enc ( )c c c s s sm m p1 2 1 2� � � � ;
— åñëè Enc ( ... ) ...c c c s s sm m p1 2 1 2� � , òî Enc ( ... ) ...c c c c s sm m1 2 1 1 2� �
...s sm p m p� � �1.
Êîäèðîâêà èíâàðèàíòíà îòíîñèòåëüíî îòîáðàæåíèÿ f n n: � �� , åñëè ðå-
øåòêà è îòíîøåíèå ñîñåäñòâà â íåé èíâàðèàíòíû îòíîñèòåëüíî f , è äëÿ ëþáûõ
m ��, c c c Lm1 2, , ,� � èç óñëîâèÿ Enc ( ... )c c c s s sm m p1 2 1 2� �� ñëåäóåò, ÷òî
Enc ( ( ) ( ) ( )) ...f c f c f c s s sm m p1 2 1 2� � � .
Êîäèðîâêà ðàçáèâàåò ìíîæåñòâî ïóòåé â ðåøåòêå íà êëàññû ýêâèâàëåíòíîñ-
òè: ïóòè c c cm1 2 ... è � � �c c cm1 2 ... îòíîñÿòñÿ ê îäíîìó êëàññó òîãäà è òîëüêî òîãäà,
êîãäà Enc Enc( ) ( ... )c c c c c cm m1 2 1 2� � � � � .
Àáñîëþòíàÿ êîäèðîâêà. Îïðåäåëåííóþ ïî ôîðìóëå
Enc abs m m mc c c c c c c c c( ... ) ( )( )... ( )1 2 2 1 3 2 1� � � � � (1)
êîäèðîâêó íàçîâåì àáñîëþòíîé. Åå àëôàâèò — ýòî âñå ìíîæåñòâî V , à çíà-
÷åíèå ïàðàìåòðà p � �1. Ìîæíî ïîêàçàòü, ÷òî àáñîëþòíàÿ êîäèðîâêà èíâà-
ðèàíòíà îòíîñèòåëüíî ïàðàëëåëüíîãî ïåðåíîñà íà ëþáîé âåêòîð v L� è ðàçáè-
âàåò ìíîæåñòâî ïóòåé íà êëàññû ýêâèâàëåíòíîñòè, âíóòðè êîòîðûõ ýëåìåíòû
ðàâíû ñ òî÷íîñòüþ äî ïàðàëëåëüíîãî ïåðåíîñà.
Àáñîëþòíóþ êîäèðîâêó óäîáíî èñïîëüçîâàòü äëÿ ðåøåíèÿ çàäà÷, åñëè â ïó-
òÿõ íå âàæíû êîîðäèíàòû íà÷àëüíîé òî÷êè. Ïðåèìóùåñòâî ïðèìåíåíèÿ àáñîëþò-
íîé êîäèðîâêè ïåðåä ïîñëåäîâàòåëüíîñòüþ êîîðäèíàò óçëîâ ñîñòîèò â òîì, ÷òî
àâòîìàòè÷åñêè âûïîëíÿåòñÿ óñëîâèå ñâÿçíîñòè ïóòè.
Ïðèìåíåíèå êâàòåðíèîíîâ â çàäà÷àõ ïðåäñêàçàíèÿ ñòðóêòóðû ïðîòåè-
íà. Â äàëüíåéøåì äëÿ îïèñàíèÿ ïðîöåññà âðàùåíèÿ áóäåì èñïîëüçîâàòü ïîíÿòèå
êâàòåðíèîíîâ. Ïðèâåäåì îñíîâíûå ñâåäåíèÿ [15], êîòîðûå ïîíàäîáÿòñÿ äëÿ ôîð-
ìàëèçàöèè ðàññìàòðèâàåìîé ïðîáëåìû.
Ïîëå êâàòåðíèîíîâ H — ýòî ìíîæåñòâî ïàð âèäà ( , )a u
�
, ãäå a �� è
�
u ��
3
ñ îïåðàöèÿìè ñëîæåíèÿ è óìíîæåíèÿ, îïðåäåëåííûìè ñëåäóþùèì îáðàçîì:
( , ) ( , ) ( , )a u b v a b u v
� � � �
� � � � ,
( , )( , ) ( , )a u b v ab u v av bu u v
� � � � � � � �
� � � � � � .
Çäåñü òî÷êîé îáîçíà÷åíî ñêàëÿðíîå ïðîèçâåäåíèå, à ñèâîëîì � — âåêòîðíîå.
Íîðìà êâàòåðíèîíà q x y z� ( , ( , , ))� åñòåñòâåííûì îáðàçîì îïðåäåëÿåòñÿ êàê
| | | |q x y z� � � �� 2 2 2 2 . Êâàòåðíèîíîì, ñîïðÿæåííûì c çàäàííûì êâàòåðíèî-
íîì q x y z� ( , ( , , ))� , íàçûâàåòñÿ êâàòåðíèîí q x y z* ( , ( , , ))� �� .
Ôîðìóëà äëÿ âû÷èñëåíèÿ îáðàòíîãî ïî óìíîæåíèþ êâàòåðíèîíà áóäåò
èìåòü âèä
q
q
q
� �1
2
*
| | | |
.
Òðåõìåðíûé âåêòîð
�
v ��
3 ìîæíî ðàññìàòðèâàòü êàê êâàòåðíèîí ( , )0
�
v .
Ïóñòü q u� ( , )�
�
— êâàòåðíèîí ñ åäèíè÷íîé íîðìîé, à
�
v ��
3 . Òîãäà ðåçóëüòàò
âðàùåíèÿ âåêòîðà
�
v âîêðóã îñè
�
u íà óãîë � �� 2arccos ìîæíî ïðåäñòàâèòü â âèäå
ïðîèçâåäåíèÿ qvq
� �1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 133
Ïîñòðîåíèå q-êîäèðîâêè. Ðàññìîòðèì òðåõìåðíóþ ðåøåòêó L ñ ìíîæåñ-
òâîì âåêòîðîâ ñîñåäñòâà V , äëÿ êîòîðîé âûïîëíÿåòñÿ ñëåäóþùåå ñâîéñòâî: åñëè
v V� — íåêîòîðûé ôèêñèðîâàííûé âåêòîð, òî
� � � � � � � � � � �� � �
�
� �
�v V q v V q vq V q v q vv v v v v
H : ( ) ( )1 1 . (2)
Åñëè îáîçíà÷èòü Q Q v v VV � �{ }( )| , òî ìîæíî ïîêàçàòü, ÷òî òàêèå ðåøåòêè
èíâàðèàíòíû îòíîñèòåëüíî ïîâîðîòîâ, çàäàííûõ êâàòåðíèîíàìè q QV� .
 äâóõìåðíîì ñëó÷àå, êðîìå àáñîëþòíîé, ïðèìåíÿåòñÿ îòíîñèòåëüíàÿ êîäè-
ðîâêà, â êîòîðîé ïîëîæåíèå ñëåäóþùåé àìèíîêèñëîòû çàäàåòñÿ îòíîñèòåëüíî
ïðåäûäóùåé [7]. Èñïîëüçóÿ ïîíÿòèå êâàòåðíèîíîâ, ïîñòðîèì ïðîöåäóðó, êîòîðàÿ
ïî àáñîëþòíîé êîäèðîâêå ïóòè áóäåò êîíñòðóèðîâàòü åãî êîäèðîâêó Enc q , è íàçî-
âåì åå q-êîäèðîâêîé. Îòìåòèì, ÷òî q-êîäèðîâêà ÿâëÿåòñÿ àíàëîãîì îòíîñèòåëüíîé
êîäèðîâêè, èñïîëüçóåìîé â ðåøåòêàõ íà ïëîñêîñòè, â òðåõìåðíîì ñëó÷àå.
Çàôèêñèðóåì íåêîòîðûé âåêòîð ñîñåäñòâà a V0 � . Èç óñëîâèÿ (2) ñëåäóåò,
÷òî ñóùåñòâóåò ôóíêöèÿ Q V Qv: � òàêàÿ, ÷òî äëÿ âñåõ a V� âûïîëíÿåòñÿ ðà-
âåíñòâî Q a a Q a a( ) ( )0
1� � , ïðè÷åì â êà÷åñòâå Q a( )0 âûáåðåì òîæäåñòâåííûé
êâàòåðíèîí, ò.å. îïèñûâàþùèé íóëåâîé ïîâîðîò Q a( ) ( , ( , , ))0 0 0 0 1� . Äîêàæåì
ñëåäóþùåå óòâåðæäåíèå.
Óòâåðæäåíèå. Åñëè q QV� , òî Q qa q q( )0
1� � .
Äîêàçàòåëüñòâî. Èç óñëîâèÿ q QV� ñëåäóåò, ÷òî ñóùåñòâóåò òàêîé âåêòîð
v V� , äëÿ êîòîðîãî Q v q( ) � è îäíîâðåìåííî qa q v0
1� � . Òîãäà, ïîäñòàâèâ âòîðîå
ðàâåíñòâî â ïåðâîå, ïîëó÷èì èñêîìîå óòâåðæäåíèå. Äîêàçàòåëüñòâî çàâåðøåíî.
Ïóñòü òåïåðü çàäàíà àáñîëþòíàÿ êîäèðîâêà ïóòè a a am1 2 1... � �
� Enc abs mc c c( ... )1 2 , âû÷èñëåííàÿ ïî ôîðìóëå (1). Ïîñòðîèì q-êîäèðîâêó
r r r c c cm q m1 2 2 1 2... ( ... )� � Enc , r Qi V� ïî ñëåäóþùèì ïðàâèëàì:
r Q a0 1� ( ) ;
r Q r r r a r r r k mk k k k k� � �
�
�
�
� �
� �( ... ... ), ,
1
1
2
1
0
1
1 0 1 1 1 2 .
Èç ïðèâåäåííîé ñõåìû âûâåäåì òàêæå îáðàòíóþ: ïî çàäàííîé q-êîäèðîâêå
r r rm1 2 2... � ïîñòðîèì ïóòü c c cm1 2 ... òàêîé, ÷òî r r r c c cm q m1 2 2 1 2... ( ... )� � Enc .
Òåîðåìà 1. Åñëè a a1 0� è a r r r a r r rk k k
� � �
� � �
1 2 1 0 1
1
2
1
1
1... ... , k m� �2 1, , òî êî-
äèðîâêà � � � �r r rm1 2 2... , êîòîðàÿ ñîîòâåòñòâóåò àáñîëþòíîé a a am1 2 1� � , ðàâíà
r r rm1 2 2... � .
Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, èìååì
� � � �r Q a Q a0 1 0 0 0 0 1( ) ( ) ( , ( , , )) ;
� � � � � � � � �� � � �r Q r a r Q r r a r r Q r a r1 0
1
2 0 0
1
1 0 1
1
0 1 0 1
1( ) ( ) ( ) r1.
Äàëåå âîñïîëüçóåìñÿ ìåòîäîì ìàòåìàòè÷åñêîé èíäóêöèè. Ïóñòü r rt t� � äëÿ
âñåõ t k�1, . Ïîêàæåì, ÷òî r rk k� �� �1 1:
� � � � � � � � ��
�
�
� �
�r Q r r r a r r rk k k k k1
1
1
1
0
1
2 0 1( ... ... )
� � � ��
�
� �
� �
� �Q r r r r r r a r r r
k k k k k
( ... ... ...1
1
1
0
1
1 2 1 0 1
1 1
1
1
0 1 1 0 1
1
1
�
� �
�
�� � � � �r r r Q r a r rk k k k... ) ( ) .
Òàêèì îáðàçîì îïðåäåëåíî, êàê èç q-êîäèðîâêè ïîëó÷èòü àáñîëþòíóþ, èç
êîòîðîé, â ñâîþ î÷åðåäü, ìîæíî ïîëó÷èòü ïîñëåäîâàòåëüíîñòü óçëîâ ïóòè, âîñ-
ïîëüçîâàâøèñü ôîðìóëîé (1).
Òåîðåìà äîêàçàíà.
134 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
Äîêàæåì îäíî èç âàæíûõ ñâîéñòâ îòíîñèòåëüíîé êîäèðîâêè.
Òåîðåìà 2. Ïîâîðîò ïóòè, çàäàííîãî àáñîëþòíîé êîäèðîâêîé a a am1 2 1� � ïðè
óñëîâèè, ÷òî a a1 0� , îïèñàííûé êâàòåðíèîíîì q QV� , íå ìåíÿåò åãî êîäèðîâêè.
Äîêàçàòåëüñòâî. Ïóñòü r r rm1 2 2... � — q-êîäèðîâêà, êîòîðàÿ ñîîòâåòñòâóåò
àáñîëþòíîé a a am1 2 1... � òàêîé, ÷òî a a1 0� , a r r r a r r rk k k
� � �
� � �
1 2 1 0 1
1
2
1
1
1
� ... ,
k m� �2 1, . Ðàññìîòðèì íåêîòîðûé êâàòåðíèîí q QV� è îïðåäåëèì, êàêîé áóäåò
q-êîäèðîâêà äëÿ ïóòè, ïîëó÷åííîãî â ðåçóëüòàòå ïîâîðîòà, ñîîòâåòñòâóþùåãî
êâàòåðíèîíó q. Îáîçíà÷èì
a qa q qa q1 1
1
0
1� � �� � ,
a qa q qr r r a r r r q kk k k k
� � � ��
� �
� � � �1
1 2 1 0 1
1
2
1
1
1 1 2... ... , , m �1 .
Ïîñòðîèì îòíîñèòåëüíóþ êîäèðîâêó äëÿ a a a m1 2 1� � � �... :
� � � ��r Q a Q qa q q0 1 0
1( ) ( ) ,
� � � � � � � �� � � �r Q r a r Q q a q Q q qa q q Q a Q1 0
1
2 0
1 1
2
1
2
1
2( ) ( ) ( ) ( ) ( )r a r r
0
1
2 0 1
� � .
Äàëåå, äîïóñòèì, ÷òî r rt t� � äëÿ âñåõ t k�1, è ìåòîäîì ìàòåìàòè÷åñêîé èí-
äóêöèè ïîêàæåì, ÷òî r rk k� �� �1 1:
� � � � � � � � � ��
�
�
� �
�r Q r r r a r r rk k k k k1
1
1
1
0
1
2 0 1( ... ... )
� ��
�
� � �
�
� �
�
Q r r r q qa q qr r Q r r
k k k k k k
( ... ... ) (1
1
1
1
1 1
2
1
1
1
1
1
1
1
2 1
� �
� �... ... )r a r rk k
� ��
�
� � �
� �Q r r r r a r r r r
k k k k k( ... ... )1
1
1
1
1
0
1
2 0 1 1.
Òàêèì îáðàçîì, q-êîäèðîâêîé, êîòîðàÿ ñîîòâåòñòâóåò àáñîëþòíîé
� � � �a a am1 2 1... , áóäåò � � � �� �r r r r r rm m1 2 2 1 2 2... ... .
Òåîðåìà äîêàçàíà.
Êàê ñëåäñòâèå, â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè, ãäå âàæíà ôîðìà
ïóòè, à íå åãî ðàñïîëîæåíèå, èñïîëüçîâàíèå q-êîäèðîâêè ðàçðåøàåò ñóçèòü ïðî-
ñòðàíñòâî âàðèàíòîâ ðåøåíèé, ÷òî ïîçâîëÿåò óìåíüøèòü âðåìÿ ïîèñêà â íåì.
ÇÀÊËÞ×ÅÍÈÅ
 çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè, ïðîñòðàíñòâîì ðåøåíèé êîòîðûõ ÿâ-
ëÿþòñÿ ïóòè â íåêîòîðîé äèñêðåòíîé ðåøåòêå, ìîæíî èñïîëüçîâàòü ðàçëè÷íûå
ñïîñîáû ïðåäñòàâëåíèÿ ïóòè â âèäå ìàòåìàòè÷åñêîãî îáúåêòà. Öåëåñîîáðàç-
íîñòü âûáîðà òîãî èëè èíîãî ïðåäñòàâëåíèÿ çàâèñèò îò îñîáåííîñòåé çàäà÷è.
Àáñîëþòíàÿ êîäèðîâêà ïðîùå â âû÷èñëèòåëüíîì àñïåêòå è ðàçëè÷àåò ïóòè
ñ òî÷íîñòüþ äî ïàðàëëåëüíîãî ïåðåíîñà. Ïðåäëîæåííàÿ q-êîäèðîâêà õðàíèò
èíôîðìàöèþ î ôîðìå ïóòè, íî íå î åãî ïîëîæåíèè â ïðîñòðàíñòâå, â ðåçóëü-
òàòå ÷åãî èìååò ïðåèìóùåñòâà ïðè èñïîëüçîâàíèè â àëãîðèòìàõ ðåøåíèÿ çàäà-
÷è ïðîãíîçèðîâàíèÿ òðåòè÷íîé ñòðóêòóðû ïðîòåèíà òàêèõ íàïðèìåð, êàê èì-
ìóííûå àëãîðèòìû èëè àëãîðèòìû îïòèìèçàöèè ìóðàâüèíûìè êîëîíèÿìè
[6–8, 16, 17]). Èñïîëüçîâàíèå êâàòåðíèîíîâ ïîçâîëÿåò ñòðîèòü q-êîäèðîâêè
â òðåõìåðíûõ ðåøåòêàõ, ïðè ýòîì ñóùåñòâåííî ñíèæàåòñÿ òðóäîåìêîñòü âû-
÷èñëèòåëüíûõ ïðîöåäóð, èñïîëüçîâàííûõ ðàíåå [18], ÷òî ïîçâîëÿåò óìåíüøèòü
è òðóäîåìêîñòü àëãîðèòìîâ ðåøåíèÿ çàäà÷è.
Ïðåäëîæåííûå êîäèðîâêè ìîæíî èñïîëüçîâàòü íå òîëüêî â àëãîðèòìàõ ìî-
äåëèðîâàíèÿ è ïðîãíîçèðîâàíèÿ ñòðóêòóðû áåëêîâûõ ìîëåêóë, íî è ïðè ðåøåíèè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 135
äðóãèõ çàäà÷, â êîòîðûõ âîçíèêàåò íåîáõîäèìîñòü èññëåäîâàíèÿ ïðîñòðàíñòâà
òðåõìåðíûõ êðèâûõ, çàäàííûõ â äèñêðåòíîé ðåøåòêå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. D i l l K . A. Theory for the folding and stability of globular proteins // Biochemistry. — 1985. —
N 24(6). — P. 1501–1509.
2. P r i n c i p l e s of protein folding — a perspective from simple exact models / K. Dill, S. Bromberg,
K. Yue at al. // Protein Sci. — 1995. — N 4. — P. 561–602.
3. T h e p r o t e i n folding problem / K.A. Dill, S. Banu Ozkan, M. Scott Shell, T.R. Weikl // Ann.
Rev. Biophysics. — 2008. — N 37. — P. 289–316.
4. O n t h e c o m p l e x i t y of protein folding / P. Crescenzi, D. Goldman, C. Papadimitriou at al. //
J. Comput. Biology. — 1998. — N 5(3). — P. 423–465.
5. I s t r a i l S . , L a m F . Combinatorial algorithms for protein folding in lattice models: a survey of
mathematical results // Commun. Inf. Syst. — 2009. — N 9(4). — P. 303–345.
6. A n i m m u n e algorithm for protein structure prediction on lattice models / V. Cutello, G. Nicosia,
M. Pavone, J. Timmis // IEEE Trans. Evol. Comput. — 2007. — N 11(1). — P. 101–117.
7. S h m y g e l s k a A . , H o o s H . An ant colony optimisation algorithm for the 2D and 3D hydro-
phobic polar protein folding problem // BMC Bioinformatics. — 2005. — N 6(30). — Ð. 30–52.
8. F i d a n o v a S . , L i r k o v I . Ant colony system approach for protein folding // Int. Conf.
Multiconf. Comput. Sci. and Inform. Techn. — 2008. — P. 887–891.
10. G r e e n b e r g H . , H a r t W . , L a n c i a G . Opportunities for combinatorial optimization in
computational biology // INFORMS J. Comput. — 2004. – N 16(3). — P. 211–231.
9. W e i W . , Y a n l i n T . A new algorithm for 2D hydrophobic-polar model: An algorithm based on
hydrophobic core in square lattice // Pak. J. Biol. Sci. — 2008. — N 11. — P. 1815–1819.
11. F e s t a P . Optimization problems in molecular biology: A survey and critical review // Int. Math.
Forum. — 2008. — 3, N 6. — P. 269–289.
12. A n f i s e n C . B . , E d s a l l J . T . , R i c h a r d s F . M . Advances in protein chemistry. — Lon-
don: Acad. Press, 1965. — 369 p.
13. Ã ó ï à ë À . Ì . , Ñ å ð ã è å í ê î È . Â . Îïòèìàëüíûå ïðîöåäóðû ðàñïîçíàâàíèÿ. — Êèåâ:
Íàóê. äóìêà, 2008. — 232 ñ.
14. C o n w a y J . H . , S l o a n e N . J . A Sphere packings, lattices and groups. — New York:
Springer-Verlag, — 1998. — 703 p.
15. K u i p e r s J . B . Quaternions and rotation sequences. — Princeton: Princeton Univ. Press, 1999. —
391 p.
16. O n d i s c r e t e models and immunological algorithms for protein structure prediction / V. Vincenzo
Cutello, G. Morelli, G. Nicosia at al. // Nat. Comput. — 2011. — N 10. — P. 91–102.
17. à ó ë ÿ í è ö ê è é Ë . Ô . , Ð ó ä û ê  . À . Àíàëèç àëãîðèòìîâ ïðîãíîçèðîâàíèÿ òðåòè÷íîé
ñòðóêòóðû ïðîòåèíà íà áàçå ìåòîäà îïòèìèçàöèè ìóðàâüèíûìè êîëîíèÿìè // Problems of
Computer Intellectualization (Eds. V. Velichko, O. Voloshin, K. Markov). — Kiev-Sofia:
V.M. Glushkov Inst. of Cybernetics, ITHEA, 2012. — P. 152–159.
18. Ð ó ä û ê Â . A . Ïðåäñòàâëåíèå ñòðóêòóðû áåëêà â òðåõìåðíûõ äèñêðåòíûõ ðåøåòêàõ
ïðîèçâîëüíîãî òèïà // Òåîð³ÿ îïòèìàëüíèõ ð³øåíü. — 2011. — ¹ 10. — Ñ. 38–47.
Ïîñòóïèëà 24.01.2013
136 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
|