Компьютерная система "Gene Discovery" для функциональной аннотации последовательностей ДНК 1

Витяев Е.Е.
Институт математики СО РАН, Новосибирск
Орлов Ю.Л., Вишневский О.В., Поздняков М.А., Беленок А.С., Подколодный Н.Л., Колчанов Н.А.
Институт цитологии и генетики СО РАН, Новосибирск
Ковалерчук Б.К.
Central Washington University, Ellensburg

Аннотация:

В статье представлено применение методов Data Mining и Knowledge Discovery для поиска закономерностей в таблицах данных по контекстным особенностям последовательностей ДНК, участвующим в регуляции транскрипции. Задачей является определение закономерностей, связывающих нуклеотидную последовательность с ее функциональным классом. Поиск схем закономерностей строился в логике первого порядка пополненной вероятностными оценками. Для решения этой задачи разработана компьютерная система "Gene Discovery". С помощью этой системы были проанализированы последовательности эритроид-специфичных промоторов и промоторов генов эндокринной системы (Kolchanov N.A. et al., 2000). Найдены закономерности, связывающие расположение олигонуклеотидов в регуляторном районе гена относительно старта транскрипции и функциональный класс этого гена. Разработан метод распознавания класса промотора на основе этих закономерностей.

This paper presents implementation of Data Mining and Knowledge Discovery techniques for the search for regularities in tables of context features of DNA sequences involved in transcription regulation. The goal is to discover regularities, which connect nucleotide sequences with the functional class of those sequences. The search patterns for regularities have been constructed in first-order logic augmented by probabilistic estimates. The PC software system "Gene Discovery" has been designed for this purpose. This system accepts molecular-genetics data retrieved from the database using SQL queries. Sequences of erythroid-specific promoters and promoters of genes of endocrine system from TRRD database (Kolchanov N.A. et al., 2000) have been analysed by this system. Several regularities that connect (i) the nucleotide sequences in the regulatory DNA and its location relative to transcription start with (ii) functional class have been found. A method for recognition of the DNA promoter class has been developed using these regularities.

Ключевые слова: Машинное обучение (Machine Learning), Открытие Знаний (Knowledge Discovery), Анализ Данных (Data Mining), биоинформатика, распознавание промоторов эукариот, сайты связывания транскрипционных факторов

ВВЕДЕНИЕ

Исследование структуры промоторов представляет интерес для понимания механизмов транскрипции эукариот. Обязательным элементом, абсолютно необходимым для инициации транскрипции, является коровый (базальный) промотор, под которым понимают минимальную последовательность ДНК, необходимую для правильной инициации транскрипции гена in vitro. В коровый промотор входит старт транскрипции и область приблизительно от -60 до +40 п.о. по отношению к нему (Zhang M.Q., 1998; Arnone M.I. & Davidson E.H., 1997). Каждый регуляторный район содержит в своем составе сайты связывания определенных транскрипционных факторов (ССТФ) (Nikolov D.B. & Burley S.K., 1997). Один ген может иметь множество промоторов, определяющих формирование различных белковых продуктов или обладающих различным уровнем специфической функциональной активности. Кроме того, для промоторов эукариот характерно отсутствие точной локализации контекстных сигналов, значимых для их функционирования и слабость этих сигналов (Goodrich J.A. et al., 1996).

Разнообразие строения промоторных районов генов создаёт наибольшие трудности для разработки программ распознавания промоторов. Несмотря на то, что создано большое количество методов распознавания промоторов РНК полимеразы II в геномах эукариот (Pedersen A.G. et al., 1999; Kondrakhin Y.V. et al., 1995) проблема повышения точности распознавания в целом остается нерешенной. Существующие методы распознавания основаны на весовых матрицах или других мерах сходства анализируемой последовательности к обучающей выборке (базе данных известных последовательностей). В то же время выбор участка последовательности для оценки сходства основан на экспертных биологических знаниях. В то же время эти знания не были независимо проверены статистически. (Например, предположение о значимости участка от -40 до -20 п.о. относительно старта транскрипции значимо для промоторов, содержащих TATA-бокс, и в то же время не обязательно для TATA-несодержащих промоторов).

Анализ данных в других научных областях связан с экстенсивной обработкой больших баз данных и открытием больших наборов закономерностей. В то же время, информация, распределенная по научной литературе и сосредоточенная в молекулярно-биологических базах данных, содержит тысячи экспериментальных результатов о последовательностях ДНК, вовлеченных в регуляцию транскрипции. В настоящее время в мире существует около 300 молекулярно-биологических баз данных, доступных через Интернет. (Baxevanis A.D., 2001). Такое положение дает возможность широкомасштабного применения теории анализа данных и открытия знаний в биоинформатики (Jakobsen I.B. et al., 2001).

"GENE DISCOVERY": ПРИНЦИПИАЛЬНАЯ СХЕМА

Компьютерная программа "Gene Discovery" была разработана для анализа структурной организации промоторов эукариот на основе информации об экспериментально известных и предсказанных функциональных сайтах.

