О нахождении статистических древовидно-контекстных моделей генетических текстов1)

Орлов Ю.Л., Потапов В.Н., Филиппов В.П.
Институт математики им. С.Л.Соболева СО РАН, Новосибирск

Аннотация:

Последовательности ДНК и белки можно рассматривать как символьные последовательности в алфавите из четырeх и двадцати букв соответственно. Известно, что частота появления буквы в генетической последовательности зависит от контекста, т. е. одной или нескольких предшествующих букв. Одним из наиболее адекватных способов описания генетического текста является статистическая модель текста. Марковская модель текста определяется алфавитом $D$, множеством состояний модели $S$ и функцией $\mu(S,D)\rightarrow S$, которая определяет текущее состояние по предыдущему состоянию и текущей букве текста. Набором параметров марковской модели служат вероятности $P(a\vert s)$ порождения букв $a\in D$ в состояниях $s\in S$. Вероятность того, что последовательность $x$ имеет начало $a_1\dots a_n$, $a_i\in D$ определяется равенством

\begin{displaymath}Pr\{x_1\dots x_n = a_1\dots a_n\}=P(a_1\vert s_1)P(a_2\vert s_2)\dots P(a_n\vert s_n),\end{displaymath}

где $s_1$ -- исходное состояние и $s_{i+1}=\mu (s_i,a_{i+1})$, $1\leq i\leq n-1$. Модель последовательности независимых испытаний соответствует марковской модели с единственным состоянием, а состояния марковской модели $k$-го порядка (вероятность буквы зависит от $k$ предыдущих) можно отождествить с наборами из $k$ букв, т. е. $S=D^k$. Марковская модель называется древовидно-контекстной (см., например, [2]) если множество состояний модели можно отождествить с набором контекстов (слов в алфавите $D$). Множество состояний древовидно-контекстной модели удобно представлять в виде множества листьев некоторого $k$-ичного контекстного дерева $T$, где $k$ - мощность алфавита. Заметим, что контекст в позиции $n$ последовательности $x_1\dots x_{n-1}x_n\dots$ однозначно определяется началом текста $x_1\dots x_{n-1}$ и деревом $T$, за исключением нескольких начальных позиций. Таким образом, контекстное дерево однозначно определяет соответствующую ему марковскую модель. В [1] предложен метод построения статистической модели текста, основаный на предложенном в [3] и развитом в [4] алгоритме сжатия данных. А именно, мы считаем, что модель наилучшим образом соответствует тексту, если в ней стохастическая сложность (см., например, [1]) текста минимальна. На основании известной теоремы о больших уклонениях нами показано, что предложенный в [1] метод позволяет определить "истинную" модель текста. Точнее, пусть на множестве последовательностей в алфавите $D$ задано распределение вероятностей, порожд„нное древовидно-контекстной моделью с деревом $T$, максимальная глубина которого не превосходит $d$. Пусть $x$ - бесконечная последовательность букв, $x_1\dots x_n\in D^n$ - начало $x$ длины $n$ и $T_n$ - контекстное дерево, построенное по слову $x_1\dots x_n$ методом из [1]. Справедливо следующее утверждение.

Теорема. $Pr\{T\ne T_n\}\rightarrow 0$ при $n\rightarrow \infty$.

Метод нахождения древовидно-контекстной модели текста реализован в програме доступной через Интернет (http://wwwmgs.bionet.nsc.ru/mgs/programs). С помощью этой программы проанализированы последовательности ДНК из базы данных "Samples" (http://wwwmgs.bionet.nsc.ru/mgs/dbase/nsamples) и аминокислотные последовательности белков, описанные в банке данных PDB. Выявлены некоторые зависимости между структурой контекстного дерева генетической последовательности и е„ функциональными свойствами.

Литература

1
Орлов Ю.Л., Потапов В.Н. Оценка стохастической сложности генетических текстов // Вычислительные технологии. 2000. Т.5, спецвыпуск. C.5-15.

2
Штарьков Ю.М., Чокенс Ч.Дж., Виллемс Ф.М.Дж. Мультиалфавитное взвешенное универсальное кодирование древовидно-контекстных источников // Проблемы передачи информ. 1997. Т.33, вып.1, С.21-34.

3
Rissanen J. A universal data compression system// IEEE Trans. Inform. Theory. 1983. V.IT-29, N5. P.656-664.

4
Rissanen J. Fast universal coding with context models// IEEE Trans. Inform. Theory. 1999. V.45, N4. P.1065-1071.
... текстов1
) Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (код проекта 99-01-00531) и Интеграционного проекта СО РАН 65.
Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Friday, 28-Sep-2001 20:11:57 NOVST