Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
личивая соответственно значения i и j,можно проверить все возможные отрезки длиной р на последовательности b,bn. На следующем этапе повторим аналогично всю процедуру на отрезке длиной р+1 и т.д. Следовательно, для каждого интервала b
Mt.J- ШаХ
Mj.j.j}, i < k <j=i + p .
Поскольку выбор дуги ij происходит с последовательным увеличением длины р, то величины М4 _,, MkMj_, и уже определены и эле-
мент матрицы Mjj может быть легко подсчитан. На последнем этапе рассчитывается величина М1п, т.е. определяется, какое максимальное количество комплементарных пар может быть образовано на всей последовательности.
Для того, чтобы получить соответствующую максимальную структуру, строится вторая n п матрица К. В элементе матрицы Kj j содержится номер основания bk с наибольшим числом возможных нуклеотидных пар на интервале b(j. Для образования структуры сначала рассмотрим величину К1п. В ней записано число к - номер нуклеотида bk, который, образуя
пару с нуклеотидом Ьп, приводит к наилучшему сворачиванию всей последовательности. Образование этой пары делит последовательность на две части. Теперь для каждой из них анализируем матрицу К и повторяем про-цедуру оптимального сворачивания. Разбивая последовательность на все более маленькие фрагменты, получим в результате структуру с максимальным числом пар.
Алгоритм поиска структуры с минимальной свободной энергией построен аналогичным индуктивным образом. Анализируются последовательно увеличивающиеся нуклеотидные фрагменты и определяется минимальная свободная энергия. Выражение для матрицы М может быть переписано следующим образом
min {Е,_, Е,
-.>• i < k <
где E, j - элемент матрицы E, e которой записана минимальная энергия структуры, образованная нуклеотидной последовательностью b4bj; Ejk -энергия пары нуклеотидов j и к; 1м1п равнс 3, это минимальное число нуклеотидов, которое может находится в петле.
В каждом случае энергия для отрезка btbj определяется как сумма энергий, рассчитанных для фрагментов bibk_1, bktlbj и энергии самой пары ЬкЬг Величина наименьшей энергии структуры, построенной на отрезке bjbj, записывается в матрицу MiiJt а позиция bk, при которой получена эта величина в матрицу К, . Такой индуктивный метод позволяет быстро подсчитать энергию. Построение вторичной структуры с наименьшей свободной энергией происходит в обратном порядке - от анализа всей последовательности b, п к минимально возможным фрагментам. В итоге определяется структура с наименьшей свободной энергией. Время, необходимое для выбора энергетически оптимальной структуры, пропорционально п3.
К числу наиболее популярных методов предсказания вторичной структуры относится также алгоритм, предложенный Дукером и Стиглером (Zuker, Stiegler,1981). Идея их индуктивного подхода очень проста. Рассматривается небольшой фрагмент нуклеотидной последовательности. На нем выбирается структура с наименьшей свободной энергией. Ha. следующем шаге фрагмент увеличивается на один нуклеотид.При анализе возможных вторичных структур предполагается, что выбранная на предыдущем этапе структура является частью вновь образованной. Поэтому необходимо вычислить энергию только тех возможных элементов вторичной структуры, которые образуются при элонгации цепи. Затем выбрать минимальную структуру и перейти к следующему этапу. На последнем этапе вычисляется энергия структуры, сформированной уже всей цепью.
На рис.6.7 представлены элементы вторичной структуры, которые анализируются в этой работе. Выделяются два типа вторичных структур: 1)
структуры, в которых концевые нуклеотиды i и j образуют комплементар-
ную пару между собой; 2) структуры, в которых нуклеотиды i и j не свя заны друг с другом.
Все варианты структур первого типа показаны на рис. 6.7,а,б,в. Б первом случае в структуре присутствует только одна петля типа шпильки. Обозначим энергию - Е1, . Если в структуре существует ровно две пет-
ли, одна петля - обязательно шпилька, а вторая может быть внутренней или боковой (рис.6.?,б). Тогда энергию такой структуры Е2, } можно представить как сумму энергий двух составляющих частей структуры -Е1М , в этой части присутствует только одна петля, замкнутая нуклеотидами il и ji, и эн*1]-,гии остальной пасти - Е Энергия структуры Е2, j равно* Е2, Я,, ,, + Е, И, к?кочец, е -г* в структуре больше
двух петель, то ?;'¦(. мсжно пред- :-явул 1 как :*умглу энергий двух
частей структуры \рис.6.7,и): ЕЭ, 1 - E1 + I>1| + E11 + liJ-,- Аналогично рассматривается и второй вариант, в ко-гпром краевые нуклеотиды не образуют пару друг с другом. Минимальная свободная энергия структуры рассчитывается, используя полученные подобным образом реккурентные формулы.
Рис. 6.7. Типы вторичных структур РНК. Вторичные структуры, в которой концевые нуклеотиды i и j образуют пару друг с другом
а - в структуре присутствует только одна петля; б - в структуре присутствуют две петли; в - общий случай: в структуре присутствуют
