МОЛЕКУЛЯРНАЯ БИОЛОГИЯ, 2003, том 37, № 5, с. 850-860
БИОИНФОРМАТИКА
УДК 577.1
ПОИСК КОНСЕРВАТИВНЫХ ВТОРИЧНЫХ СТРУКТУР РНК
© 2003 г. К. Ю. Горбунов1*, А. А. Миронов2, В. А. Лшбецкий1
1Институт проблем передачи информации Российской академии наук, Москва, 101447 2Федералъное государственное унитарное предприятие "ГосНИИгенетика", Москва, 113545
Поступила в редакцию 03.04.2003 г.
Предложен новый алгоритм для поиска консервативных вторичных структур РНК в заданном наборе последовательностей. Алгоритм основан на выравнивании цепочек плеч потенциальных спиралей. Он позволяет учитывать консервацию нуклеотидных последовательностей в окрестностях спиральных участков. Алгоритм применим для поиска новых структурных РНК и регуляторных элементов. Его эффективность позволяет использовать алгоритм для полногеномного анализа. Приведены результаты разнообразного тестирования этого алгоритма.
Ключевые слова: вторичная структура РНК, алгоритм динамического программирования, структура тРНК, структура ЯРК регуляция транскрипции, регуляция трансляции.
Роль вторичной структуры РНК хорошо известна. Она важна для: структурных РНК, таких как рибосомные или малые ядерные РНК; РНК ряда вирусных геномов; рибозимов; регуляции экспрессии генов. Большинство известных систем регуляции в бактериях на уровне матричных РНК работают по принципу аттенюации, когда реализуется одна из двух альтернативных структур. "Запрещающая" на уровне транскрипции содержит терминатор транскрипции, а на уровне трансляции блокирует сайт связывания рибосом. Альтернативная ("разрешающая") структура соответственно не позволяет образоваться терминатору транскрипции или блокировать сайт связывания рибосом. Часто "разрешающая" структура стабилизируется различными молекулами: белком в случае регуляции экспрессии рибосом-ных белков, низкомолекулярными лигандами в случае регуляции синтеза рибофлавина и тиамина [1, 2], другими РНК в случае Т-бокса [3]. В связи с биологической важностью вторичных структур РНК проблема ее предсказания по одной исходной последовательности или по набору исходных последовательностей является одной из классических задач биоинформатики.
Для анализа и предсказания вторичных структур РНК применяли различные подходы. Наиболее популярен подход, основанный на оптимизации какой-либо функции качества вторичной структуры. В 1966 г. для поиска наиболее длинных шпилек в одной последовательности Туманян предложил метод динамического программирования [5]. В 1980 г. Нуссинов и Якобсон предложили метод динамического программирования для поиска вторичной структуры с максималь-
* Эл. почта: gorbunov@ittp.ru
ным количеством спаренных оснований также в одной последовательности [6]. Позже Зукер предложил метод динамического программирования для поиска структур с минимальной свободной энергией (также в одной последовательности), который позволяет использовать дополнительные ограничения, получаемые из экспериментальных данных [7-9]. В настоящее время стандартным алгоритмом предсказания вторичных структур РНК является упомянутый алгоритм Зукера (Ы-tp://www.bioinfo.rpi.edu/~zukerm/rna/). К сожалению, эти подходы не лишены недостатков. В частности, для транспортных РНК только примерно для 80% последовательностей удается предсказать структуру "клеверного листа". Другим существенным недостатком подхода, основанного на минимизации свободной энергии, является его принципиальная зависимость от исходных энергетических параметров. Кроме того, в ряде случаев, например при анализе аттенюаторов, наибольший интерес представляет как раз "разрешающая" структура, которая по механизму действия аттенюатора заведомо не является оптимальной. Поэтому авторам кажется, что вообще алгоритмы, основанные на оптимизации (по крайней мере, с доступными исследователям функционалами), не будут успешными.
Другим направлением в изучении и предсказании вторичных структур РНК является анализ динамики формирования вторичной структуры в процессе синтеза РНК. В работах [10-12] предложена кинетическая модель сворачивания РНК, которая реализована в форме монте-карловской процедуры. Такой подход улучшил понимание процессов формирования структуры РНК, одна-
ко его предсказательная сила также не достаточно велика.
Наиболее успешен подход, основанный на поиске консервативных структур в последовательностях изофункциональных РНК. Таким образом, предсказаны структуры тРНК, рРНК, мяРНК. Однако при этом анализе, во-первых, использовали дополнительные сведения [13], получаемые из экспериментов, и значительную часть работы делали вручную, а во-вторых, эти последовательности заранее имели естественное выравнивание, что значительно упрощало задачу. Более поздние работы основывались на заранее построенных выравниваниях и использовали соображения о коррелированных заменах, сохраняющих потенциальные спирали (см., например, [14, 15]). Ряд работ основан на статистическом анализе взаимно комплементарных сегментов последовательностей [16, 17]. В последнее для поиска консервативных вторичных структур РНК время стали развиваться методы, основанные на генетических алгоритмах [18, 19].
Сейчас доступны последовательности многих геномов. Их сравнительный анализ позволяет, в частности, искать новые консервативные (и альтернативные) структуры РНК. Для проведения такого рода массовых исследований необходимы методы, алгоритмы и компьютерные программы автоматического и, главное, быстрого поиска вторичных структур.
Эти методы должны допускать наличие в исходной выборке некоторого количества "мусорных" последовательностей, т.е. таких, которые заведомо не содержат искомой консервативной структуры. Другая их важная особенность должна состоять в том, чтобы заранее не требовалось выравнивания исходных последовательностей. И наконец, такие методы должны быть столь эффективными (быстрыми), чтобы за разумное время проводить полногеномный анализ.
ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ
Будем называть потенциальной спиралью в данной последовательности пару взаимно комплементарных плеч (состоящих из отрезков и промежутков между ними - выпячиваний и внутренних петель). Пары потенциальных спиралей могут иметь различное взаимное расположение. Основные виды взаимного расположения спиралей показаны на рис. 1. Более полная классификация их взаимного расположения приведена в [12]. Частично перекрывающиеся спирали будем относить к одному из указанных здесь случаев. Рассмотрим множество всех возможных потенциальных спиралей (или их разумную, например, по значению энергии часть) в одной из данных последовательностей. Для этого множества спира-
О О
Рис. 1. Возможные взаимные расположения двух спиралей: а - две шпильки, б - вложенные спирали с внутренней петлей, в - псевдоузлы, г - взаимоисключающие спирали.
лей строится граф, вершины которого приписаны потенциальным спиралям. Две вершины графа (две спирали) соединены ребром в том случае, если эти спирали "совместимы в одной вторичной структуре", где понятие совместимости меняется в зависимости от биологической задачи. Обычно ситуации в и г на рис. 1 считают несовместимыми. Каждое ребро можно считать "покрашенным в цвет", который указывает на взаимное расположение спиралей, приписанных его концам. Такой граф будем называть графом вторичных структур.
Отношение "спираль Е целиком содержит в своей петле спираль Б", которое обозначается Е > Б, играет здесь существенную роль. Другое важное отношение состоит в том, что спираль Е расположена целиком левее спирали Б, в этом случае будем записывать Е/Б. Понятно, что взаиморасположение четырех спиралей клеверного листа и некоторые другие вторичные структуры целиком описываются этими двумя отношениями, рис. 2.
В самом общем виде задачу поиска вторичных структур в одной данной последовательности можно сформулировать как задачу поиска максимальных клик или достаточно плотных подграфов в графе вторичных структур [20].
Теперь, переходя к постановке, в которой дан набор исходных последовательностей, рассмотрим соответствующий ему набор таким образом полученных графов вторичных структур (по одному графу вторичных структур для каждой из данных нуклеотидных последовательностей). Консервативной вторичной структурой называется набор попарно изоморфных (с учетом цвета и всех других приписанных ребрам и вершинам характеристик) подграфов этих графов. В этом случае задача состоит в поиске таких наборов. Конечно, можно построить множество очень разных таких наборов (например, если взять по одной спирали в каждой последовательности).
Для поиска биологически содержательной вторичной структуры нужно сформулировать критерий качества консервативной вторичной
а
ОАнтикодоновая шпилька
Дополнительная петля
T ¥
G C
R
Т¥-шпилька
- Акцепторная
спираль
С С А
Рис. 2. Клеверная структура тРНК. Ас - акцепторная спираль, D - "левая боковая" D-спираль, An - антико-донная спираль, ¥ - "правая боковая" спираль. Очевидно, что следующая система отношений описывает топологию тРНК: Ас > D, Ас > An, Ac > ¥, D/An, An/¥.
структуры, который зависит от самой биологической задачи. Снабдим вершины и ребра дополнительными характеристиками, например расстоянием между плечами спиралей, и(или) последовательностями нуклеотидов в промежутках между спиральными участками (петлях) и в самих спиралях и(или) статистическими свойствами спиралей. В этом случае качество консервативной структуры определяется как функция этих характеристик.
К сожалению, попытка прямо перейти от этой постановки задачи к алгоритму ее решения не может привести к успеху, так как не вызывает сомнения, что таким образом получится переборный алгоритм.
Итак, пусть дан набор из n фрагментов РНК, например набор регуляторных областей ортоло-гичных генов. Далее переменные i и j пробегают номера этих фрагментов от 1 до n. Задача состоит в том, чтобы найти в этих последовательностях подобные (гомологичные) вторичные структуры, причем некоторые из последовательностей могут не содержать этой структуры (так называемые "мусорные").
Часто интересно и достаточно было бы найти только ранжирование потенциальных спиралей в каждой из немусорных по
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.