Множественное выравнивание С.А.Спирин, весна 2009. - презентация

1 Множественное выравнивание С.А.Спирин, весна 2009

2 Множественное выравнивание … это то же, что парное, только последовательностей сколько угодно

3 Для чего строят множественные выравнивания? позволяет оценить эволюционные отношения Построение множественных выравниваний необходимый этап решения многих задач молекулярной биологии поиск активного центра позволяет найти общее мотивы, паттерны, профили предсказание 3D-структуры реконструкция эволюции

4 Множественное выравнивание гомеодоменов Красным выделены консервативные (одинаковые у всех) остатки; желтым – на 80% консервативные (одинаковые почти у всех) остатки Красным выделены консервативные и функционально консервативные остатки

5 Биологический смысл Тот же, что у парного: сопоставляемые остатки разных белков должны: иметь общее происхождение; выполнять аналогичную функцию; одинаково располагаться в пространстве.

6 Парное и множественное выравнивание 1.Любое множественное выравнивание порождает набор парных выравниваний 2. Не любой набор парных выравниваний можно просто "сложить" во множественное выравнивание. Пример: P1 ALGTEEIC- P2 ALGT--IAA + P1 AL-GTEEI-C P1 AL-GTEEI-C P2 AL-GT--IAA P3 ALVGTE-IAC + P2 AL-GT-IAA P3 ALVGTEIAC

7 (С) А.Б.Рахманинова Змей-Горыныч биоинформатики Биологическая задача поставить друг под другом гомологичные позиции Математическая задача найти способ количественного сравнения качества выравниваний. Программирование создание эффективного алгоритма и его реализация

8 Парное выравнивание: вес >P1 ALGTEEIC >P2 ALGTIAA Две последовательности:Параметры: матрица замен штрафы за пропуски Алгоритм Нидельмана – Вунша Алгоритм Смита – Ватермана P1 ALGTEEIC- P2 ALGT--IAA P1 ALGT P2 ALGT Оптимальное полное выравниваниеОптимальное частичное выравнивание

9 Множественное выравнивание Можно определить вес (хотя ситуация со штрафом за пропуски сложнее) Но не существует приемлемого алгоритма, гарантирующего нахождение оптимального по данному весу выравнивания Аналог алгоритма Нидельмана – Вунша имеет приемлемое время работы лишь для очень малого числа последовательностей (до 4–5)

10 Руководящее дерево Очевидные недостатки : результат зависит от порядка выравниваний; «один раз гэп – всегда гэп» Алгоритм ClustalW – пример эвристического прогрессивного алгоритма

11 Программы множественного выравнивания ClustalW – к настоящему времени явно устарела, но по-прежнему очень популярна Muscle – пожалуй, на текущий момент программа первого выбора MAFFT – тоже очень популярная программа DiAlign T-Coffee Kalign ProbCons Всё это программы полного выравнивания Единственная популярная программа частичного множественного выравнивания – MEME (ищет блоки, то есть выравнивания без пропусков)