Предсказание структуры генов с использованием смесей вероятностных распределений
Рассмотрена задача восстановления последовательности скрытых состояний для смесей распределений, описываемых обобщениями цепей Маркова произвольного порядка и скрытых марковских моделей. Предложен алгоритм динамического программирования для решения этой задачи, а также его модификации, направленные...
Gespeichert in:
| Datum: | 2015 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/124819 |
| 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: | Предсказание структуры генов с использованием смесей вероятностных распределений / И.В. Сергиенко, А.М. Гупал, А.В. Островский // Кибернетика и системный анализ. — 2015. — Т. 51, № 3. — С. 44-53. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-124819 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1248192025-02-09T10:15:05Z Предсказание структуры генов с использованием смесей вероятностных распределений Прогнозування структури генів з використанням сумішей ймовірнісних розподілів Predicting gene structure with probability distributions Сергиенко, И.В. Гупал, А.М. Островский, А.В. Системный анализ Рассмотрена задача восстановления последовательности скрытых состояний для смесей распределений, описываемых обобщениями цепей Маркова произвольного порядка и скрытых марковских моделей. Предложен алгоритм динамического программирования для решения этой задачи, а также его модификации, направленные на устранение рекурсии и сокращение перебора. Полученные результаты применены к задаче распознавания фрагментов генов в геномах растений. Розглянуто задачу відновлення послідовності прихованих станів для сумішей розподілів, що описуються узагальненнями ланцюгів Маркова довільного порядку і прихованих марковських моделей. Запропоновано алгоритм динамічного програмування для розв’язання цієї задачі, а також його модифікації, що направлені на усунення рекурсії та скорочення перебору. Отримані результати застосовано до задачі розпізнавання фрагментів генів у геномах рослин. The authors consider the problem of recovering hidden state sequences for mixture distributions with constituents described by the generalization of high-order Markov chains and hidden Markov models. A new algorithm to solve the problem using dynamic programming is proposed, as well as its modifications to eliminate recursion and diminish search. The results are applied to the problem of gene fragment recognition in plants. 2015 Article Предсказание структуры генов с использованием смесей вероятностных распределений / И.В. Сергиенко, А.М. Гупал, А.В. Островский // Кибернетика и системный анализ. — 2015. — Т. 51, № 3. — С. 44-53. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/124819 519.217.2 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Сергиенко, И.В. Гупал, А.М. Островский, А.В. Предсказание структуры генов с использованием смесей вероятностных распределений Кибернетика и системный анализ |
| description |
Рассмотрена задача восстановления последовательности скрытых состояний для смесей распределений, описываемых обобщениями цепей Маркова произвольного порядка и скрытых марковских моделей. Предложен алгоритм динамического программирования для решения этой задачи, а также его модификации, направленные на устранение рекурсии и сокращение перебора. Полученные результаты применены к задаче распознавания фрагментов генов в геномах растений. |
| format |
Article |
| author |
Сергиенко, И.В. Гупал, А.М. Островский, А.В. |
| author_facet |
Сергиенко, И.В. Гупал, А.М. Островский, А.В. |
| author_sort |
Сергиенко, И.В. |
| title |
Предсказание структуры генов с использованием смесей вероятностных распределений |
| title_short |
Предсказание структуры генов с использованием смесей вероятностных распределений |
| title_full |
Предсказание структуры генов с использованием смесей вероятностных распределений |
| title_fullStr |
Предсказание структуры генов с использованием смесей вероятностных распределений |
| title_full_unstemmed |
Предсказание структуры генов с использованием смесей вероятностных распределений |
| title_sort |
предсказание структуры генов с использованием смесей вероятностных распределений |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2015 |
| topic_facet |
Системный анализ |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/124819 |
| citation_txt |
Предсказание структуры генов с использованием смесей вероятностных распределений / И.В. Сергиенко, А.М. Гупал, А.В. Островский // Кибернетика и системный анализ. — 2015. — Т. 51, № 3. — С. 44-53. — Бібліогр.: 8 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT sergienkoiv predskazaniestrukturygenovsispolʹzovaniemsmesejveroâtnostnyhraspredelenij AT gupalam predskazaniestrukturygenovsispolʹzovaniemsmesejveroâtnostnyhraspredelenij AT ostrovskijav predskazaniestrukturygenovsispolʹzovaniemsmesejveroâtnostnyhraspredelenij AT sergienkoiv prognozuvannâstrukturigenívzvikoristannâmsumíšejjmovírnísnihrozpodílív AT gupalam prognozuvannâstrukturigenívzvikoristannâmsumíšejjmovírnísnihrozpodílív AT ostrovskijav prognozuvannâstrukturigenívzvikoristannâmsumíšejjmovírnísnihrozpodílív AT sergienkoiv predictinggenestructurewithprobabilitydistributions AT gupalam predictinggenestructurewithprobabilitydistributions AT ostrovskijav predictinggenestructurewithprobabilitydistributions |
| first_indexed |
2025-11-25T18:34:32Z |
| last_indexed |
2025-11-25T18:34:32Z |
| _version_ |
1849788410680573952 |
| fulltext |
È.Â. ÑÅÐÃÈÅÍÊÎ, À.Ì. ÃÓÏÀË, À.Â. ÎÑÒÐÎÂÑÊÈÉ
ÓÄÊ 519.217.2 ÏÐÅÄÑÊÀÇÀÍÈÅ ÑÒÐÓÊÒÓÐÛ ÃÅÍÎÂ
Ñ ÈÑÏÎËÜÇÎÂÀÍÈÅÌ ÑÌÅÑÅÉ
ÂÅÐÎßÒÍÎÑÒÍÛÕ ÐÀÑÏÐÅÄÅËÅÍÈÉ
Àííîòàöèÿ. Ðàññìîòðåíà çàäà÷à âîññòàíîâëåíèÿ ïîñëåäîâàòåëüíîñòè ñêðûòûõ ñîñòîÿíèé
äëÿ ñìåñåé ðàñïðåäåëåíèé, îïèñûâàåìûõ îáîáùåíèÿìè öåïåé Ìàðêîâà ïðîèçâîëüíîãî ïî-
ðÿäêà è ñêðûòûõ ìàðêîâñêèõ ìîäåëåé. Ïðåäëîæåí àëãîðèòì äèíàìè÷åñêîãî ïðîãðàììèðî-
âàíèÿ äëÿ ðåøåíèÿ ýòîé çàäà÷è, à òàêæå åãî ìîäèôèêàöèè, íàïðàâëåííûå íà óñòðàíåíèå
ðåêóðñèè è ñîêðàùåíèå ïåðåáîðà. Ïîëó÷åííûå ðåçóëüòàòû ïðèìåíåíû ê çàäà÷å ðàñïîçíà-
âàíèÿ ôðàãìåíòîâ ãåíîâ â ãåíîìàõ ðàñòåíèé.
Êëþ÷åâûå ñëîâà: öåïü Ìàðêîâà, ñêðûòûå ïåðåìåííûå, ãåí, áèîèíôîðìàòèêà, íóêëåîòèä,
ýêçîí, èíòðîí, ïðàâäîïîäîáèå.
ÂÂÅÄÅÍÈÅ
Çàäà÷à îïðåäåëåíèÿ ìåñòîïîëîæåíèÿ ãåíîâ â ÄÍÊ è ïðåäñêàçàíèÿ èõ âíóòðåí-
íåé ñòðóêòóðû ÿâëÿåòñÿ îäíèì èç íàèáîëåå âîñòðåáîâàííûõ ïðèëîæåíèé áèî-
èíôîðìàòèêè. Äëÿ åå ðåøåíèÿ èñïîëüçóþòñÿ ìåòîäû íà îñíîâå îáîáùåííûõ
ìîäåëåé Ìàðêîâà ñî ñêðûòûìè ïåðåìåííûìè [1], îáëàäàþùèå îïðåäåëåííûìè
íåäîñòàòêàìè — ÷ðåçìåðíîé ñïåöèôè÷íîñòüþ è ñëîæíîñòüþ èíòåðïðåòàöèè.
 [2] ïðåäëîæåí àëüòåðíàòèâíûé ïîäõîä ê ðàñïîçíàâàíèþ âíóòðåííåé ñòðóê-
