Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 11 лет назад пользователемНикита Яхно
1 Множественное выравнивание
2 Обобщение парного выравнивания Выравнивание 2-х последовательностей – двумерная матрица 3-х последовательностей – 3-х мерная. A T _ G C G _ A _ C G T _ A A T C A C _ A Задача: больше консервативных столбцов, лучше выравнивание
3 Глобальное выравнивание 3-х последовательностей начало конец
4 2-D versus 2-D В 3-D - 7 В 2-D, 3 пути прихода в узел
5 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)
6 Алгоритм 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 ) Нет гэпов Один гэп Два гэпа
7 Время работы алгоритма Для 3-х последовательностей длины n, время работы - 7n^3; O(n^3) Для k последовательностей - (2k-1)(n^k); O(2kn^k)
8 Множественное выравнивание порождает парные выравнивания 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
9 Обратная проблема Имея 3 субъективных парных варнивания: x: ACGCGG-C; x: AC-GCGG-C; y: AC-GCGAG y: ACGC-GAC; z: GCCGC-GAG; z: GCCGCGAG Можем ли мы вычислить множественное выравнивание, их порождающее?
10 Хороший вариант Плохой вариант Ответ – не всегда.
11 Выравнивание выравниваний x GGGCACTGCAT y GGTTACGTC-- Alignment 1 z GGGAACTGCAG w GGACGTACC-- Alignment 2 v GGACCT-----
12 Профили x GGGCACTGCAT y GGTTACGTC-- Combined Alignment z GGGAACTGCAG w GGACGTACC-- v GGACCT----- GTCTGA GTCAGC GTC t/a G a/c A
13 Множественное выравнивание – жадный алгоритм 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
14 ClustalW Прогрессивное выравнивание – жадный алгоритм с более «умным» способом выбора пар. Три шага 1.) Построить парные выравнивания 2.) Построить дерево-подсказку 3.) Прогрессивное выравнивание по дереву-подсказке Прогрессивное выравнивание
15 Шаг 1: Парные Выравнивания Выравнивания пар порождают матрицу identity v 1 v 2 v 3 v 4 v 1 - v v v (.17 значит идентичны на 17 % )
16 Шаг 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
17 Шаг 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.. : **. :.. *:.* *. * **: Точки и звезды отображают насколько консервативны столбцы.
18 Множественные Выравнивания: Взвешивание Количество полных совпадений Энтропия Сумма по парам (SP-Score)
19 LCS Score Хорошо только для очень близких последовательностей AAA AAT ATC
20 Энтропия Определим вероятности букв в столбцах 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
21 Энтропия: Пример Лучший вариант Худший вариант
22 Энтропия: Пример Энтропия столбца: -( 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
23 Сумма по парам (SP-Score) Построим парное выравнивание по множественному Посчитаем веса всех этих парных выравниваний - s*(a i, a j ) Просуммируем : s(a 1, …,a k ) = Σ i,j s*(a i, a j )
24 Проекции на плоскости 3-D выравнивание может быть спроецировано на 2-D плоскость чтобы получить порождаемое парное выравнивание.
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.