Научная литература
booksshare.net -> Добавить материал -> Биология -> Александров А.А. -> "Компьютерный анализ генетических текстов" -> 66

Компьютерный анализ генетических текстов - Александров А.А.

Александров А.А., Александров Н.Н., Бородовский М.Ю. Компьютерный анализ генетических текстов — М.:Наука , 1990. — 267 c.
ISBN 5-02-004691-4
Скачать (прямая ссылка): komputerniyanalizgeneticheskihtextov1990.djv
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 119 >> Следующая

выравнивание.
Собел и Мартинец предложили использовать-очень простую рекурсивную процедуру поиска такого набора регионов. Пусть v(X) - вес оптимального выравнивания последовательностей от первого нуклеотида до региона X. Следующим шагом нам надо определить, какой из дальнейших регионов выгоднее включить в это выравнивание. Предлагается включить такой регион Y, на котором достигается максимум весовой функции v(Y)
v(Y) = max { 1(Y) - d(X,Y) + v(X) },
где 1(Y) - длина региона Y, a d(X,Y) - штраф за пропуски между регионами X и Y. Штраф вводится так, чтобы он зависел от суммарной по всем последовательностям длины вставок между регионами X и Y.
К недостаткам алгоритма относятся два жестких требования: точное совпадение сегментов, образующих регион и обязательное их наличие вс всех выравниваемых последовательностях. Впрочем, нестрогое совпадение длинного слова можно представить в виде точных совпадений фрагментов меньшей длины, а второе требование авторы предлагают ослабить введением еще одного параметра алгоритма - числом последовательностей, включающих в себя общий сегмент. Например, при выравнивании пяти последовательностей достаточно встретить сегмент в четырех из них, чтобы он считался общим.
Этот подход значительно развил Уотерман (Waterman, 1986), естественным образом устранив указанные недостатки. Пусть набор из R последовательностей длины N изначально выровнен относительно какой-нибудь биологически определенной позиции. Это может быть, к примеру, точка инициации транскрипции для промоторов или место соединения эк-зона с интроном для сайтов сплайсинга. Такое выравнивание является, конечно, приблизительным. Цель алгоритма - выровнить последовательно::’ так, чтобы похожие участки были бы расположены друг под другом. В качестве параметра, определяющего возможное относительное смещение участков, вводится ширина окна w. Рассмотрим фрагменты последовательности длиной w, начинающиеся с (j+D-й буквы:
ai . j + 1 ai ,jt2 ' * • ai , J*w’
a2 , j + 1 a2,J*2 ’ * * a2,j<-w’
aR.j*l aR,j*2 • ’ * aR,jtw‘
Найдем в этих фрагментах слова, совпадающие или близкие к слову-s. Если найденное слово отличается от s в t позициях, будем называть его t соседом. Пусть qs_t - число строк, в которых наиболее близкое к v слово является t соседом. При этом обычно ограничиваются значениями t=0,1,2. Каждому из t соседов приписывается вес lt. Вычислим вес слова s в данном окне по формуле
vJMij.w(s)- 2 ltqs t•
Наилучшим словом будет слово s', удовлетворяющее условию
max
Теперь упорядочим слова: s,<s2, если слово s, встречается
всегда левее s2 и не пересекается с ним. При этом не обязательно их присутствие во всех последовательностях. В этих терминах постановка задачи проста: нужно найти слова удовлетворяющие условию
max{ Е v(Sj): s,<s2<... }.
Но, как часто бывает, простота формулировки вовсе не подразумевает простоту решения и достичь поставленной цели за разумное время не представляется возможным. Тем не менее можно придумать алгоритмы, позволяющие подойти довольно близко к максимуму.
Для этого предлагается простая рекурсия. Положим vt - максимум суммы от первой буквы последовательности до i-й. Тогда v1=max{vJ+vJ + 1>1: i-w+l<j<i-k), где vJtlii - вес наилучшего
консенсусного слова в окне от j+1 до i, а к - длина слова. Предложенный алгоритм требует времени пропорционально Nw2R и был проверен на 34 последовательностях, кодирующих 5S РНК (-100 нуклеотидов). Единственным ограничением алгоритма является ширина окна w, определяющая максимальное расстояние между гомологичными участками.
Использование консенсуса. Интересными представляются алгоритмы, основанные на построении пра-последовательности, или консенсуса. Эти два термина означают одно и то же, хотя и употребляются в разных контекстах: пра-последовательность имеет эволюционный оттенок, а Консенсус - функциональный. Именно в этих алгоритмах нашло свое от-
ражение тесное переплетение двух задач компьютерной генетики - распознавания сайтов и множественного выравнивания.
Первым такой подход разработал Санкофф (Sankoff, 1975) и применил его для выравнивания ББ-рибосомальных РНК. Кроме первичной структуры молекул в качестве исходной информации использовалось филогенетическое дерево организмов, из которых были выделены 5S-PHK. Однако знание этого дерева a priori не является обязательным, так как оно может быть восстанавлено по последовательностям введением метрики прт/ попарном выравнивании. Рассмотрим в качестве примера дерево для девяти последовательностей на рис. 4.10,а. Каждая из висячих вершин 1-9 соответствует реальной последовательности, а каждой внутренней вершине ставится в соответствие некая пра-последовательность. Вначале все пра-последовательности полагаются равными любой из близлежащих реальных последовательностей. Для получение новых пра-последовательностей использовалась следующая итеративная процедура: методами
Предыдущая << 1 .. 60 61 62 63 64 65 < 66 > 67 68 69 70 71 72 .. 119 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed