Множественное выравнивание

Обобщение парного выравнивания Выравнивание 2-х последовательностей – двумерная матрица 3-х последовательностей – 3-х мерная. A T _ G C G _ A _ C G T _ A A T C A C _ A Задача: больше консервативных столбцов, лучше выравнивание

Глобальное выравнивание 3-х последовательностей начало конец

2-D versus 2-D В 3-D - 7 В 2-D, 3 пути прихода в узел

3-D архитектура (i-1,j-1,k-1) (i,j-1,k-1) (i,j-1,k) (i-1,j-1,k) (i-1,j,k) (i,j,k) (i-1,j,k-1) (i,j,k-1)

Алгоритм s i,j,k = max (x, y, z) – запись в трехмерной матрице весов s i-1,j-1,k-1 + (v i, w j, u k ) s i-1,j-1,k + (v i, w j, _ ) s i-1,j,k-1 + (v i, _, u k ) s i,j-1,k-1 + (_, w j, u k ) s i-1,j,k + (v i, _, _) s i,j-1,k + (_, w j, _) s i,j,k-1 + (_, _, u k ) Нет гэпов Один гэп Два гэпа

Время работы алгоритма Для 3-х последовательностей длины n, время работы - 7n^3; O(n^3) Для k последовательностей - (2k-1)(n^k); O(2kn^k)

Множественное выравнивание порождает парные выравнивания x:AC-GCGG-C y:AC-GC-GAG z:GCCGC-GAG Порождает: x: ACGCGG-C; x: AC-GCGG-C; y: AC-GCGAG y: ACGC-GAC; z: GCCGC-GAG; z: GCCGCGAG

Обратная проблема Имея 3 субъективных парных варнивания: x: ACGCGG-C; x: AC-GCGG-C; y: AC-GCGAG y: ACGC-GAC; z: GCCGC-GAG; z: GCCGCGAG Можем ли мы вычислить множественное выравнивание, их порождающее?

Хороший вариант Плохой вариант Ответ – не всегда.

Выравнивание выравниваний x GGGCACTGCAT y GGTTACGTC-- Alignment 1 z GGGAACTGCAG w GGACGTACC-- Alignment 2 v GGACCT-----

Профили x GGGCACTGCAT y GGTTACGTC-- Combined Alignment z GGGAACTGCAG w GGACGTACC-- v GGACCT----- GTCTGA GTCAGC GTC t/a G a/c A

Множественное выравнивание – жадный алгоритм u 1 = ACGTACGTACGT… u 2 = TTAATTAATTAA… u 3 = ACTACTACTACT… … u k = CCGGCCGGCCGG u 1 = ACg/tTACg/tTACg/cT… u 2 = TTAATTAATTAA… … u k = CCGGCCGGCCGG… k k-1

ClustalW Прогрессивное выравнивание – жадный алгоритм с более «умным» способом выбора пар. Три шага 1.) Построить парные выравнивания 2.) Построить дерево-подсказку 3.) Прогрессивное выравнивание по дереву-подсказке Прогрессивное выравнивание

Шаг 1: Парные Выравнивания Выравнивания пар порождают матрицу identity v 1 v 2 v 3 v 4 v 1 - v v v (.17 значит идентичны на 17 % )

Шаг 2: Дерево-подсказка v1v3v4v2v1v3v4v2 Далее вычислить: v 1,3 = выравнивание (v 1, v 3 ) v 1,3,4 = выравнивание ((v 1,3 ),v 4 ) v 1,2,3,4 = выравнивание ((v 1,3,4 ),v 2 ) v 1 v 2 v 3 v 4 v 1 - v v v

Шаг 3: Прогрессивное выравнивание Выравниванием 2 наиболее близких последовательности. Следуя дереву - подсказке, довыравниваем следующую последовательность к имеющемуся выравниванию FOS_RAT PEEMSVTS-LDLTGGLPEATTPESEEAFTLPLLNDPEPK-PSLEPVKNISNMELKAEPFD FOS_MOUSE PEEMSVAS-LDLTGGLPEASTPESEEAFTLPLLNDPEPK-PSLEPVKSISNVELKAEPFD FOS_CHICK SEELAAATALDLG----APSPAAAEEAFALPLMTEAPPAVPPKEPSG--SGLELKAEPFD FOSB_MOUSE PGPGPLAEVRDLPG-----STSAKEDGFGWLLPPPPPPP LPFQ FOSB_HUMAN PGPGPLAEVRDLPG-----SAPAKEDGFSWLLPPPPPPP LPFQ.. : **. :.. *:.* *. * **: Точки и звезды отображают насколько консервативны столбцы.

Множественные Выравнивания: Взвешивание Количество полных совпадений Энтропия Сумма по парам (SP-Score)

LCS Score Хорошо только для очень близких последовательностей AAA AAT ATC

Энтропия Определим вероятности букв в столбцах p A = 1, p T =p G =p C =0 (1 -ый столбец ) p A = 0.75, p T = 0.25, p G =p C =0 (2 -ый столбец ) p A = 0.50, p T = 0.25, p C =0.25 p G =0 (3 -ий столбец ) Энтропия столбца будет равна AAA AAT ATC

Энтропия: Пример Лучший вариант Худший вариант

Энтропия: Пример Энтропия столбца: -( p A logp A + p C logp C + p G logp G + p T logp T ) Столбец 1 = -[1*log(1) + 0*log0 + 0*log0 +0*log0] = 0 Столбец 2 = -[( 1 / 4 )*log( 1 / 4 ) + ( 3 / 4 )*log( 3 / 4 ) + 0*log0 + 0*log0] = -[ ( 1 / 4 )*(-2) + ( 3 / 4 )*(-.415) ] = Столбец 3 = -[( 1 / 4 )*log( 1 / 4 )+( 1 / 4 )*log( 1 / 4 )+( 1 / 4 )*log( 1 / 4 ) +( 1 / 4 )*log( 1 / 4 )] = 4* -[( 1 / 4 )*(-2)] = +2.0 Энтропия выравнивания = = AAA ACC ACG ACT

Сумма по парам (SP-Score) Построим парное выравнивание по множественному Посчитаем веса всех этих парных выравниваний - s*(a i, a j ) Просуммируем : s(a 1, …,a k ) = Σ i,j s*(a i, a j )

Проекции на плоскости 3-D выравнивание может быть спроецировано на 2-D плоскость чтобы получить порождаемое парное выравнивание.