Компьютерная система "Gene Discovery" является адаптацией системы "Discovery" для задач молекулярной биологии (Kovalerchuk B. & Vityaev E., 2000). "Gene Discovery" состоит из трех основных модулей: (1) модуль для интерактивного представления контекстных сигналов в стандартной таблице данных; (2) модуль "Discovery" для поиска закономерностей; (3) модуль для распознавания класса последовательности, используя найденные закономерности. Программа написана на языке С++ и предназначена для интерактивного использования. Блок анализа данных "Discovery" обозначен на рисунке 1 как "поиск паттернов совместного присутствия и взаимной локализации контекстных сигналов" ("Search for patterns of the joint presence and relative localisation of contextual signals...") Другие модули системы предназначены для подготовки и интерпретации молекулярно-генетических данных.

Рис. 1: Схема системы "Gene Discovery".
\begin{figure}\begin{center} \epsfxsize=12cm\ %%\epsfysize=12cm \epsfbox{fig1.eps} \end{center}\end{figure}

"DISCOVERY": ТЕХНОЛОГИЯ АНАЛИЗА ДАННЫХ

Метод машинного обучения и созданная на его основе система "Discovery" (Витяев Е.Е. & Москвитин А.А., 1993) находит статистически значимые правила в логике первого порядка для функциональной аннотации регуляторных районов. Система "Discovery" успешно применялась к решению многих проблем в психологии, физике, медицине, финансах и других науках (Kovalerchuk B. & Vityaev E. et al, 1997, 2000, 2001) (см. также www-сайт "Scientific Discovery": http://www.math.nsc.ru/LBRT/l/vityaev/, раздел "comparison"). Также как и любая техника, основанная на логических правилах, данная техника позволяет получить предсказывающие правила на естественном языке, которые интепретируются с биологической точки зрения и обеспечивают предсказание промоторов (функциональную аннотацию) (Mitchell T., 1997). Биолог может оценить корректность распознавания и значимость правил самих по себе. Научной проблемой в применении предсказывающих систем, основанных на данных, является обобщение. Система "Discovery" обобщает данные через обнаружение логических вероятностных правил-законов.

Концепция вероятностной обусловленности (P.Suppes, 1970) является краеугольным камнем этого подхода при выводе из того, что $Y$ есть вероятностная причина $X$ ( $Y \Rightarrow X$), когда вероятность $X$ при данном $Y$ больше вероятности $X$. Система "Discovery" использует обобщенную версию этой концепции. Она оперирует с логическими выражениями вида $A_{{\rm 1}}\& \ldots \& A_{{\rm k}} \quad \Rightarrow A_{{\rm0}}$. Выражения $A_{{\rm 1}}, \ldots ,A_{{\rm k}}$ позволяют заключать, что они являются вероятностной причиной $A_{{\rm0}}$ при выполнении некоторого дополнительного условия, которое будет приведено ниже. Это условие требует, чтобы условная вероятность $CondProb(A_{{\rm0}}\vert SubFormular(A_{{\rm 1}}\& \ldots \& A_{{\rm k}}))$ события $A_{{\rm0}}$ при любом подусловии $SubFormular(A_{{\rm 1}}\& \ldots \& A_{{\rm k}})$ была строго меньше, чем условная вероятность $CondProb(A_{{\rm0}}\vert A_{{\rm 1}}\& \ldots \& A_{{\rm k}})$ события $A_{{\rm0}}$ при полном условии. В частности, для выражения $Y \Rightarrow X$, если мы имеем $SubFormular(Y) = \emptyset $, то условная вероятность $CondProb(X\vert SubFormular(Y)) = CondProb(X\vert \emptyset ) = Probability(X)$ должна быть строго меньше, чем $CondProb(X\vert Y)$ -- вероятность $X$ при данном $Y$. Эта идея приводит нас к следующему определению (Kovalerchuk B. & Vityaev E., 2000):

Определение: правило $C~=~(A_{{\rm 1}}\& \ldots \& A_{{\rm k}} \quad \Rightarrow A_{{\rm0}})$ является правилом-законом (выражает вероятностную причинную зависимость между посылкой $A_{{\rm 1}}\& \ldots \& A_{{\rm k}}$ и заключением $A_{{\rm0}})$, если:

\begin{displaymath}CondProb(A_{{\rm0}}\vert SubFormular(A_{{\rm 1}}\& \ldots \& ... ...< CondProb(A_{{\rm0}}\vert A_{{\rm 1}}\& \ldots \& A_{{\rm k}})\end{displaymath}

для любого подусловия $SubFormular(A_{{\rm 1}}\& \ldots \& A_{{\rm k}})$, где

$SubFormular(A_{{\rm 1}}\& \ldots \& A_{{\rm k}})=A^{{\rm s}}_{{\rm 1}}\& \ldots... ...}}_{{\rm k}}, \{A^{{\rm s}}_{{\rm 1}}, \ldots ,A^{{\rm s}}_{{\rm k}}\} \subset$ (не равно) $\{ A_{{\rm 1}}\& \ldots \& A_{{\rm k}}\}$.

Это определение правила-закона удовлетворяет всем свойствам научных законов. Концептуально правила-законы пришли из философии науки. Эти правила пытаются зафиксировать математически существенные особенности научных законов: (1) высокий уровень обобщения; (2) простоту (Бритва Оккама); и (3) максимальная опровержимость.

Правило $C = (A_{{\rm 1}}\& \ldots \& A_{{\rm k}} \quad \Rightarrow A_{{\rm0}})$ позволяет генерировать подправила

\begin{displaymath}SubFormular (A_{{\rm 1}}\& \ldots \& A_{{\rm k}}) \quad \Rightarrow A_{{\rm0}}\end{displaymath}

с сокращенной условной частью, т.е. $A_{{\rm 1}}\& A_{{\rm 2}} \quad \Rightarrow A_{{\rm0}};\ A_{{\rm 1}} \& A_{{\rm 2}}\& A_{{\rm 3}~} \Rightarrow ~A_{{\rm0}}$ и т.д. Известно, что подправило логически сильнее, чем само правило используемое для его построения. Таким образом, если некоторое правило $C$ и его подправило $C'$ выполнены (классифицируют один и тот же набор примеров), то подправило предпочтительнее. Вообще говоря, существует три причины для предпочтения подправила:

1) Подправило более общее (логически сильнее и описывает тот же набор событий);