òóðû ãåíîâ, îñíîâàííûé íà ñî÷åòàíèè ñêðûòûõ ìàðêîâñêèõ ìîäåëåé è öåïåé
Ìàðêîâà âûñøèõ ïîðÿäêîâ; åãî ïðèìåíåíèå äëÿ ãåíîìîâ ðàñòåíèé è íàñåêîìûõ
ïî ýôôåêòèâíîñòè ñðàâíèìî ñ àêòóàëüíûìè íà ñåãîäíÿøíèé äåíü àëãîðèòìàìè.
Äëÿ ïîâûøåíèÿ êà÷åñòâà ðàñïîçíàâàíèÿ ãåíîìîâ âûñøèõ îðãàíèçìîâ (íà-
ïðèìåð, ìëåêîïèòàþùèõ) âîçìîæíî èñïîëüçîâàíèå êîìïîçèöèé ìîäåëåé ñ ýêñ-
êëþçèâíîé êîìïåòåíòíîñòüþ, â êîòîðûõ êàæäûé ãåí ðàñïîçíàåòñÿ ñòðîãî îäíîé
èç ñîñòàâëÿþùèõ ìîäåëåé, ïîäáèðàþùåéñÿ èñõîäÿ èç ïîñëåäîâàòåëüíîñòè åãî
íóêëåîòèäîâ.  [3] â êà÷åñòâå ïðèçíàêîâ, ïî êîòîðûì ïðîèñõîäèò ðàçáèåíèå
íà îáëàñòè êîìïåòåíòíîñòè, ðàññìàòðèâàþòñÿ êîíöåíòðàöèè íóêëåîòèäîâ; â [4]
òàêîå ðàçáèåíèå ñòðîèòñÿ íà îñíîâå EM-àëãîðèòìà ñ ïîñëåäóþùåé àïïðîêñèìà-
öèåé ñ ïîìîùüþ ìåòîäà îïîðíûõ âåêòîðîâ (SVM). Ýêñêëþçèâíîñòü îáëàñòåé êîì-
ïåòåíòíîñòè ïîçâîëÿåò ðåøàòü çàäà÷ó âîññòàíîâëåíèÿ ñòðóêòóðû ãåíà òàêèì æå îá-
ðàçîì, êàê è â ñëó÷àå èñïîëüçîâàíèÿ îäíîé ìîäåëè; îäíàêî ýòî òðåáîâàíèå ïðèâîäèò
ê ñóæåíèþ êëàññà ðàññìàòðèâàåìûõ ðàñïðåäåëåíèé è, ïîòåíöèàëüíî, ê ñíèæåíèþ
êà÷åñòâà ðàñïîçíàâàíèÿ.  ñâÿçè ñ ýòèì â äàííîé ñòàòüå ðàññìàòðèâàåòñÿ àëãîðèòì,
êîòîðûé ðàáîòàåò íåïîñðåäñòâåííî ñî ñìåñÿìè âåðîÿòíîñòíûõ ðàñïðåäåëåíèé.
1. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È
Ïóñòü çàäàíà ñòðîêà S RsÎ * , îòäåëüíûå ñèìâîëû êîòîðîé ïðèíàäëåæàò ìíîæåñ-
òâó íàáëþäàåìûõ ñèìâîëîâ Rs. Èçâåñòíî, ÷òî êàæäûé ñèìâîë ñòðîêè ïîðîæäåí
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
© È.Â. Ñåðãèåíêî, À.Ì. Ãóïàë, À.Â. Îñòðîâñêèé, 2015
ñòðîãî îäíèì ñèìâîëîì èç ìíîæåñòâà ñêðûòûõ ñèìâîëîâ Rh , ò.å. S ñîîòâåòñòâóåò
ïîñëåäîâàòåëüíîñòü H RhÎ * òîé æå äëèíû; â åå íàõîæäåíèè è çàêëþ÷àåòñÿ çàäà-
÷à, êîòîðàÿ ñîãëàñíî ïðèíöèïó ìàêñèìóìà ïðàâäîïîäîáèÿ èìååò âèä
log ( | ) maxP H S
H
® . (1)
Äëÿ ðàññìàòðèâàåìîé ïðîáëåìû îïðåäåëåíèÿ ôðàãìåíòîâ ãåíîâ ìíîæåñòâî
íàáëþäàåìûõ ñèìâîëîâ ñîñòîèò èç ÷åòûðåõ ýëåìåíòîâ; ýòè ñèìâîëû
ñîîòâåòñòâóþò íóêëåîòèäàì (àäåíèíó, öèòîçèíó, ãóàíèíó è òèìèíó), èç ïîñëåäî-
âàòåëüíîñòè êîòîðûõ ñîñòîÿò ãåíû. Îñíîâíûìè ôóíêöèîíàëüíûìè ôðàãìåíòàìè
ëþáîãî ãåíà ÿâëÿþòñÿ ÷åðåäóþùèåñÿ ìåæäó ñîáîé ýêçîíû (ó÷àñòêè, êîäèðóþ-
ùèå îïðåäåëåííûé áåëîê îðãàíèçìà ñ ïîìîùüþ óíèâåðñàëüíîãî ãåíåòè÷åñêîãî
êîäà) è èíòðîíû (ðàñïîëîæåííûå ìåæäó ýêçîíàìè ó÷àñòêè, íå ïðèíèìàþùèå
ó÷àñòèÿ â ñèíòåçå áåëêà) [4]. Ñîîòâåòñòâåííî ìíîæåñòâî ñêðûòûõ ñèìâîëîâ Rh
ñîñòîèò èç äâóõ ýëåìåíòîâ.
Óïîðÿäî÷åííûå ïàðû èç íàáëþäàåìûõ è ñîîòâåòñòâóþùèõ èì ñêðûòûõ ñèì-
âîëîâ íàçîâåì ïîëíûìè ñîñòîÿíèÿìè. Äëÿ ñòðîêè ïîëíûõ ñîñòîÿíèé Q RqÎ * , ãäå
R R Rq s hº ´ , îïðåäåëåíû ôóíêöèè, âîçâðàùàþùèå åå íàáëþäàåìóþ è ñêðûòóþ ÷àñòè:
prs Q S( ) = ; prh Q H( ) = .
Ñ ó÷åòîì ââåäåííûõ îáîçíà÷åíèé çàäà÷à (1) ýêâèâàëåíòíà ñëåäóþùåìó ñîîò-
íîøåíèþ:
log ( ) maxP Q
Q
® , prs Q S( ) = . (2)
 ñîîòâåòñòâèè ñ îáùåé ôîðìóëèðîâêîé çàäà÷è îáó÷åíèÿ ñ ïðåöåäåíòàìè
äëÿ îïðåäåëåíèÿ îïòèìàëüíûõ ïàðàìåòðîâ q * âåðîÿòíîñòíîãî ðàñïðåäåëåíèÿ
P Q( ) èñïîëüçóåòñÿ êîíå÷íûé íàáîð ñòðîê (îáó÷àþùàÿ âûáîðêà) T RqÌ * , äëÿ êî-
òîðûõ èçâåñòíû êàê íàáëþäàåìàÿ, òàê è ñêðûòàÿ ÷àñòè. Èç ïðèíöèïà ìàêñèìóìà
ïðàâäîïîäîáèÿ ñëåäóåò
q q
q
* arg max log ( | )=
Î
å P Q
Q T
. (3)
 ðàáîòàõ [2, 5] äëÿ ôóíêöèè ïðàâäîïîäîáèÿ P Q( ) èñïîëüçóåòñÿ ôîðìóëà
äëÿ öåïè Ìàðêîâà ïðîèçâîëüíîãî l-ãî ïîðÿäêà
P Q Q Q Q p Q Q Ql i i l i
i l
Q
( ) (| | ) ( ) ( | )
| |
= - -
= +
Õj p 1 1
1
K K , (4)
ãäå j — ôóíêöèÿ ðàñïðåäåëåíèÿ ñòðîê ïî äëèíå, p — ðàñïðåäåëåíèå íà÷àëü-
íûõ âåðîÿòíîñòåé, p — ðàñïðåäåëåíèå ïåðåõîäíûõ âåðîÿòíîñòåé; òàêèì îáðà-
çîì, ïàðàìåòðàìè ìîäåëè ÿâëÿåòñÿ òðîéêà ôóíêöèé q j p= ( , , )p . Ðåøåíèå çàäà÷è
(2) ñ ó÷åòîì (4) ìîæíî íàéòè ñ ïîìîùüþ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ; ïðè
ýòîì èç (3) ñëåäóåò, ÷òî îïòèìàëüíûå íà÷àëüíûå è ïåðåõîäíûå âåðîÿòíîñòè ìîäå-
ëè íàõîäÿòñÿ êàê ÷àñòîòû âñòðå÷è ñîîòâåòñòâóþùèõ ïîñëåäîâàòåëüíîñòåé â ñòðîêàõ
îáó÷àþùåé âûáîðêè.
 ðàáîòàõ [3, 4] ðàññìîòðåíà ôóíêöèÿ ïðàâäîïîäîáèÿ â âèäå ñìåñè ðàñïðå-
