Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
больше двух петель
В последние годы метод динамического програмирования очень широко применялся для предсказания вторичных структур РКК. По-видимому, наиболее интенсивно использовались рассмотренные нами алгоритмы, полученные в работах (Nussinov, Jacobson, 1980; Zuker, Stiegler, 1981).Позже оба эти алгоритма неоднократно модифицировались. Якобсон и Зукер,объединившись друг с другом (Jacobson, Good et al., 1984), сумели в 4 раза уменьшить требуемый объем памяти, необходимый для расчетов по программе Зукера и Стиглера. В свою очередь в другой работе Нуссинов с соавт. (Comay, Nussinov et al., 1984) значительно улучшили алгоритм расчета, предложенный ею ранее совместно с Якобсон, - скорость счета при этом для последовательности, содержащей 1000 нуклеотидов, возросла на два порядка.
При использовании метода динамического программирования независимо от того, какой конкретно алгоритм применяется, на каждом шаге выбирается сдна структура. В результате с помощью этого метода можно полу-
а
б
в
i-»i\_________/Т-i
чить только одну единственную вторичную структуру с минимальной свободной энергией. Естественно, что корректность этих предсказаний зависит от точности определения термодинамических параметров. Однако в экспериментальных работах указывается, что точность определения параметров для спиральных областей не превышает 0,2-0,5 ккал, а для петель и для других неспиральных областей оценка параметров еще Оолее грубая -1-2 ккал (Salser, 1977).
Кроме этого, термодинамические параметры рассчитываются для конкретной температуры (обычно 37 ) и строго определенных условий, имеется в виду, например, ионная сила раствора. Изменения условий должны привести к изменению вторичной структуры. Однако метод динамического программирования не позволяет выявить возможные структурные модификации. Он очень жестко связан с параметрами. Поэтому нет никакой уверенности в том. «то, даже если расчет произведен чт<кург!г'НО. тр;?'- 'азанная структура действительно соответствует структуре с минимальной свободной энергией.
Есть еще более важное соображение, которое заставляет быть неудовлетворенным методом динамического программирования для поиска вторич ных структур РНК. В ряде работ было показано, что биологическое значение могут иметь альтернативные неравновесные структуры. Так, альтернативные структуры могут быть важны для объяснения механизма трансляции (Gold, et al., 1981), стабильности мРНК (von Gabin et al.,1983), атте-нюации (КоIter, Yanofsky, 1982).
Поэтому возникла потребность в разработке алгоритма, позволяющего предсказывать несколько близких по энергиям структур. В работе (Williams, Tinoco, 1986) был разработан модифицированный алгоритм, ъ котором используются идеи динамического программирования, развитые Дукером и Стиглером. В результате расчета можно получить не только одну единственную оптимальную структуру, но и определить ряд субопти-мальных вторичных структур.
Кинетический подход. Для предсказания вторичной структуры РНК было предложено еще несколько оригинальных алгоритмов, которые можно условно объединить под названием кинетический подход. На наш взгляд, этот подход является наиболее перспективным. Идея его заключается в моделировании на ЭВМ процесса формирования вторичной структуры РНК.
В наиболее четком виде такой подход" был впервые использован Джорданом (Jordan, 1972). Он фактически разыгрывал на ЭВМ процесс образования спиральных участков. С помощью метода Монте-Кар;:с на последовательности выбираются две случайные точки. Если они могут образовать комплементарную пару, то программа "старается" дорастить сколькс возможно спиральный участок в обе стороны от стартовой пары. Если спиральный участок в этом месте возможен, то ок фиксируется, затем выбираются две другие случайные точки и процедура повторяется до тех пор. пока на последовательности остается возможность образовать комплемен-
тарные пары. Такой расчет проводится несколько раз и в результате можно выбрать структуру с наибольшим числом пар.
В работе Мартинеца (Martinez, 1984) предлагается рассматривать процесс образования вторичной структуры как последовательное добавление спиральных участков. Правило, которым при этом пользуются, является очень простым: к структуре надо добавить спираль, которая имеет наи-
большую константу равновесия - Кравн = ехр(- 6G,/RT), где 6G. - изменение стандартной свободной энергии структуры при присоединении к ней i-й спирали.
Практически реализация этого алгоритма происходит следующим образом. Предварительно рассчитываются все возможные спирали, которые могут образоваться на данной последовательности. Затем на ЭВМ начинают моделировать образование вторичной структуры. Предположим, что на некотором этапе уже сформировалась часть вторичной структуры. На следующем шаге для всех полностью топологически совместимых с этой структурой спиралей рассчитываются константы равновесия. Выбор спирали, которая добавляется к структуре, происходит с помощью метода Монте-Карло, при этом вероятность выбора пропорциональна константе равновесия. Процесс самосборки молекулы РНК многократно повторяют, и в результате получается наиболее вероятная структура.