2) Подправило проще, чем само правило, поскольку состоит из меньшего числа утверждений в условной части;

3) Подправило более опровержимо, чем само правило, поскольку больший набор возможных примеров может его опровергнуть (условная часть подправила имеет меньше ограничений).

Таким образом, если правило $C$ покрывает набор примеров, то нужно проверить, что бы ни одно из его подправил $C'$ не покрывали тот же набор примеров. В противном случае это подправило (или, возможно, некоторое его подправило) будет предпочтительнее, поскольку это подправило проще, более общо и более опровержимо. В детерминистическом случае правило-закон может быть определено (для некоторого набора примеров) как правило без подправил, покрывающих тот же набор примеров. Другими словами, правило-закон есть правило, которое истинно для некоторого набора примеров, но ни одно из его подправил не истинно для этого же набора примеров.

Если примеры содержат шум, что типично для естественных наук, следует использовать вероятностные характеристики выражений вместо значений истина/ложь. Условная вероятность правила используется в системе "Discovery" в качестве такой характеристики. Условная вероятность правила $C$ определена как $Prob(C) = CondProb(A_{{\rm0}}\vert A_{{\rm 1}}\& \ldots \& A_{{\rm k}})$, предполагая, что $Prob(A_{{\rm 1}}\& \ldots \& A_{{\rm k}}) > 0$. Подобным же образом определены условные вероятности $Prob(A_{{\rm0}}\vert A_{{\rm i}{\rm 1}}\& ...\& A_{{\rm i}{\rm h}})$ для подправил $C_{{\rm i}~}=~(A_{{\rm i}{\rm 1}}\& ...\& A_{{\rm i}{\rm h}} \quad \Rightarrow A_{{\rm0}})$, предполагая, что $Prob(A_{{\rm i}{\rm 1}}\& ...\& A_{{\rm i}{\rm h}}) > 0$. Условная вероятность Prob(C) используется далее для оценки прогностической силы правила для предсказания $A_{{\rm0}}$. Кроме того, условная вероятность - основное средство для определения не детерминистических (вероятностных) правил-законов (Kovalerchuk B. et al., 2001; Витяев Е.Е., 1992).

Правило является вероятностным правилом-законом тогда и только тогда, когда все его подправила имеют значимую более низкую условную вероятность, чем само правило. Другое определение правил-законов может быть получено в терминах обобщения. Правило является правилом-законом тогда и только тогда, когда оно не может быть обобщено без статистически значимого уменьшения его условной вероятности. Правила-законы определены таким образом, чтобы соответствовать всем трем отмеченным выше свойствам (свойства научных законов), т.е., эти правила (1) общие с логической точки зрения, (2) простые, и (3) опровержимые.

Система "Discovery" ищет все цепочки $C_1,\ C_{{\rm 2}}, \ldots, C_{{\rm m}{\rm -} {\rm 1}},\ C_{{\rm m}}$ связанных подправил-законов, где $C_{{\rm 1}}$ есть подправило $C_{{\rm 2}},\ C_{{\rm 1}} = sub(С_{{\rm 2}}),\ C_{{\rm 2}}$ - подправило правила $C_{{\rm 3}},\ C_{{\rm 2}} = sub(С_{{\rm 3}})$ и, окончательно, $C_{{\rm m}{\rm -} {\rm 1}}$ - подправило правила $C_{{\rm m}},\ C_{{\rm m}{\rm -} {\rm 1}} = sub(C_{{\rm m}})$. Также $Prob(C_{{\rm 1}})<Prob(C_{{\rm 2}}), \ldots, Prob(C_{{\rm m}{\-}{\rm 1}}) < Prob(C_{{\rm m}})$. Доказана теорема (Витяев Е.Е., 1992) о том, что все правила, имеющие максимальные значения условной вероятности, могут быть найдены в конце таких цепочек.

Цель системы "Discovery" -- найти все наиболее сильные предсказывающие правила (St-правила (strong)).

Определение 1. Правило $C = (A_{{\rm 1}}\& \ldots \& A_{{\rm k}} \quad \Rightarrow A)$, где $k > 1$ и $Prob(A_{{\rm 1}}\& \ldots \& A_{{\rm k}}) > 0$ называется St-правилом для атомарной формулы $A$ на данных $D$, если и только если:

1) $Prob(C) = Prob(A\vert A_{{\rm 1}}\& \ldots \& A_{{\rm k}}) > Prob(A)$, где $A_{{\rm 1}}\& \ldots \& A_{{\rm k}}$ - условия, выполненные на данных $D$;

2) Правило $C$ имеет максимум условной вероятности $Prob(C)$ среди правил $C*$, удовлетворяющих условию 1 и выполненных на тех же данных, что и $C$, и

3) Для любого правила $C*$, удовлетворяющего условиям 1, 2, мы имеем $C \Rightarrow C*$.

Условие 1 означает, что St-правило $C$ имеет значимую условную часть (посылку), т.е. условная вероятность $Prob$ правила $C$ больше, чем вероятность атомарной формулы $A$ как таковой. Если это условие не выполняется, то нет оснований добавлять посылку для прогнозирования $A$. Если атом A сам имеет высокую вероятность, то он может быть предсказан без посылки

Условие 2 приводит к "сильнейшему" St-правилу, т.е. правилу с максимумом условной вероятности среди правил, удовлетворяющих указанному выше условию 1 на тех же данных.

Условие 3 означает, что St-правило С является наиболее "общим" среди правил, удовлетворяющих условиям 1 и 2, т.е., правило $С$ охватывает наиболее широкий набор случаев из $D$, для которых оно применимо.

Доказана теорема (Витяев Е.Е., 1992) что все St-правила могут быть найдены в конце цепочек $C_{{\rm 1}},\ C_{{\rm 2}}, \ldots , C_{{\rm m}{\rm -}{\rm 1}},\ C_{{\rm m}}$. Так достигается цель системы "Discovery".

Алгоритм перестает генерировать новые правила, когда они становятся слишком сложными (т.е. статистически незначимыми для анализируемых данных) даже если правила имеют высокую точность на обучении. Для оценки статистической значимости в алгоритме используется статистический критерий Фишера (точный критерий Фишера для таблиц сопряженности) (Kendall M.G. & Stuart A., 1977).

Другой очевидный критерий остановки - ограничение числа условий $A_{{\rm k}}$ (число полей данных в анализируемой таблице).

Рис. 2: Пример поиска правил для гипотезы $A_{{\rm 0}}$.
\begin{figure}\begin{center} \epsfxsize=12cm\ \epsfysize=12cm \epsfbox{fig2.eps} \end{center}\end{figure}

Теоретические преимущества обобщения представлены в теореме (Витяев Е.Е., 1992; Витяев Е.Е. & Москвитин А.А., 1993). Данный подход имеет сходство с подходом подсказок (Abu-Mostafa, 1990). Мы используем математический формализм правил логики первого порядка, описанный в ряде работ (Russel S. & Norvig P., 1995; Halpern J.Y., 1990; Krantz D.H. et al. 1971, 1989, 1990). Заметим, что класс правил логики первого порядка шире, чем класс решающих деревьев. (Mitchell T., 1997).

ПОДГОТОВКА ДАННЫХ ДЛЯ СИСТЕМЫ "GENE DISCOVERY"

Компьютерная система "Gene Discovery" является адаптацией системы "Discovery" для анализа нуклеотидных последовательностей регуляторных районов. Принципиальная схема системы представлена на рисунке 1.

На вход системы подается обучающая выборка нуклеотидных последовательностей двух альтернативных классов: класс 1 - промоторы; класс 2 - последовательности, не выполняющие этой функции (например, случайные последовательности с теми же частотами нуклеотидов, либо соседние участки последовательности, не несущие регуляторной функции, например, экзоны).

Имеется блок программ, осуществляющих поиск контекстных сигналов в последовательностях этих двух классов (рисунок 1). Сигнал может быть:

контекстным (короткое олигонуклеотидное слово, функциональный сайт и т.д.),

конформационным (участок ДНК, характеризующийся особенностями конформационных или физико-химических свойств, например, легкоплавкие участки ДНК, сильно изогнутая ДНК и т.д.),

структурным (например, Z-ДНК или шпилька вторичной структуры РНК и др.).

Все эти сигналы могут быть установлены с использованием знаний о свойствах ДНК и консенсусных схемах, на основе экспериментальной информации из специализированных баз данных.

В настоящей работе рассматриваются контекстные сигналы только одного типа - несовершенные олигонуклеотиды.

