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

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

Для чего строят множественные выравнивания? позволяет оценить эволюционные отношения Построение множественных выравниваний необходимый этап решения многих задач молекулярной биологии поиск активного центра позволяет найти общее мотивы, паттерны, профили предсказание 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 (ищет блоки, то есть выравнивания без пропусков)

Форматы хранения выравниваний Fasta Aln (он же Clustal) MSF (Multiple sequence format) PHYLIP NEXUS … См. Всё это текстовые файлы!

Редакторы выравниваний GeneDoc (установлен у нас) BioEdit (тоже установлен) Mega (тоже установлена) JalView ClustalX … См.