Использование ЭВМ в молекулярной биологии. Введение в теорию генетических текстов - Соловьев В.В.
Скачать (прямая ссылка):
Таблица 4
Энергия стэкинг взаимодействия соседних комплементарных пар в спиралях РНК (ккал/моль)
Нуклеотиды с 5 стороны в спирали Нуклеотида с 3 -стороны в спирали
А С G V
А -1.2 -2.1 -2.1 -1.8
С -2.1 -4.8 -3.0 -2.1
б -2.1 -4.3 -4.8 -2.1
и -1.8 -2.1 -2.1 -1.2'
Омельянчук и соавт. /151/ цредложили метод ускоренного перебора ВС, основанный на использовании теории графов. В их алгоритме ключевым моментом являлось построение графа стерео-химической разрешенности - G , в котором вершине сопоставляется одна из спиралей, а две вершины соединяются ребром, если соответствующие им спирали взаимно стереохимически разрешены. В этом случае поиск всех ВС формально сводится к оптимальному перебору клик графа Q , т.е. к задаче, которая имеет ряд алгоритмических решений /152/. Этот метод позволяет рассчитывать ВС для молекул РЖ длиной до 150 н.п. /151/.
На использовании аппарата теории графов базировался таюхе и алгоритм, предложенный Нинио /153/, который для убыстрения перебора применил известный метод ветвей и границ.
Однако решающий вклад в создание эффективных алгоритмов поиска наиболее низкоэнергетической ВС РНК внесли дальнейше разработки рекуррентных подходов в работах Пуссинов и др. /154 - 157/, Зукера и др. /137; 147; 158/ и модификации эти:: основных алгоритмов другими авторами /КЗ; 15:)/.
Эти алгоритмы учитывают энергию спиралей и петель, входящих в ВС. Тая, например, в алгоритмах Нуссинов /154/ энергия (i , j ) - области последовательности - рассчитывается следующим образом:
E(i, к-i) + E(k<-I,j-i) + Е
(27)
Е (i,j-i), j-4 ,
где к выбирается аналогично алгоритму Нуссинов, описанному выше; Е Kj ~ энергия, вносимая во вторичную структуру вновь введенной комплементарной парой. Зйачение EKj зависит от того, входит ли данная пара {ВК-Ъ;> в спираль, в боковую, во внутреннюю, в шпилечную или в сложную петлю (рис. 33).
В алгоритме Зукера /137/ для каждого участка последовательности (t,у) рассчитывается две энергии: I) V ( -t ,J) - минимальная свободная энергия всех допустимых, т.е. стереохимически разрешенных ВС (см. рис. 29), которые можно построить на
Рис. 34. Иллюстрация шага обратной процедуры после введения в ВСГ комплементарной пары Вк-В; , необходимой для расчета энергии Е*.; в формуле ( 27 У .
Вк,
В„
В,-
)-з
а - пара В * -В; образует стэкинг-район (S) с цреды-
б, в образуют боковую петлю <ЕKj - ЕТВ));
Ч |
В„
К
г - внутреннюю петлю (Е.. = = E(I) V,
, / ? д - сложную петлю (Ew =
в,'н' . 1«». ч
66
подпоследовательности Bi ... Bj ; 2) V (i, j) - минимальная энергия всех допустимых структур, в которых основание спарено с основанием В j . Если В i и Bj не комплементарны, то V( i, j;= «о .
Значения W (v,j) и V(i,j) рассчитываются рекуррентно, сначала для всех пентануклеотидов в последовательности j ~ 'ь -= 4, а затем для все больших и больших подпоследовательностей. Если j - i=*d>4 , то V (j, j) и W(i,j) вычисляются исходя из уже известных значений для \l (v\ j') и W(v’ j’), где j’-i’ < d.
На рис. 35(а, б) изображены все возможные различные варианты вторичных структур участка ( i, j) . Как видно из рис. 35,а, цри расчете значения V(Ь, j ) необходимо выбрать минимальную из трех энергий
V(i, j)= тт{Ы,Ъг,Ъ5), где EI - энергия шпилечной петли, образующейся цри спаривании
V(l,‘) , ^ з Рис. 35. А. V
минимальная свободная
lJ. энергия всех возможных
! \ вторичных структур на
V ! ь ’ 1 подпоследовательности
П ’ \ • '• -b'i' U , j ), в которых нук-
'Ы'"1 ‘ 1 леотиды ВС и Bj спа-
• I
рены. I - шпилечная петля; 2: а - район стэкинга, Ь - боковая петля, с - внутренняя петля; 3 - сложная петля.
Б. (w( v, j)) - минимальная свободная энергия всех возможных вто-( ричных структур на под-
и' w w w последовательности ( Ь ,
Н Н Щ j ).. I - либо b , ли-
‘ а ГТ"'- -В бо у входят в структу-
f 'i i i 11 РУ.2 - i я j cnape-
Й' W ны между собой; 3 - I
- i . и j спарены, но не
1 друг с другом .
67
Bi cB;5 EZ=mxn{v, j7 i\j’) + V(s, j) ; E3= min
i<ifVj’ci *+l<i\j-2
*W(ilJ,j-l)+Em) ; Ем - энергия сложной петли (авторы принимают
Ем = 0).
Для расчета энергии W(i, j) (см. рис. 35,6) необходимо выбрать минимальное значение из четырех энергий:
V(i,j), ?4),
где
Л4= 777777 (W(i,i’) + W(i’+l,j)) .
Для того чтобы понять необходимость вычисления двух энергий (т.е. вычисление дополнительной энергии V ( i, j) , которая не является минимальной для данной подпоследовательности), обратимся к рис. 36. На этом рисунке упрощенно показан один этап алгоритма расчета оптимальной ВС. Пусть на участке (i,j) найдены оптимальная ВС (I) и "навдучшая" закрытая структура (2). Из рисунка видно, что при переходе к подпоследовательности ( i +1, j + i) из четырех альтернативных структур (3) -(6) минимумом свободной энергии обладает закрытая структура (6), возникшая из структуры (2). Если на цредыдущем этапе алгоритма отбросить структуру (2) как неоптимальную, то на данном этапе оптимальная ВС (6) будет потеряна.
Это происходит потому, что цри спаривании концевых нуклеотидов увеличиваются энтропийные потери на стабилизацию такой структуры (учитываются нами в виде дестабилизирующей энергии петли). В результате повышается суммарная энергия структуры.
