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

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

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

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

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

Парное и множественное выравнивание 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

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

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

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

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

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