äåëåíèé
P Q w P Qw j j
j
k
( ) ( | )=
=
å q
1
, w j ³ 0, w j
j
k
=
å =
1
1 , (5)
ãäå w j — àïðèîðíûé âåñ j-é ìîäåëè, P Q j( |q ) — ôóíêöèÿ ðàñïðåäåëåíèÿ, îïðå-
äåëÿåìàÿ ïî ôîðìóëå (4); ïàðàìåòðàì ñîñòàâíîé ìîäåëè ñîîòâåòñòâóåò âåêòîð
Q = =( , ; ; , ) ( , , , ; ; , , , )w w w p w pk k k k k k1 1 1 1 1 1q q j p j pK K .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 45
Óñëîâèå ýêñêëþçèâíîé êîìïåòåíòíîñòè ñîñòàâëÿþùèõ êîìïîçèöèè
" ÎQ Rq
* $ £ £j j k:1 P Qj( | )q = 1 (6)
ïðèâîäèò ê «ñõëîïûâàíèþ» ôóíêöèè (5) ê âèäó
P Q w P Qj j( ) ( | )= q , j j Qs= ( ( ))pr , (7)
ò.å. ïîëàãàåòñÿ, ÷òî èíäåêñ ìîäåëè ìîæíî íàéòè ñ ïîìîùüþ íàáëþäàåìîé ÷àñ-
òè ðàññìàòðèâàåìîé ñòðîêè. Çàäà÷à ìàêñèìèçàöèè ôóíêöèè ïðàâäîïîäîáèÿ (2)
ïðè âûïîëíåíèè ðàâåíñòâà (7) àíàëîãè÷íà òàêîé çàäà÷å ïðè èñïîëüçîâàíèè
åäèíñòâåííîé ìîäåëè (4).
 ðàáîòå [3] óñëîâèå (6) äîñòèãàåòñÿ çà ñ÷åò ìîäèôèêàöèè ôóíêöèè ðàñïðåäå-
ëåíèÿ (4) òàêèì îáðàçîì, ÷òîáû ìíîæåñòâî ãåíåðèðóåìûõ èì ñòðîê îãðàíè÷èâà-
ëîñü íåêîòîðîé îáëàñòüþ; ýòî ïðè îïðåäåëåííûõ óñëîâèÿõ íå âëèÿåò íà ñïîñîá ðå-
øåíèÿ çàäà÷è íàõîæäåíèÿ ïàðàìåòðîâ ìîäåëè (3) ïî ñðàâíåíèþ ñ ïðèìåíåíèåì
îäíîãî ðàñïðåäåëåíèÿ. Â [4], íàïðîòèâ, â êîìïîçèöèè èñïîëüçóþòñÿ èñõîäíûå
ìîäåëè (4), à äëÿ íàõîæäåíèÿ èõ îïòèìàëüíûõ ïàðàìåòðîâ ïðèìåíÿåòñÿ èòåðà-
òèâíûé EM-àëãîðèòì, ïî ðåçóëüòàòàì êîòîðîãî óñëîâèå (6) âûïîëíÿåòñÿ ñ äîñòà-
òî÷íî âûñîêîé òî÷íîñòüþ. Ïðè ýòîì äëÿ îïðåäåëåíèÿ îáëàñòè êîìïåòåíòíîñòè
ïî íàáëþäàåìîé ÷àñòè ñòðîêè Q èñïîëüçóåòñÿ SVM.
Íåñìîòðÿ íà ýôôåêòèâíîñòü îïèñàííîãî âûøå ïîäõîäà, óñëîâèå èçîëèðîâàí-
íîñòè îáëàñòåé êîìïåòåíòíîñòè (7) äàæå ïðè òî÷íîì ïðèáëèæåííîì âûïîëíåíèè (6)
ÿâëÿåòñÿ íåñêîëüêî èñêóññòâåííûì è íå ñëåäóåò èç êàêèõ-ëèáî àïðèîðíûõ ñîîá-
ðàæåíèé. Ðàññìîòðèì äàëåå èñõîäíóþ çàäà÷ó âîññòàíîâëåíèÿ ïîñëåäîâàòåëüíîñ-
òè ïîëíûõ ñîñòîÿíèé äëÿ ñìåñè ðàñïðåäåëåíèé
log ( ) log ( | ) maxP Q w P Qw j j
j
k
=
æ
è
ç
ç
ö
ø
÷
÷
®
=
å q
q1
, prs Q S( ) = . (8)
Ïðè ýòîì âåñà ñîñòàâëÿþùèõ ìîäåëåé w º ( , , )w wk1 K è èõ ïàðàìåòðû
{ }( , , )j pj j j j
kp =1
ïîëàãàåì çàäàííûìè.
2. ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß
Äëÿ ïðîèçâîëüíîé ñòðîêè x RqÎ * , ñèìâîëà y RqÎ è íåîòðèöàòåëüíûõ âåñîâ
u º ( , , )u uk1 K ñïðàâåäëèâî ðàâåíñòâî
log ( | ) log ( | ) ( | )u P xy u P x p y xj j
j
k
j j j
j
k
q q
= =
å
æ
è
ç
ç
ö
ø
÷
÷
=
1 1
å
æ
è
ç
ç
ö
ø
÷
÷
=
=
æ
è
ç
ç
ö
ø
÷
÷
+
=
ålog ~ ( | ) logu P x Cj j
j
k
q
1
, (9)
ãäå
C C x y u p y xj j
j
k
= =
=
å( , , ) ( | )u
1
" =j k1, ,K , ~ ~ ( , , )
( | )
u u x y
u p y x
C
j j
j j= =u . (10)
Ïóñòü F i x( , , )u — ìàêñèìóì äëÿ çàäà÷è (8) äëÿ ïðåôèêñà ñòðîêè Q äëèíû i l>
è âåñîâ ñîñòàâëÿþùèõ ìîäåëåé u ïðè äîïîëíèòåëüíîì óñëîâèè, ÷òî ïîñëåäíèå l
åå ïîëíûõ ñîñòîÿíèé ôèêñèðîâàíû:
F i x u P Q Qj i j
j
k
( , , ) maxlog ( | )u =
æ
è
ç
ç
ö
ø
÷
÷
=
å 1
1
K q , prs Q S( ) = , Q Q xi l i- + =1 K . (11)
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
Òîãäà ñîãëàñíî (9)
F i x F i yx x x y
y
l( , , ) max ( , , ~ ( , , ))u u u= - +
æ
è
ç
ç -1 1 1K
+
æ
è
ç
ç
ö
ø
÷
÷
ö
ø
÷
÷-
=
ålog ( | )u p x yx xj j l l
j
k
1 1
1
K , (12)
ãäå ìàêñèìóì áåðåòñÿ ïî ïîëíûì ñîñòîÿíèÿì y RqÎ , ñîîòâåòñòâóþùèì íàáëþäàå-
ìîé ñòðîêå: prs i ly S( ) = - ; âåñà ~ (~ , , ~ )u = u uk1 K âû÷èñëÿþòñÿ ïî ôîðìóëå (10). Òà-
êèì îáðàçîì, ðåøåíèå çàäà÷è (11) îïðåäåëÿåòñÿ ðåøåíèåì íåñêîëüêèõ ïîäîáíûõ çà-
äà÷ ìåíüøåãî ðàçìåðà, ÷òî ïîçâîëÿåò ðåøàòü åå ìåòîäîì äèíàìè÷åñêîãî ïðîãðàì-
ìèðîâàíèÿ, òàê æå êàê ïðè èñïîëüçîâàíèè ôóíêöèè ïðàâäîïîäîáèÿ (4). Ãðàíè÷íûìè
óñëîâèÿìè ïðè ðåêóðñèâíîì âû÷èñëåíèè ôóíêöèè F ïî ôîðìóëå (12) ÿâëÿþòñÿ ðà-
âåíñòâà âèäà
F l x u xj j
j
k
( , , ) log ( )u =
æ
è
ç
ç
ö
ø
÷
÷
=
å p
1
. (13)
Ïðè îïèñàííîì ñïîñîáå âû÷èñëåíèÿ ôóíêöèè (11) îïðåäåëåíèå ðåøåíèÿ èñ-
õîäíîé çàäà÷è (8) òðèâèàëüíî:
max log ( ) max (| | , , )P Q F Q xw
x
= w , (14)
ãäå ïåðåáîð âûïîëíÿåòñÿ ïî ñòðîêàì ïîëíûõ ñîñòîÿíèé x äëèíû l, êîòîðûå
ñîîòâåòñòâóþò ñóôôèêñó íàáëþäàåìîé ñòðîêè S: prs S l Sx S S( ) | | | |= - +1 K .
Îïòèìàëüíîå ðåøåíèå Q âîññòàíàâëèâàåòñÿ ïóòåì çàïîìèíàíèÿ îïòèìàëüíûõ
ïîëíûõ ñîñòîÿíèé ïðè âû÷èñëåíèè ìàêñèìóìîâ (12) è (14).
 îòëè÷èå îò çàäà÷è, ðàññìîòðåííîé â [5], ôîðìóëû (12)–(14) íå ïîçâîëÿþò
