Компьютерный анализ генетических текстов - Александров А.А.
ISBN 5-02-004691-4
Скачать (прямая ссылка):
динамического программирования, например алгоритмом Мурата, выравниваются три последовательности, одна из которых является предшествующей версией пра-последовательности, а две другие соеденены с ней ребрами дерева. По результатам этого выравнивания строится новая пра-последовательность. Итеративная процедура осуществляется от висячих вершин к корню дерева. Общий ход итеративной процедуры представлен на рис. 4.11,а-г. Когда все пра-последовательности будут скорректированы, процесс повторяется в обратном порядке: вычисления проводятся в направлении г-а. Как только полный итеративный цикл пройдет в двух направлениях без изменения пра-последовательностей, алгоритм останавливается. Во всех проведенных испытаниях сходимость наступала до пятого цикла. Авторы отмечают, что алгоритм не гарантирует достижения глобального оптимума выравнивания.
Похожие алгоритмы, использующие итеративные процедуры для вывода
Рис. 4.10. Множественное выравнивание с помощью филогенетического дерева
А-Г - этапы реализации алгоритма
консенсусной последовательности, были независимо предложены Уотерманом с соавт. (Waterman et al., 1984) и Бэйнсом (Bains, 1986). Уотерман применил интересную геометрическую интерпретацию проблемы выравнивания, введя метрику в пространстве последовательностей. Чтобы вычислить расстояние D(a,b) между двумя последовательностями a=ata2...an и b=b,b2... bn, применяется стандартная рекурсивная процедура динамического программирования:
DtJ= min{Di_1J+d(ai,o),DI_liJ_1+d(ai,bj), D,_j_1+d(o,bJ)}
с начальными условиями:
DOJ-D(0,b1...bJ); D10=D(а,.. .а,,0); Doo=0,
где о соответствует вставке; 0=оо...; ad(ai,bj) - расстояние между буквами последовательности.
Особенностью применяемого алгоритма является введение понятия усредненной последовательности, каждой позиции которой соответствует не конкретная буква, а вектор (р0,р,,р2...), где Pj>=0 и ? р,=1
(для нуклеотидных последовательностей i<4, для белков i<20). Из любых выровненных последовательностей можно вывести усредненную, если интерпретировать р( как частоту встречи i-й буквы алфавита в данной позиции, а р0 - вставки v. Расстояние между двумя буквами усредненных последовательностей ai=(p0p,p2...) и b.=(q0q1q2...) равно
d(a1,bj) = (Е vjpk-qjf)1/f, k
где vk - вес, a f>l - параметр.
Кроме метрики в пространстве вводится операция сложения последовательностей: с( 1 ) = 1 а+(1-1)Ь, где с,(1)=1 а^Ц-ПЬ,. Нужно
Рис. 4.11. Геометрическое выравнивание последовательностей
а?
помнить, что а4,Ь,,с, - векторы. Параметр 1 характеризует
относительную значимость усредненной последовательности а: чем
больше последовательностей принимало участие в формировании а, тем больше 1.
Теперь представим выравниваемые последовательности в виде точек (рис. 4.11). Усредненная последовательность (консенсус) будет совпадать с центром тяжести первоначальных точек. Последовательность консенсуса определяется итерационным алгоритмом, каждый шаг которого заключается в вычислении последовательностей, лежащих на середине отрезков, соединяющих первоначальные точки а1, а2 и а3:
b'=(a'+a2)/2; b2=(a'+a2)/2; b3=(a2+a3)/2.
Далее в качестве первоначальных точек рассматриваем b',b2,b3 и снова вычисляем координаты середин сторон треугольника. Продолжаем процесс до тех пор, пока сумма расстояний между вновь образованными точками не станет меньше наперед заданного числа е. Сходимость алгоритма очень медленная и время работы растет экспоненциально с ростом числа последовательностей. Метрика последовательностей не является евклидовой, и поэтому нельзя применить известные эффективные способы поиска центра тяжести точек. Быть может, при детальном изучении Уотермановской или
подобных метрик удастся предложить более совершенный метод геометрирческого выравнивания последовательностей.
Эвристический алгоритм Бзйнса (Bains, 1986) проиллюстрирован на
1) Исходные последовательности:
1¦ TGCTTTCGTCA
2. GCTTCGTA (начальный консенсус)
3. GCTTCGGTCA
2) Попарное выравнивание:
консенсус -GC-TTCGT-A GCTTCGTA GCTTC-GT-A
1. TGCTTTCGTCA 2. GCTTCGTA 3. GCTTCGGTCA
3) Введение вставок во все последовательности:
консенсус -GC-TTC-GT-A -GC-TTC-GT-A -GC-TTC-GT-A
1. TGCTTTC-GTCA 2. -GC-TTC-GT-A 3. -GC-TTCGGTCA
4) Компиляция полученных последовательностей:
консенсус -GC-TTC-GT-A
1. TGCTTTC-GTCA
2. -GC-TTC-GT-A
3. -GC-TTCGGTCA
5) Новый консенсус:
-GC-TTCGGTCA Рис. 4.12. Иллюстрация алгоритма Бзйнса
рис. 4.12. В первом приближении консенсусом объявляется любая из последовательностей. Производится попарное выравнивание каждой последовательности с консенсусом. Все вставки в консенсусе фиксируются и таким образом вводятся во все остальные последовательности. После этого из компиляции выровненных таким образоми последовательностей выводится новый консенсус и цикл повторяется. Если консенсус не изменился после прохождения цикла, алгоритм заканчивается. Брзйнс отмечает, что алгоритм может зациклиться; но в программе есть против этого защита, предусматривающая наличие не одного, а нескольких конечных консенсусов. Более серьезные трудности возникают, если алгоритм просто не сходится. Тем не менее алгоритмом можно пользоваться для одновременого выравнивания нескольких десятков похожих последовательностей длиной до 1000 нуклеотидов.
