Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
p,=Zexp(-6G,/RT),
где 6G. - свободная энергия i-й структуры, a Z - нормировочный множитель.
Однако изложенные комбинаторные методы, в которых осуществляется перебор всех возможных структур, оказались недостаточно эффективны и не получили широкого распространения. Развитие методов анализа нуклеотидных последовательностей привело к тому, что увеличились длины расшифрованных последовательностей и соответственно резко возросло число альтернативных структур. Пропорционально этому увеличилось и время, требуемое для расчетов. Однако неразумность использования переборного подхода связана скорее всего не с этим обстоятельством. Дело в том, что при анализе всех вариантов вторичных структур нет возможности, так сказать, руководить этим процессом, например на каком-то этапе забраковывать явно невыгодную структуру и не доводить процесс ее формирования до конца. Поскольку очевидно, что невыгодным будет подавляющее число структур, то отсюда понятно, насколько неэффективен метод перебора. Поиски выхода из этого затруднения привели к идее использования метода динамического программирования, которая оказалось исключительно плодотворна.
Индуктивные методы. Индуктивный, или рекурсивный, подход наиболее широко распространен для предсказания вторичных структур РНК. Как правило, для этой цели используют метод динамического программирования. Впервые этот алгоритм для определения вторичной структуры РНК по нуклеотидной последовательности был использован В.Г.Туманяном с соавт. (Туманян и др.,1966).
Продемонстрируем возможности метода на примере небольшой нуклеотидной последовательности (рис. 6.5). Запишем все возможные комплементарные пары в виде треугольной таблицы. Элемент таблицы а, , стоящий на пересечении i-ro столбца и j-й строки, равен 1, если i-й нуклеотид комплементарен j-му, и равен 0, если соответствующие основания не комплементарны. Нетрудно догадаться, что если через единички можно про-
вести диагональ из левого нижнего угла в правый верхний, то на последовательности может образоваться соответствующая спираль. В данном случае видно, что существует только одна диагональ из единичек и последовательность как бы складывается пополам и 1-й нуклеотид образует пару с 10-м нуклеотидом, 2-Я нуклеотид с 9-м и т.д. Следовательно, на данной последовательности можно построить спираль из пяти спаренных оснований. Это число можно найти, построив вторую треугольную таблицу, элементы которой btj находятся по следующему правилу:
bi-м j-i если atJ -1
1J шах (a. _ b^ j), если au = 0.
Можно доказать методом математической индукции, что построенный таким образом матричный элемент Ъ.. равен числ^ пар в максимальной по длине спирали, построенной на участке последовательности от i-ro до j-ro нуклеотида. Заполнение этой таблицы начинается с первых номеров последовательности.
1 2 3 4 5 6 7 8 9 10
A U U '3 С G С A A U
1 А 0
2 и 1 0 1
3 и 1 0 0 1 0
4 G 0 0 0 0 1 0 0
5 С 0 0 0 1 0 1 1 1 1
6 G 0 0 0 0 1 0 1 1 1 1 1
7 С 0 0 0 1 0 1 п 2 2 2 2 1 1
8 А 0 1 1 0 0 0 0 0 3 3 3 2 1 1 0
9 А 0 1 1 0 0 0 0 0 0 4 4 3 2 1 1 0 0
10 и 1 0 0 0 0 0 0 1 1 0 5 4 3 2 1 1 1 1
Рис. 6.5. Нуклеотидная последовательность и матриць. возможных комплементарных пар
Таким образом, можно выбрать на данной последовательности наиболее длинную спираль. На основе одношпилечного алгоритма можно найти конфигурацию с двумя и более спиралями. В результате можно получить структуру, состоящую из самых длинных спиралей.
В последующих работах, аналогично тому, как развивалось применение комбинаторных методов, подсчет нуклеотидных пар был заменен расчетом свободной энергии. Нуссинов и Якобсон (Nussinov, Jacobson, 1980) разработали быстрый алгоритм для предсказания вторичной структуры РНК с наименьшей свободной энергией. Поскольку эта работа получила широкую известность и породила целый ряд исследований, рассмотрим ее более подробно.
Идею подхода легче представить на задаче, в которой определяется структура с наибольшим числом спаренных оснований. Представим нуклеотидную последовательность b,bn в ваде окружности, а возможные комплементарные пары - дугами между соответствующими нуклеотидами (рис. 6.6). Выберем на окружности отрезок bjbj длиной р и определим макси-
Р и с. 6.6. Представление вторичной структуры на окружности
мальное число пар на этом отрезке. Точка разбиения отрезка к пробегает все нуклеотиды от о4 до 3 каждой точке проверяется возможность
образования комплементарной пары bkbj и подсчитывается их число на фрагментах b, bk_, и bk+ tbj_t. После того, как все точки к будут проверены, выбирается максимальная величина нуклеотидных пар и записывается в матрицу комплементарных пар М, г Если bj не может образовать пару ни с одним нуклеотидом к на фрагменте bj, то М, =М, . Уве-