С помощью этой программы были проанализированы последовательности промоторов генов эндокринной системы и соответствующие им по частотам олигонуклеотидов случайные последовательности. Выборка 40 промоторов была взята из базы данных ES-TRRD (http://wwwmgs.bionet.nsc.ru/). Последовательности промоторов имели длину 120 п.о. (от -100 до +20 п.о. относительно старта транскрипции). Оценка гомологии между промоторами показала, что она для любой пары не превышает 60% . Негативная выборка "не-промоторов" содержала 1000 случайных последовательностей той же длины и с теми же частотами нуклеотидов, что и последовательности промоторов. Для генерации случайных последовательностей использовалась программа http://wwwmgs.bionet.nsc.ru/mgs/dbases/nsamples/.

Для выделения олигонуклеотидных сигналов, специфичных к данной группе промоторов, использовалась программа ARGO (Babenko V.N. et al., 1999), (см. также http://wwwmgs.bionet.nsc.ru/mgs/programs/argo/). Под олигонуклеотидным сигналом, или мотивом, понимается слово длиной 8 оснований, записанное в обобщённом 15-буквенном алфавите IUPAC: {A, T, G, C, R=G/A, Y=T/C, M=A/C, K=T/G, W=A/T, S=G/C, B=T/C/G, V=A/G/C, H=A/T/C, D=A/T/G, N=A/T/G/C}. Это стандартный способ представления близких строк нуклеотидов одной записью, как один сигнал. Таким образом, был выполнен подготовительный этап подготовки данных. Заметим, что подобные сигналы могут быть построены по гомологии с известными белковыми сайтами связывания в других формах записи.

Отобранные контекстные сигналы (вырожденные олигонуклеотиды) были локазизованы в исследуемых последовательностях ДНК и представлены в виде таблицы данных с помощью модуля "Gene Discovery". Итак, данные были представлены в виде таблицы "объект-признак". В этой таблице объектами являются последовательности ДНК, признаками - присутствие контекстных сигналов и их локализация относительно экспериментально определенного старта транскрипции.

Таким же образом была проанализирована другая выборка промоторов, а именно, промоторы эритроидных генов. В итоге для анализа данных была построена таблица, содержащая несколько тысяч строк. Она содержала последовательность контекстного сигнала $S_{{\rm i}}$ и его позицию $Position(S_{{\rm i}})$ в промоторном районе. Например, для первого промотора в анализируемой выборке сигнал $S_{{\rm 1}}$=TGACCAAT, $Position(S_{{\rm 1}})=-67$, сигнал $S_{{\rm 2}}$=RCCAATND, $Position(S_{{\rm 2}})=-65$ и т.д.

ПРИМЕНЕНИЕ СИСТЕМЫ ДЛЯ АНАЛИЗА РЕГУЛЯТОРНЫХ ГЕНОМНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Проверяемая гипотеза $A_{{\rm0}}$ в нашем случае звучит так: "Принадлежит ли последовательность к классу 1 (промоторы)?"

Назовем комплексным сигналом группу олигонуклеотидных мотивов, имеющих некоторую схему взаимного расположения в промоторной последовательности. Другими словами комплексный сигнал - это группа описанных ранее коротких контекстных сигналов. Присутствие такого комплексного сигнала может рассматриваться как условие $A_{{\rm0}}$ принадлежности к классу промоторов. Рассмотрим простейший комплексный сигнал $(S_{{\rm 1}},\ S_{{\rm 2}})$, образованный парой олигонуклеотидов с заданным порядком:

\begin{displaymath} (S_{{\rm 1}},\ S_{{\rm 2}}) = (Position(S_{{\rm 1}})<Position(S_{{\rm 2}})),\end{displaymath}

где $S_{{\rm 1}}$ и $S_{{\rm 2}}$ - олигонуклеотиды в таблице объект-признак; $Position(S_{{\rm 1}})$ и $Position(S_{{\rm 2}})$ - позиции этих олигонуклеотидов в последовательности относительно старта транскрипции.

То есть мы можем рассматривать условие $A_{{\rm 1}}$ как $(S_{{\rm 1}},\ S_{{\rm 2}})$, и проверить гипотезу $A_{{\rm 1}} \Rightarrow A_{{\rm0}}$ для всех последовательностей ДНК, содержащих $S_{{\rm 1}}$ и $S_{{\rm 2}}$.

Но присутствие только двух олигонуклеотидов ( $S_{{\rm i}},\ S_{{\rm j}})$ может быть недостаточным условием. Поэтому мы должны рассмотреть все тройки олигонуклеотидов, такие как $(S_{{\rm 1}},\ S_{{\rm 2}},\ S_{{\rm 3}})=(Position(S_{{\rm 1}})<Position(S_{{\rm 2}}) <Position(S_{{\rm 3}}))$. Формально такая тройка может быть рассмотрена как две пары $(S_{{\rm 1}},\ S_{{\rm 2}})$ и $(S_{{\rm 2}},\ S_{{\rm 3}})$. Гипотеза для тестирования сейчас $A_{{\rm 1}}\& A_{{\rm 2}} \Rightarrow A_{{\rm0}}$. Таким образом, используя логику первого порядка, мы строим более и более сложные условия, включая присутствие этих олигонуклеотидов в прямой или комплементарной цепи ДНК, перекрывание олигонуклеотидов (пересечение позиций) и так далее.

В результате анализа "Gene Discovery" было найдено большое число закономерностей совместного появления контекстных сигналов в промоторных районах. Число закономерностей зависит от параметров поиска, задаваемых пользователем. Если мы определим низкий уровень условной вероятности (менее 0.5), то итоговое число правил будет очень большим (до нескольких тысяч). Такое число правил трудно интерпретировать эксперту. Поэтому мы можем задать высокий уровень условной вероятности, например, более 0.95. Тогда число правил будет мало, но они будут очень значимы с биологической точки зрения.

ИНТЕРПРЕТАЦИЯ ПОЛУЧЕННЫХ ЗНАНИЙ КАК КОМПЛЕКСНЫХ СИГНАЛОВ В ПРОМОТОРАХ ЭУКАРИОТ

Найденные закономерности могут быть проанализированы экспертом в молекулярной биологии как уникальные комплексные сигналы, значимые для правильного функционирования промотора.

Таблица 1. Примеры комплексных сигналов в промоторах генов эндокринной системы



1 2 3 4 5
1 CWGNRGCN<NGSYMTAM<CAGGRNCH 0.875 0.00054 4 0.24 (<1)
2 KGRSSAGR<CYCYNSCY<CWGSNYCH 1.0 0.00012 4 0.28 (<1)
3 CWGNRGCN<NGSYMTAM<MAGKSHCN 1.0 0.00009 6 0.47 (<1)
4 CWGNRGCN<NGSYMTAM<CMDGGNCH 0.846 0.00099 5 0.43 (<1)
5 CNKSAGNT<NCARGRNC<HNNKGCTG 1.0 0.01426 4 0.37 (<1)
6 RNWGGCCN<DGRGNRGG<TCMAGNMN 0.875 0.00118 4 0.4 (<1)
7 RGSNRGRG<NNGSTWTA<CNCNRKGC 1.0 0.02852 5 0.53 (<1)
8 NNGSTWTA<NMAGDGMC<CNCNRKGC 0.875 0.04755 5 0.53 (<1)
9 RGSNRGRG<NNGSTWTA<CMDGGNCH 1.0 0.03964 5 0.55 (<1)
10 RGSNRGRG<KGGNSAGD<ANCTSMNG 1.0 0.03964 4 0.45 (<1)
... ... ... ... ... ...
45 RGSNRGRG<NGSYMTAM<CNCNRKGC 1.0 0.03964 5 0.58 (<1)


Примечания. Данные в таблице приведены не полностью из-за большого объема, пропуски обозначены многоточиями.

1 - Комплексный сигнал состоит из олигонуклеотидов в 15-буквенном алфавите, линейно расположенных на последовательности в соответствии с приведенной записью. Знак "<" означает, что позиция первого олигонуклеотида относительно старта транскрипции меньше позиции второго. Расстояние между отдельными сигналами не фиксировано.

2 - Условная вероятность $PC(N_{{\rm 1}},\ N_{{\rm 2}})$ считается как отношение числа промоторов, имеющих данный сигнал $N_{{\rm 1}}$ к общему числу последовательностей, имеющих данный сигнал $N_{{\rm 1}}/(N_{{\rm 1}}+N_{{\rm 2}})$.

3 - Оценка вероятности получить сигнал в промоторах по случайным причинам большее число раз, чем наблюдаемое, по точному критерию Фишера для таблиц сопряженности $P(N_{{\rm 1}},\ N_{{\rm 2}},\ N_{{\rm 3}},\ N_{{\rm 4}})$.

4 - Количество промоторов в обучающей выборке, имеющих данный комплексный сигнал.

5 - Ожидаемое по случайным причинам количество промоторов, имеющих комплексный сигнал. В предположении независимости входящих в комплексный сигнал олигонуклеотидов оценивается как произведение общего числа промоторов на частоты олигонуклеотидов в промоторах, с учетом вариантов их взаимного линейного расположения.


Рассмотрим дополнительные условия к отбору комплексных сигналов, помимо высокого уровня условной вероятности:

(1) индивидуальные сигналы, входящие в комплексный сигнал, не пересекаются на последовательностях рассмотренных промоторов;

(2) наблюдаемое количество промоторов $N$, в которых встретился комплексный сигнал выше числа $N*$, которое по случайным причинам ожидается в выборке промоторов, $N>N*$.

Ожидаемое количество $N*$ оценивалось как произведение частот отдельных олигонуклеотидов в промоторах, умноженное на общее число промоторов, с учетом числа вариантов взаимного расположения олигонуклеотидов на последовательности промотора. Например, ожидаемое количество промоторов $N*$, в которых встретился комплексный сигнал $(S_{{\rm 1}},\ S_{{\rm 2}},\ S_{{\rm 3}}\vert Pos(S_{{\rm 1}})<Pos(S_{{\rm 2}})<Pos(S_{{\rm 3}}))$, равно

\begin{displaymath} N*=P(S_{{\rm 1}})P(S_{{\rm 2}})P(S_{{\rm 3}})M/6, \end{displaymath}

где $N*$ - ожидаемое количество промоторов, в которых встретился комплексный сигнал; $P(S_{{\rm 1}})$, $P(S_{{\rm 2}})$, $P(S_{{\rm 3}})$ - частоты промоторов, содержащих олигонуклеотиды $S_{{\rm 1}},\ S_{{\rm 2}}$ и $S_{{\rm 3}}$ соответственно; $M$ - полное количество промоторов в анализируемой выборке; $6=3!$ - число возможных вариантов взаимного размещения трех олигонуклеотидов в промоторе.

Примеры комплексных сигналов, удовлетворяющих этим условиям, специфичных для промоторов генов эндокринной системы приведены в таблице 1. Рассмотрим сигнал CWGNRGCN<NGSYMTAM<MAGKSHCN. Знак "<" здесь означает, что позиции соответствующих олигонуклеотидов упорядочены относительно старта транскрипции. Итак, ожидаемое число встретить этот сигнал $N*=0.47$, т.е. меньше единицы, в то время как он встретился в 6 промоторах, что в приблизительно в 13 раз больше ожидаемого уровня.

Пример расположения комплексного сигнала представлен на рисунке 3.

Рис. 3: Схема расположения комплексного сигнала CWGNRGCN < NGSYMTAM < MAGKSHCN в промоторах генов эндокринной системы. Последовательности промоторов сфазированы относительно старта транскрипции (позиция +1 п.о.), выделенного стрелкой. Идентификатор EMBL исследуемой последовательности указан слева в скобках. Входящие в комплексный сигнал олигонуклеотидные мотивы длиной 8 п.о. отмечены черными прямоугольниками, указана позиция первого нуклеотида относительно старта транскрипции. Положение TATA-бокса, проиндексированное в базе данных TRRD, отмечено заштрихованными прямоугольниками. Позиции первого и последнего нуклеотида в TATA-боксе указаны курсивом.
\begin{figure}\begin{center} \epsfxsize=12cm\ \epsfysize=12cm \epsfbox{fig3.eps} \end{center}\end{figure}

Промоторные последовательности выровнены относительно старта транскрипции (позиция +1 п.о.), отмеченная стрелкой. Идентификаторы EMBL рассмотренных последовательностей приведены в скобках. Восьминуклеотидные мотивы, представляющие комплексные сигналы показаны как затемненные прямоугольники. Указана позиция первого олигонуклеотида относительно старта транскрипции. Черным прямоугольниками показаны позиции TATA-бокса, проиндексированные в базе данных TRRD; позиции первого и последнего нуклеотида выделены курсивом.

Следует заметить, что система не переобучается на обучающих примерах и показывает ошибку первого рода на контроле примерно равную условной вероятности правил, вычисленных на обучении.

Таким образом, разработанная нами компьютерная система "Gene Discovery" позволяет выявлять как индивидуальные значимые мотивы (вырожденные квазиинвариантные олигонуклеотиды), так и комплексные сигналы. Проведенный анализ показал, что промоторы генов эндокринной системы и эритроид-специфичные промоторы характеризуются высокой насыщенностью такими сигналами. О функциональной значимости комплексных сигналов свидетельствует тот факт, что они имеют сходное расположение в пределах подгрупп специфичных промоторов. Кроме того, как отмечалось выше, комплексные сигналы могут иметь сходные расстояния между индивидуальными мотивами. При этом анализируемые промоторы не имеют выраженной гомологии.

Индивидуальные мотивы могут соответствовать сайтам связывания транскрипционных факторов. Еще в ранних работах по анализу и распознаванию промоторов было показано, что они обогащены потенциальными сайтами связывания транскрипционных факторов по сравнению со случайными последовательностями (Kondrakhin Yu.V. et al., 1995). Индивидуальные мотивы могут также соответствовать участкам ДНК, обеспечивающим специфические конформационные или физико-химические свойства: повышенную гибкость ДНК, легкоплавкость и т.д., необходимые для функционирования промоторов.

При рассмотрении комплексных сигналов следует отметить несколько обстоятельств.

Во-первых, в ряде работ (см. (Kondrakhin Yu.V. et al., 1995; Klingenhoff A. et al., 1999) выявлены специфичные паттерны распределения потенциальных сайтов связывания транскрипционных факторов с максимумами локализации различных сайтов в различных участках промоторов. Таким образом, наблюдающиеся комплексные сигналы могут отражать преимущественное расположение различных сайтов в определенных участках промоторов. Доказательства важности позиционирования контекстных характеристик в пределах промоторов также получены М.Зангом (Zhang M.Q., 1998). В работах В.Г.Левицкого (Левицкий В.Г. и др., 2000) выявлено разбиение промотора на локальные участки с характерным динуклеотидным составом.

Во-вторых, в последнее время активно изучается особый тип регуляторных элементов, контролирующих транскрипцию, которые называются композиционными элементами (КЭ)(Kel-Margoulis O.V. et al., 2000). Они образованы парами сайтов связывания транскрипционных факторов, которые в результате белок-белковых взаимодействий между соответствующими транскрипционными факторами приобретают новые регуляторные свойства. Каждый из сайтов в составе КЭ способен функционировать по отдельности, но их взаимодействие обеспечивает существенно более выраженный активирующий или репрессирующий эффект на транскрипцию гена. В настоящее время экспериментально выявлено более 150 КЭ (Kel-Margoulis O.V. et al., 2000) (см. также http://compel.bionet.nsc.ru/). Исследование закономерностей совместной встречаемости и взаимного расположения сайтов c помощью системы "Gene Discovery" открывает путь для создания компьютерных методов поиска потенциальных композиционных элементов. Мы полагаем, что выявление и учет комплексных сигналов позволит в дальнейшем существенно повысить точность распознавания специфических групп промоторов.

Авторы выражают признательность В.Г. Левицкому, Е.В. Игнатьевой, О.А. Подколодной за ценные замечания и помощь в работе.

Литература

1
Abu-Mostafa. Learning from hints in neural networks // J. Complexity, 1990, 6: 192-198.

2
Arnone M.I., Davidson E.H. The hardwiring of development: organization and function of genomic regulatory systems //Development 1997, 124(10): 1851-1864.

3
Babenko V.N., Kosarev P.S., Vishnevsky O.V., Levitsky V.G., Basin V.V., Frolov A.S. Investigating extended regulatory regions of genomic DNA sequences // Bioinformatics, 1999, 15: 644-653.

4
Baxevanis A.D. The Molecular Biology Database Collection: an updated compilation of biological database resources // Nucleic Acids Research, 2001, 29: 1-10.

5
Fickett J.W., Hatzigeorgiou A.G. Eukaryotic promoter recognition // Genome Res., 1997, 7: 861-878.

6
Goodrich J.A., Cutler G., Tjian R. Contacts in context: promoter specificity and macromolecular interactions in transcription // Cell 1996, 84(6): 825-830

7
Halpern J.Y. An analysis of first-order logic of probability // Artificial Intelligence 1990, 46: 311-350.

8
Jakobsen I.B., Saleeba J.A., Poidinger M., Littlejohn T.G. TreeGeneBrowser: phylogenetic data mining of gene sequences from public databases // Bioinformatics 2001, 17: 535-540.

9
Kel-Margoulis O.V., Romaschenko A.G., Kolchanov N.A., Wingender E., Kel A.E. // Nucleic Acids Res., 2000, 28, 311-315.

10
Kendall M.G., Stuart A. The advanced theory of statistics, 4th ed., Charles Griffin & Co LTD, London. 1977.

11
Klingenhoff A, Frech K, Quandt K, Werner T. Functional promoter modules can be detected by formal models independent of overall nucleotide sequence similarity // Bioinformatics 1999, 15(3): 180-186.

12
Kolchanov N.A., Podkolodnaya O.A., Ananko E.A., Ignatieva E.V., Stepanenko I.L., Kel-Margoulis O.V., Kel A.E., Merkulova T.I., Goryachkovskaya T.N., Busygina T.V., Kolpakov F.A., Podkolodny N.L., Naumochkin A.N., Korostishevskaya I.M., Romashchenko A.G., Overton G.C. Transcription regulatory regions database (TRRD): its status in 2000 // Nucleic Acids Research 2000, 28(1): 298-301.

13
Kondrakhin Y.V, Kel A.E., Kolchanov N.A., Romaschenko A.G., Milanesi L. Eukaryotic promoter recognition by binding sites for transcription factors // CABIOS, 1995, 11: 477-488.

14
Kovalerchuk B., Vityaev E., Ruiz J.F. Design of consistent system for radiologists to support breast cancer diagnosis // In Proc Joint Conf Information Sciences, Durham, NC, 1997, 2: 118-121.

15
Kovalerchuk B., Vityaev E. Data Mining in finance: Advances in Relational and Hybrid Methods // (Kluwer international series in engineering and computer science; SECS 547), Kluwer Academic Publishers, 2000, 308 p.

16
Kovalerchuk B., Vityaev E., Ruiz J. Consistent Knowledge Discovery in Maedical Diagnosis // IEEE Engineering in Medicine and Biology Magazine. Special issue: "Medical Data Mining", July/August 2000, 26-37.

17
Kovalerchuk, B., Vityaev E., Ruiz J.F.  Consistent and Complete Data and "Expert" Mining in Medicine // In: Medical Data Mining and Knowledge Discovery (Book chapter),  Springer, 2001, 238-280.

18
Krantz D.H., Luce R.D., Suppes P., Tversky A. Foundations of measurement. Vol. 1,2,3 NY, London: Acad. press, 1971. 577 p., 1989, 493 p., 1990. 356 p.

19
Mitchell T. Machine Learning. New York: McGraw Hill, 1997.

20
Nikolov D.B., Burley S.K. RNA Polymerase II transcription initiation: A structural view // Proc. Natl. Acad. Sci. USA, 1997, 94: 15-22.

21
Pedersen A.G., Baldi P., Chauvin Y., Brunak S. The biology of eukaryotic promoter prediction - a review // Comput. Chem., 1999, 23: 191-207.

22
Russel S., Norvig P. Artificial Intelligence. A Modern Approach. Englewood Cliffs, NJ: Prentice Hall, 1995.

23
Suppes P. A probabilistic Theory of Causality, North-Holland, Amsterdam, 1970.

24
Zhang M.Q. Identification of human gene core-promoters in silico // Genome Res. 1998, 8: 319-326.

25
Витяев Е.Е., Москвитин А.А. Введение в Теорию Открытий. Программная система Discovery // Вычислительные системы, Новосибирск 1993, 148: 117-163.

26
Витяев Е.Е. Семантический подход к созданию баз знаний. Семантический вероятностный вывод // Вычислительные системы, Новосибирск, 1992, 146: 19-49/

27
Левицкий В.Г., Катохин А.В., Колчанов Н.А. // Вычислительные технологии, 2000, Т. 5, С. 41-47.

Примечание

... ДНК 1
Работа поддержана грантами РФФИ (00-04-49229, 00-07-90337, 99-07-90203, 01-07-90376, 00-04-49255, 01-04-06243мас), программы "Геном человека", Интеграционным проектом СО РАН № 65, ИНТАС (грант YSF 00-178)
Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

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