âû÷èñëèòü ðåêóððåíòíóþ ôóíêöèþ F i x( , , )u , èòåðàòèâíî íàðàùèâàÿ ðàçìåðíîñòü
çàäà÷è, ò.å. ïåðåìåííóþ i. Äâà ïåðâûõ ïàðàìåòðà ôóíêöèè ïðèíèìàþò êîíå÷íîå
êîëè÷åñòâî çíà÷åíèé ( | |l i S£ £ , x Rq
lÎ ), à ìíîæåñòâî âåñîâ u èìååò ìîùíîñòü
êîíòèíóóìà è íå ìîæåò áûòü ïðåäñêàçàíî àïðèîðíî (çà èñêëþ÷åíèåì òðèâèàëü-
íîãî ñëó÷àÿ, êîãäà êîìïîçèöèÿ ñîñòîèò èç îäíîé ìîäåëè). Òàêèì îáðàçîì, âîç-
ìîæíûì ñïîñîáîì âû÷èñëåíèÿ ôóíêöèè F ÿâëÿåòñÿ íåïîñðåäñòâåííàÿ èìïëå-
ìåíòàöèÿ ðåêóððåíòíîé ôîðìóëû (12) ñ çàïîìèíàíèåì ïðîìåæóòî÷íûõ çíà÷å-
íèé. Ïðè ýòîì íà÷àëüíîìó ýòàïó ðàáîòû àëãîðèòìà ñîãëàñíî ôîðìóëå (14)
ñîîòâåòñòâóåò ñëåäóþùèé ïñåâäîêîä.
Àëãîðèòì 1. Îïðåäåëåíèå ñòðîêè Q ñ ðåêóðñèåé.
Äàíî: íàáëþäàåìàÿ ñòðîêà S , âåñà ìîäåëåé w, ïàðàìåòðû ìîäåëåé
{ }( , , )j pj j j j
kp =1
.
1. M:= Æ ; — êýø-ïàìÿòü äëÿ õðàíåíèÿ çíà÷åíèé ôóíêöèè F;
2. äëÿ âñåõ x Rq
lÎ , prs S l Sx S S( ) | | | |= - +1 K :
3. ( [ ], [ ] ) : (| | , , )F x Q x FR Q x- = w ;
4. x F x
x
* : arg max [ ]= - ;
5. âåðíóòü Q x x[ ]* *.
Çäåñü ïîëàãàåòñÿ, ÷òî ðåêóðñèâíàÿ ïðîöåäóðà FR i x( , , )u âîçâðàùàåò, ïîìèìî
çíà÷åíèÿ ôóíêöèè F äëÿ ñîîòâåòñòâóþùåãî íàáîðà àðãóìåíòîâ, îïòèìàëüíóþ
ïîñëåäîâàòåëüíîñòü ïîëíûõ ñîñòîÿíèé Q Qi l1 K - , âîññòàíîâëåííóþ çà ñ÷åò çàïî-
ìèíàíèÿ çíà÷åíèé ïåðåìåííîé y, êîòîðûå ìàêñèìèçèðóþò (12).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 47
Àëãîðèòì 2. Ïðîöåäóðà FR i x( , , )u .
1. åñëè i l= :
2. âû÷èñëèòü çíà÷åíèå ôóíêöèè F ïî ôîðìóëå (13);
3. âåðíóòü ( , )F e (e — ïóñòàÿ ñòðîêà);
4. èíà÷å: åñëè ( , , )i x u íåò â êýø-ïàìÿòè M:
5. äëÿ âñåõ y RqÎ , prs i ly S( ) = - :
6. ( [ ], [ ]) : ( , , ~( , , ))F y Q y FR i yx x x yl
-
-= -1 1 1K u u ;
7. íàéòè îïòèìàëüíîå ñîñòîÿíèå y* è çíà÷åíèå ôóíêöèè F ñîãëàñíî ôîðìóëå (12),
èñõîäÿ èç âû÷èñëåííûõ çíà÷åíèé F - ;
8. çàíåñòè îïòèìóì â êýø-ïàìÿòü: M i x F Q y y[ , , ] : ( , [ ] )* *u = ;
9. âåðíóòü M i x[ , , ]u — çíà÷åíèå èç êýø-ïàìÿòè.
3. ÌÎÄÈÔÈÊÀÖÈÈ È ÝÂÐÈÑÒÈÊÈ
Ïîñêîëüêó ìíîæåñòâî ðàçëè÷íûõ ðàññìàòðèâàåìûõ âåñîâ äëÿ êàæäîãî íàáîðà
âåëè÷èí ( , )i x áûñòðî ðàñòåò ñ óìåíüøåíèåì i, íåïîñðåäñòâåííîå èñïîëüçîâà-
íèå ïðèâåäåííîãî àëãîðèòìà äëÿ äëèííûõ ñòðîê S íå ïðåäñòàâëÿåòñÿ âîçìîæ-
íûì. Ýòî îãðàíè÷åíèå ìîæíî îáîéòè, åñëè ïðåäïîëîæèòü, ÷òî äëÿ áëèçêèõ
âåêòîðîâ âåñîâ u çíà÷åíèÿ ôóíêöèè F òàêæå ìàëî îòëè÷àþòñÿ:
r r( , ) minu u ¢ £ Þ F i x F i x( , , ) ( , , )u u» ¢ , (15)
ãäå ìåòðèêà r ñîîòâåòñòâóåò ïðîñòðàíñòâó îãðàíè÷åííûõ ïîñëåäîâàòåëüíîñòåé l
¥ :
r( , ) max| |u u ¢ = - ¢
£ £1 j k
u uj j .
Èñõîäÿ èç ýâðèñòèêè, åñëè ïðè âûçîâå ïðîöåäóðû FR i x( , , )u â êýø-ïàìÿòè M
ñîäåðæèòñÿ ðåçóëüòàò ðàáîòû ïðîöåäóðû äëÿ òåõ æå ïàðàìåòðîâ ( , )i x è áëèçêîãî
ê u âåêòîðà âåñîâ, òî äàëüíåéøèõ âûçîâîâ ïðîöåäóðû íå ïðîèñõîäèò, à âìåñòî
ýòîãî íåìåäëåííî âîçâðàùàåòñÿ ñîõðàíåííîå çíà÷åíèå. ×åì ìåíüøå ïîðîãîâîå
ðàññòîÿíèå rmin , òåì òî÷íåå àïïðîêñèìàöèÿ (15) è ñîîòâåòñòâåííî íèæå ñêîðîñòü
ðàáîòû àëãîðèòìà è âûøå îáúåì ïîòðåáëÿåìîé èì ïàìÿòè. Çíà÷åíèå rmin = 0 îò-
âå÷àåò èñõîäíîìó àëãîðèòìó.
Ïðè ðåàëèçàöèè êýø-ïàìÿòè M â âèäå õýø-òàáëèöû ïðîñòåéøèì ñïîñîáîì
ðåàëèçàöèè ýâðèñòèêè ÿâëÿåòñÿ èñïîëüçîâàíèå â êà÷åñòâå êëþ÷åé òàáëèöû îáúåê-
òîâ, äëÿ êîòîðûõ õýø-ôóíêöèÿ íå çàâèñèò îò âåñîâ u, à îïåðàöèÿ ðàâåíñòâà ó÷èòû-
âàåò ôîðìóëó (15):
hash i x( , , ) ( )u u= const ;
( , , ) ~ ( , , ) ( ) ( ) ( ( , ) )mini x i x i i x xu u u u¢ ¢ ¢ Û = ¢ Ù = ¢ Ù ¢ £r r .
Íåäîñòàòîê òàêîãî ïîäõîäà — âûñîêîå êîëè÷åñòâî êîëëèçèé ïî õýø-ôóíêöèè;
òåì íå ìåíåå äëÿ ðàññìàòðèâàåìîé çàäà÷è îí îêàçàëñÿ äîñòàòî÷íî ýôôåêòèâíûì.
Ãëóáèíà ñòåêà âûçîâîâ ïðîöåäóðû FR ñîñòàâëÿåò Q(| | )S , ÷òî ìîæåò ïðèâåñ-
òè ê åãî ïåðåïîëíåíèþ. Áîëåå òîãî, ïîñêîëüêó ðåçóëüòàò êàæäîãî âûçîâà ñîäåð-
æèò ñòðîêó äëèíû Q(| | )S , òðåáóåìûé àëãîðèòìîì îáúåì ïàìÿòè ñîñòàâëÿåò ïî-
ðÿäêà | |S 2 , ÷òî íåäîïóñòèìî ìíîãî äàæå äëÿ ñîâðåìåííûõ îïåðàöèîííûõ ñðåä.
Äëÿ ðåøåíèÿ ýòèõ ïðîáëåì íåîáõîäèì ïåðåõîä ê íåðåêóðñèâíîìó âû÷èñëåíèþ
ôóíêöèè F çà ñ÷åò èñïîëüçîâàíèÿ î÷åðåäè âûçîâîâ, ðåàëèçîâàííîé â âèäå ëèíåé-
íîãî ìàññèâà. Ïðè ýòîì êàæäûé ýëåìåíò î÷åðåäè ñîîòâåòñòâóåò îòäåëüíîìó âû-
çîâó ïðîöåäóðû FR ñ îïðåäåëåííûì íàáîðîì ïàðàìåòðîâ è ÿâëÿåòñÿ îáúåêòîì ñî
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
ñëåäóþùèì íàáîðîì ïîëåé:
· i x, , u — àðãóìåíòû âûçîâà;
· F — çíà÷åíèå ôóíêöèè;
· y*— îïòèìàëüíîå ïîëíîå ñîñòîÿíèå ïðè âû÷èñëåíèè ôóíêöèè ïî ôîðìóëå (12);
· ch — ìàññèâ èç èíäåêñîâ ýëåìåíòîâ î÷åðåäè, îòâå÷àþùèõ äî÷åðíèì âûçî-
âàì, íåîáõîäèìûì äëÿ âû÷èñëåíèÿ F .
Ðàçìåð îáúåêòà, òàêèì îáðàçîì, ñîñòàâëÿåò O k Rh( | | )+ . Êýø-ïàìÿòü â ðàìêàõ ìî-
äèôèêàöèè ïðèìåíÿåòñÿ äëÿ çàïîìèíàíèÿ è ïîñëåäóþùåãî èñïîëüçîâàíèÿ íîìåðîâ
ýëåìåíòîâ î÷åðåäè, ñîîòâåòñòâóþùèõ ðàçëè÷íûì íàáîðàì àðãóìåíòîâ ( , , )i x u .
Îïðåäåëåíèå îïòèìàëüíîé ñòðîêè Q ñîñòîèò èç äâóõ ýòàïîâ, ïåðâûì èç êîòî-
ðûõ ÿâëÿåòñÿ ôîðìèðîâàíèå î÷åðåäè âûçîâîâ è óñòàíîâëåíèå ñâÿçåé ìåæäó åå
ýëåìåíòàìè.
Àëãîðèòì 3. Îïðåäåëåíèå ñòðîêè Q áåç ðåêóðñèè (ïðÿìîé õîä).
1. èíèöèàëèçèðîâàòü î÷åðåäü: q:= Æ ;
2. äëÿ âñåõ x Rq
lÎ , prs S l Sx S S( ) | | | |= - +1 K :
3. äîáàâèòü â q âûçîâ ñ ïàðàìåòðàìè (| | , , )S x w ;
4. ïîêà â î÷åðåäè åñòü íåðàññìîòðåííûå ýëåìåíòû:
5. âçÿòü èç q ïåðâûé íåðàññìîòðåííûé ýëåìåíò e ;
6. åñëè e i l. = :
7. âû÷èñëèòü çíà÷åíèå e F. ïî ôîðìóëå (13) ;
8. èíà÷å:
9. äëÿ âñåõ y RqÎ , prs i ly S( ) = - :
10. îïðåäåëèòü ïàðàìåòðû íîâîãî âûçîâà ( . , ~, ~)e i x-1 u ;
11. åñëè ( . , ~, ~)e i x-1 u íåò â êýø-ïàìÿòè M:
12. äîáàâèòü â q ýëåìåíò ñ àðãóìåíòàìè ( . , ~, ~)e i x-1 u ;
13. M e i x q[ . , ~, ~]: | |- =1 u ;
14. çàïîìíèòü ññûëêó íà äî÷åðíèé âûçîâ: e ch y M e i x. [ ] : [ . , ~, ~]= -1 u .
Âòîðûì ýòàïîì ðàáîòû àëãîðèòìà ÿâëÿåòñÿ âû÷èñëåíèå ïî ñîñòàâëåííîìó
äåðåâó âûçîâîâ çíà÷åíèé ðåêóððåíòíîé ôóíêöèè è îïðåäåëåíèå íà èõ îñíîâå
îïòèìàëüíîé ñêðûòîé ñòðîêè.
Àëãîðèòì 4. Îïðåäåëåíèå ñòðîêè Q áåç ðåêóðñèè (îáðàòíûé õîä).
1. äëÿ j q q= -| | , | | , ,1 1K :
2. eñëè e i. > 1:
3. âû÷èñëèòü e F. ïî ôîðìóëå (12) èñõîäÿ èç çíà÷åíèé { }q e ch y F[ . [ ]].
è îïðåäåëèòü e y. * ;
4. íàéòè ýëåìåíò î÷åðåäè, ñîîòâåòñòâóþùèé âûçîâó âèäà FR S x(| | , , )w
ñ îïòèìàëüíûì çíà÷åíèåì x Rq
lÎ :
ptr arg q j F
j
: max [ ].= , 1 £ £j Rq
l| |;
5. âîññòàíîâèòü ñóôôèêñ ñòðîêè Q : Q Q q ptr xS l S| | | |: [ ].- + =1 K ;
6. ïîêà ptr > 0 :
7. e q ptr: [ ]= ; ptr e ch e y: . [ . ]*= ;
8. Q e ye i.
*: .= .
Ìåòîäîì ìàòåìàòè÷åñêîé èíäóêöèè ìîæíî ïîêàçàòü, ÷òî ýëåìåíòû î÷åðåäè
ðàñïîëîæåíû ïî íåâîçðàñòàíèþ äëèíû i:
" ¢ £ < ¢ £ Þ ³ ¢j j j j q q j i q j i, : | | [ ]. [ ].1 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 49
Ñëåäîâàòåëüíî, èíäåêñû äî÷åðíèõ âûçîâîâ ëþáîãî ýëåìåíòà áîëüøå èíäåêñà
ñàìîãî ýëåìåíòà:
" £ £j j q: | |1 q j ch y j[ ]. [ ]> ,
ïîýòîìó íà øàãå 3 àëãîðèòìà 4 çíà÷åíèÿ { }q e ch y F[ . [ ]]. âû÷èñëåíû ðàíåå, ÷òî
ñâèäåòåëüñòâóåò î êîððåêòíîñòè îïðåäåëåíèÿ çíà÷åíèé ôóíêöèè F äëÿ âñåõ
îáúåêòîâ â î÷åðåäè q çà îäèí ïðîõîä.
Ñëîæíîñòü àëãîðèòìà 3 îïðåäåëÿåòñÿ äâóìÿ âëîæåííûìè öèêëàìè íà øàãàõ
4 è 9. Ñëîæíîñòü îïðåäåëåíèÿ ïàðàìåòðîâ íîâîãî âûçîâà ôóíêöèè íà øàãå 10 ñî-
ñòàâëÿåò O k( ). Ñëåäîâàòåëüíî, ïðè óñëîâèè, ÷òî äîñòóï ê ýëåìåíòàì êýø-ïàìÿòè
îñóùåñòâëÿåòñÿ â ñðåäíåì çà O( )1 , âðåìåííûå çàòðàòû íà àëãîðèòì 3 ðàâíû
O k q Rh( | | | | ). Ñëîæíîñòü àëãîðèòìà 4 ñîñòàâëÿåò O k q( | | ) çà ñ÷åò öèêëà íà øàãå 1;
òàêèì îáðàçîì, îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü âîññòàíîâëåíèÿ öåïî÷êè ïîë-
íûõ ñîñòîÿíèé ðàâíà O k q Rh( | | | | ). Ïàìÿòü, èñïîëüçóåìàÿ àëãîðèòìîì, îïðåäåëÿ-
åòñÿ îáúåìîì õýø-òàáëèöû è ñîñòàâëÿåò O k R qh(( | | )| | )+ .
 îáåèõ îöåíêàõ ñëîæíîñòè ó÷èòûâàåòñÿ ðàçìåð î÷åðåäè ïîñëå çàâåðøåíèÿ ïðÿ-
ìîãî õîäà âû÷èñëåíèé — | |q ; âûðàçèòü åãî ÷åðåç äðóãèå ïåðåìåííûå íå ïðåäñòàâëÿåò-
ñÿ âîçìîæíûì èç-çà ñèëüíîé çàâèñèìîñòè îò ãðàíè÷íîãî ðàññòîÿíèÿ rmin . Íèæíåé
ãðàíèöåé äëÿ | |q â îáùåì ñëó÷àå ÿâëÿåòñÿ êîëè÷åñòâî ðàçëè÷íûõ íàáîðîâ ( , )i x , äëÿ
êîòîðûõ âû÷èñëÿåòñÿ ôóíêöèÿ F : | | | | | |q S R
h
l³ × . Ýòó îöåíêó ìîæíî óëó÷øèòü, åñëè
ïîñëå îïðåäåëåíèÿ ïàðàìåòðîâ äî÷åðíåãî âûçîâà íà øàãå 10 àëãîðèòìà 3 äîáàâëÿòü
ýëåìåíò â î÷åðåäü òîëüêî â òîì ñëó÷àå, êîãäà çíà÷åíèå âåëè÷èíû C, âû÷èñëåííîé ïî
ôîðìóëå (10), ÿâëÿåòñÿ ñòðîãî ïîëîæèòåëüíûì; â ïðîòèâíîì ñëó÷àå çíà÷åíèå ôóíê-
öèè ãàðàíòèðîâàííî ðàâíî - ¥. Äëÿ ðàññìàòðèâàåìîé çàäà÷è ðàñïîçíàâàíèÿ ôðàãìåí-
òîâ ãåíîâ ýòà ìîäèôèêàöèÿ ÿâëÿåòñÿ îñîáåííî ýôôåêòèâíîé, òàê êàê áîëüøèíñòâî ïå-
ðåõîäíûõ âåðîÿòíîñòåé â ñîñòàâëÿþùèõ êîìïîçèöèþ ìîäåëÿõ ðàâíî íóëþ.
4. ÂÛ×ÈÑËÈÒÅËÜÍÛÉ ÝÊÑÏÅÐÈÌÅÍÒ
Äëÿ îïðåäåëåíèÿ êà÷åñòâà ðàñïîçíàâàíèÿ ïðåäëîæåííûõ àëãîðèòìîâ áûëè ðàñ-
ñìîòðåíû ãåíîìû ðàñòåíèé Glycine max (ñîÿ êóëüòóðíàÿ), Oryza sativa (ðèñ ïî-
ñåâíîé), Populus trichocarpa (òîïîëü áàëüçàìè÷åñêèé), Sorghum bicolor (äâóõ-
öâåòíîå ñîðãî) è Vitis vinifera (âèíîãðàä êóëüòóðíûé), âçÿòûå èç ðåïîçèòîðèÿ
NCBI [6]. Âî âíèìàíèå ïðèíèìàëèñü ãåíû, äëÿ êîòîðûõ ïîëíîñòüþ èçâåñòíà
íóêëåîòèäíàÿ çàïèñü (îêîëî 90% îò âñåõ ãåíîâ äëÿ âñåõ ðàññìàòðèâàåìûõ âè-
äîâ). Äëÿ ðåàëèçàöèè àëãîðèòìîâ èñïîëüçîâàëñÿ ÿçûê ïðîãðàììèðîâàíèÿ Java.
Îïòèìàëüíûå ñìåñè ðàñïðåäåëåíèé (5) ñòðîèëèñü ñ ïîìîùüþ îïèñàííîãî â [4]
èòåðàòèâíîãî EM-àëãîðèòìà ñ ïîñëåäîâàòåëüíûì äîáàâëåíèåì êîìïîíåíòîâ ñìåñè;
äëÿ êàæäîãî ÷èñëà êîìïîíåíòîâ âûïîëíÿëîñü äåñÿòü èòåðàöèé. Ïðè ýòîì ïîðÿäîê
öåïåé Ìàðêîâà áûë ïðèíÿò ðàâíûì l = 6 êàê îáåñïå÷èâàþùèé ìàêñèìàëüíîå êà÷åñò-
âî ðàñïîçíàâàíèÿ äëÿ áîëüøèíñòâà ðàñòåíèé ïðè èñïîëüçîâàíèè ïðîñòûõ âåðîÿòíîñ-
òíûõ ìîäåëåé âèäà (4).
Ïåðâûé ýòàï ýêñïåðèìåíòà — ïðîâåðêà îáîñíîâàííîñòè îïèñàííîé â ðàçä. 3
ýâðèñòèêè ïî ñîêðàùåíèþ ðàçìåðà î÷åðåäè âûçîâîâ äëÿ âû÷èñëåíèÿ ðåêóððåíò-
íîé ôóíêöèè. Äëÿ êàæäîãî èç ñòà ñëó÷àéíûì îáðàçîì îòîáðàííûõ ãåíîâ êàæäîãî
âèäà ñðàâíèâàëèñü òðè çíà÷åíèÿ ëîãàðèôìè÷åñêîãî ïðàâäîïîäîáèÿ:
· ïðàâäîïîäîáèå äëÿ äåéñòâèòåëüíîé ïîñëåäîâàòåëüíîñòè ïîëíûõ ñîñòîÿ-
íèé — log ( )P a ;
· ïðàâäîïîäîáèå, âû÷èñëåííîå â ïðîöåññå ðàáîòû àëãîðèòìà 4, — log ( )P q ;
· ïðàâäîïîäîáèå, âû÷èñëåííîå ïóòåì ïîäñòàíîâêè âîññòàíîâëåííîé àëãî-
ðèòìîì ïîñëåäîâàòåëüíîñòè ïîëíûõ ñîñòîÿíèé â ôîðìóëó (5), — log ( )P e .
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
Íà îñíîâàíèè ïðèâåäåííûõ ïðàâäîïîäîáèé âû÷èñëÿëèñü ðàçíîñòè:
D qe
q eP P= -| log log |;( ) ( ) D ae
a eP P= -| log log |( ) ( ) .
Ðåçóëüòàòû âû÷èñëåíèé ñðåäíèõ çíà÷åíèé (òàáë. 1) ñâèäåòåëüñòâóþò î òîì,
÷òî ãèïîòåçà (15) âûïîëíÿåòñÿ ñ äîñòàòî÷íîé òî÷íîñòüþ: log log( ) ( )P Pe q» ;
ïîìèìî ýòîãî, èç ïðèáëèæåííîãî ðàâåíñòâà log log( ) ( )P Pe a» ñëåäóåò ïðèìå-
íèìîñòü äëÿ ðàññìàòðèâàåìîé çàäà÷è ïðèíöèïà ìàêñèìóìà ïðàâäîïîäî-
áèÿ. Òî÷íîñòü âûïîëíåíèÿ ðàâåíñòâ óìåíüøàåòñÿ ñ óâåëè÷åíèåì äëèíû ðàñ-
ñìàòðèâàåìîé ñòðîêè S (òàáë. 2).
Íà âòîðîì ýòàïå ýêñïåðèìåíòà èññëåäîâàíà çàâèñèìîñòü ðàçìåðà î÷åðåäè q,
èñïîëüçóåìîé â àëãîðèòìå 3, îò äëèíû ñòðîêè íàáëþäàåìûõ ñîñòîÿíèé S , à òàê-
æå îò ãðàíè÷íîãî ðàññòîÿíèÿ rmin . Êàê îêàçàëîñü, çàâèñèìîñòü äîñòàòî÷íî òî÷íî
ïðèáëèæàåòñÿ ñòåïåííîé ôóíêöèåé
| | | |q K S= a , a >1 ,
ïðè÷åì çíà÷åíèå ïîêàçàòåëÿ a óâåëè÷èâàåòñÿ ñ óìåíüøåíèåì ãðàíè÷íîãî ðàññòî-
ÿíèÿ (ðèñ. 1). Äëÿ êàæäîãî èç ðàññìàòðèâàåìûõ ãåíîìîâ îïðåäåëåíî çíà÷åíèå
rmin , ïðèâåäåííîå â òàáë. 1, ïðè êîòîðîì ïî ìåíüøåé ìåðå 90% ãåíîâ îáðàçóþò
î÷åðåäü äëèíîé íå áîëåå 5 106× ýëåìåíòîâ. Îãðàíè÷åíèå íà äëèíó î÷åðåäè ñâÿçà-
íî ñ äîñòóïíûì îáúåìîì ïàìÿòè, à òàêæå âðåìåíåì âûïîëíåíèÿ àëãîðèòìà, êîòî-
ðûå, êàê âûÿñíåíî â ðàçä. 3, ïðÿìî çàâèñÿò îò | |q . Îïðåäåëåííûå â ðåçóëüòàòå
ýêñïåðèìåíòà çíà÷åíèÿ èñïîëüçîâàëèñü â äàëüíåéøèõ âû÷èñëåíèÿõ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 51
Ãåíîì r min ( )10 3- Äëèíà
ãåíà, S
Ðàçìåð
î÷åðåäè, q
log ( )
P
e D qe D ae
Glycine max 5 3568 567765 –4662 1,163 6,955
Oryza sativa 1 2379 220667 –3124 0,546 5,946
Populus trichocarpa 2,5 2268 897660 –2991 0,271 5,337
Sorghum bicolor 1 2408 241832 –3196 0,863 8,634
Vitis vinifera 2,5 3467 951629 –4555 0,580 5,104
Ò à á ë è ö à 1 . Õàðàêòåðèñòèêè âûïîëíåíèÿ àëãîðèòìîâ 3, 4 ïðè èñïîëüçîâà-
íèè ñìåñè èç äâóõ ðàñïðåäåëåíèé
Íîìåð
ãåíà
Äëèíà ãåíà, S Ðàçìåð î÷åðåäè, q log ( )
P
q
log ( )
P
e log ( )
P
a
1 1387 137054 –1787,60 –1787,63 –1787,63
2 1587 300279 –2100,12 –2100,06 –2100,06
3 2049 418185 –2675,63 –2675,63 –2675,63
4 3632 603760 –4798,59 –4797,61 –4792,29
5 3865 784925 –5042,09 –5042,13 –5043,73
6 4093 388386 –5195,06 –5195,04 –5201,65
7 5681 949672 –7461,74 –7461,23 –7473,25
8 6075 1200067 –8072,33 –8072,38 –8082,89
9 6347 1093695 –8233,01 –8233,02 –8235,90
10 11876 2348274 –15773,02 –15773,06 –15795,49
Ò à á ë è ö à 2 . Õàðàêòåðèñòèêè âûïîëíåíèÿ àëãîðèòìîâ 3, 4 äëÿ äåñÿòè ãåíîâ
Glycine max ïðè èñïîëüçîâàíèè ñìåñè èç äâóõ ðàñïðåäåëåíèé ñ rmin = × -5 10 3
Çàêëþ÷èòåëüíûé ýòàï ýêñïåðèìåíòà — ñðàâíåíèå ýôôåêòèâíîñòè ìîäåëåé (5)
ñ ïðîñòûìè âåðîÿòíîñòíûìè ìîäåëÿìè (4), à òàêæå ìîäåëÿìè ñ ýêñêëþçèâíîé
êîìïåòåíòíîñòüþ ñîñòàâëÿþùèõ, ðàññìîòðåííûõ â [5]. Äëÿ îöåíêè êà÷åñòâà ìî-
äåëåé èñïîëüçîâàëèñü îïèñàííûå â [1] ìåòðèêè:
· ìåðû, îïðåäåëÿþùèå êà÷åñòâî ïðåäñêàçàíèÿ îòäåëüíûõ ñêðûòûõ ñîñòîÿ-
íèé, — íóêëåîòèäíàÿ ñïåöèôè÷íîñòü NSp, íóêëåîòèäíàÿ ÷óâñòâèòåëüíîñòü NSn,
êîýôôèöèåíò êîððåëÿöèè CC è ñðåäíÿÿ óñëîâíàÿ âåðîÿòíîñòü ACP;
· ìåðû, îïðåäåëÿþùèå êà÷åñòâî ðàñïîçíàâàíèÿ ãðàíèö ìåæäó ýêçîíàìè è
èíòðîíàìè, — ýêçîííàÿ ñïåöèôè÷íîñòü ESp è ýêçîííàÿ ÷óâñòâèòåëüíîñòü ESn.
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3
Ðèñ. 1. Çàâèñèìîñòü ðàçìåðà î÷åðåäè | |q îò äëèíû ãåíà | |S äëÿ ãåíîìà Populus trichocarpa è èõ
àïïðîêñèìàöèÿ ñòåïåííûìè ôóíêöèÿìè äëÿ òðåõ ðàçëè÷íûõ çíà÷åíèé ãðàíè÷íîãî ðàññòîÿíèÿ r min
| |S
| | , | | ,q S= 10 5 1 46
| |q
| | , | | ,q S= 8 42 1 62
| | , | | ,q S= 16 8 1 23
r min ,= 0 001
r min ,= 0 025
r min ,= 0 010
107
105
104
0 1000 2000 3000 4000 5000 6000
106
Ãåíîì
×èñëî
àëãîðèòìîâ
Çíà÷åíèÿ ìåðû êà÷åñòâà, %
NSp NSn CC ACP ESp ESn
Glycine max 1 80,96 89,86 77,65 88,84 69,19 64,01
2 ýêñêëþçèâíûõ 86,62 90,90 83,08 91,54 70,29 66,32
2 87,72 92,62 84,41 92,21 70,68 68,43
Oryza sativa 1 90,61 78,65 72,58 86,29 61,60 48,16
2 ýêñêëþçèâíûõ 89,96 88,99 80,28 90,14 62,42 54,46
2 89,93 88,55 79,86 89,93 64,45 56,86
Populus trichocarpa 1 87,94 93,26 82,67 91,33 69,59 61,36
2 ýêñêëþçèâíûõ 92,09 93,55 86,97 93,49 69,77 64,00
2 93,14 94,20 87,43 93,72 69,74 64,33
Sorghum bicolor 1 84,44 76,06 64,66 82,33 58,01 43,36
2 ýêñêëþçèâíûõ 86,62 90,90 83,08 91,54 70,29 66,32
2 87,72 92,62 84,41 92,21 70,68 68,43
Vitis vinifera 1 80,28 87,38 77,42 88,72 64,42 55,37
2 ýêñêëþçèâíûõ 83,50 88,67 80,69 90,35 64,06 56,58
2 89,54 91,90 85,12 92,56 67,00 59,98
Ò à á ë è ö à 3 . Ìåðû êà÷åñòâà ðàñïîçíàâàíèÿ äëÿ ïîäõîäîâ èç [2, 4] è àëãî-
ðèòìîâ 3, 4
Çíà÷åíèÿ âñåõ ìåòðèê íàõîäÿòñÿ íà îòðåçêå [0,1]; áËëüøèì çíà÷åíèÿì ñîîòâåò-
ñòâóåò ëó÷øåå êà÷åñòâî àëãîðèòìà.
Äëÿ êîíòðîëÿ ýôôåêòà ïåðåîáó÷åíèÿ (÷ðåçìåðíîé ñïåöèàëèçàöèè ïàðàìåò-
ðîâ ìîäåëè) ïðèìåíÿëàñü êðîññ-âàëèäàöèÿ [7]: âûáîðêà ñëó÷àéíûì îáðàçîì ðàç-
áèâàëàñü íà ïÿòü ïðèáëèçèòåëüíî ðàâíûõ ÷àñòåé, êàæäàÿ èç êîòîðûõ ïî î÷åðåäè
ïðèìåíÿëàñü â êà÷åñòâå êîíòðîëüíîé, à îñòàâøèåñÿ ÷åòûðå ÷àñòè ôîðìèðîâàëè
îáó÷àþùóþ âûáîðêó; ïîëó÷åííûå çíà÷åíèÿ ìåòðèê êà÷åñòâà ïîñëå ýòîãî óñðåä-
íÿëèñü. Êàê è â [4], â öåëÿõ óñêîðåíèÿ âû÷èñëåíèé ïðè îáó÷åíèè èñïîëüçîâàëèñü
âåñà è ïàðàìåòðû ñîñòàâëÿþùèõ êîìïîçèöèþ ìîäåëåé, ïîëó÷åííûå ïðè ðàáîòå
EM-àëãîðèòìà íà âñåé äîñòóïíîé âûáîðêå.
Ñîãëàñíî ðåçóëüòàòàì ðàáîòû (òàáë. 3) ïðèìåíåíèå ñìåñåé ìîäåëåé ïîçâîëÿåò ïî-
âûñèòü êà÷åñòâî ðàñïîçíàâàíèÿ äëÿ âñåõ èññëåäóåìûõ âèäîâ ãåíîìîâ. Ïðè ýòîì äëÿ
âñåõ âèäîâ, êðîìå Oryza sativa, êà÷åñòâî, ïîêàçûâàåìîå àëãîðèòìàìè 3, 4, âûøå, ÷åì
ïðè èñïîëüçîâàíèè ìåòîäà ñ ýêñêëþçèâíûìè çîíàìè êîìïåòåíòíîñòè, îïèñàííîãî â [4].
ÇÀÊËÞ×ÅÍÈÅ
Ðàññìîòðåíà â îáùåì âèäå çàäà÷à âîññòàíîâëåíèÿ ïîñëåäîâàòåëüíîñòè ñêðû-
òûõ ñîñòîÿíèé äëÿ ñìåñåé âåðîÿòíîñòíûõ ðàñïðåäåëåíèé, èìåþùèõ âèä öåïåé
Ìàðêîâà ïðîèçâîëüíîãî ïîðÿäêà. Äëÿ åå ðåøåíèÿ ïðåäëîæåí àëãîðèòì äèíà-
ìè÷åñêîãî ïðîãðàììèðîâàíèÿ ñ ýâðèñòèêîé, ïîçâîëÿþùåé çíà÷èòåëüíî ñîêðà-
òèòü ïåðåáîð. Ïîëó÷åííûé àëãîðèòì ïðèìåíåí ê çàäà÷å ðàñïîçíàâàíèÿ ôðàã-
ìåíòîâ ãåíîâ äëÿ ïÿòè ãåíîìîâ ðàñòåíèé, ÷òî îùóòèìî ïîâûñèëî êà÷åñòâî
ðàñïîçíàâàíèÿ ýòèõ ãåíîìîâ.
Íåñìîòðÿ íà äîñòàòî÷íóþ ýôôåêòèâíîñòü îïèñàííîé â ðàçä. 3 ýâðèñòèêè äëÿ
ðàññìîòðåííûõ îðãàíèçìîâ, â ñëó÷àå áîëåå ñëîæíûõ ãåíîìîâ (íàïðèìåð, ìëåêî-
ïèòàþùèõ) åå èñïîëüçîâàíèå ôàêòè÷åñêè íåâîçìîæíî: ïðè áîëüøèõ ãðàíè÷íûõ
ðàññòîÿíèÿõ rmin ôîðìóëà (15) âûïîëíÿåòñÿ ñ íåóäîâëåòâîðèòåëüíîé òî÷íîñòüþ;
ïðè ìåíüøèõ çíà÷åíèÿõ rmin íåäîïóñòèìî áîëüøèì ñòàíîâèòñÿ ðàçìåð î÷åðåäè
q â àëãîðèòìå 3. Òà æå ïðîáëåìà âîçíèêàåò ïðè óâåëè÷åíèè ÷èñëà ñîñòàâëÿþùèõ â
ñìåñè ðàñïðåäåëåíèé (5). Ýòî îáóñëîâëèâàåò ïîèñê äðóãèõ ìåòîäîâ âû÷èñëåíèÿ ðå-
êóððåíòíîé ôîðìóëû (12). Ñðåäè âîçìîæíûõ íàïðàâëåíèé äëÿ äàëüíåéøèõ èññëåäî-
âàíèé îòìåòèì òåñòèðîâàíèå ðàáîòû àëãîðèòìà íà ñõîäíûõ çàäà÷àõ (íàïðèìåð, äëÿ
îïðåäåëåíèÿ ïðîñòðàíñòâåííîé ñòðóêòóðû áåëêîâ) [5, 8].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. K n a p p K . , C h e n Y . - P . P . An evaluation of contemporary hidden Markov model genefinders with
a predicted exon taxonomy // Nucleic Acids Research. — 2007. — 35. — P. 317–324.
2. Ñ å ð ã è å í ê î È . Â . , Ã ó ï à ë À . Ì . , Î ñ ò ð î â ñ ê è é À . Â . Ðàñïîçíàâàíèå ôðàãìåíòîâ ãåíîâ
â ÄÍÊ ñ ïðèìåíåíèåì ìîäåëåé Ìàðêîâà ñî ñêðûòûìè ïåðåìåííûìè // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2012. — ¹ 3. — Ñ. 58–67.
3. Ã ó ï à ë À . Ì . , Î ñ ò ð î â ñ ê è é À . Â . Èñïîëüçîâàíèå êîìïîçèöèé ìîäåëåé Ìàðêîâà äëÿ îïðåäåëå-
íèÿ ôóíêöèîíàëüíûõ ó÷àñòêîâ ãåíîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2013. — ¹ 5. — Ñ. 61–68.
4. Ñ å ð ã è å í ê î È . Â . , Ã ó ï à ë À . Ì . , Î ñ ò ð î â ñ ê è é À . Â . Èñïîëüçîâàíèå ÅÌ-àëãîðèòìà äëÿ
êëàññèôèêàöèè ãåíîâ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2015. — ¹ 1. — Ñ. 48–58.
5. Î ñ ò ð î â ñ ê è é À .  . Îïðåäåëåíèå âòîðè÷íîé ñòðóêòóðû áåëêîâ ñ ïîìîùüþ ìîäåëåé Ìàðêîâà //
Ìåæäóíàðîäíûé íàó÷íî-òåõíè÷åñêèé æóðíàë «Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè». — 2013. —
¹ 2. — Ñ. 140–147.
6. Í à ö è î í à ë ü í û é öåíòð áèîòåõíîëîãè÷åñêîé èíôîðìàöèè ÑØÀ. — http://ncbi.nlm.nih.gov/.
7. N g A . Y . Preventing overfitting of cross-validation data // Proc. 14th Intern. Conf. on Machine Learning.
— Waltham: Morgan Kaufmann, 1997. — P. 245–253.
8. Ï ð å ä ñ ê à ç à í è å âòîðè÷íîé ñòðóêòóðû áåëêîâ íà îñíîâå áàéåñîâñêèõ ïðîöåäóð ðàñïîçíàâàíèÿ íà
öåïÿõ Ìàðêîâà / È.Â. Ñåðãèåíêî, Á.À. Áåëåöêèé, Ñ.Â. Âàñèëüåâ, À.Ì. Ãóïàë // Êèáåðíåòèêà è ñèñòåì-
íûé àíàëèç. — 2007. — ¹ 2. — Ñ. 59–64.
Ïîñòóïèëà 03.07.2014
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 3 53
|