Мно́жественное выра́внивание после́довательностей () — выравнивание трёх и более биологических последовательностей, обычно белков, ДНК или РНК. В большинстве случаев предполагается, что входной набор последовательностей имеет эволюционную связь. Используя множественное выравнивание, можно оценить эволюционное происхождение последовательностей, проведя филогенетический анализ.
Визуальное представление выравнивания иллюстрирует мутационные события как точечные мутации (изменение одной аминокислоты или одного нуклеотида) в виде различающихся символов в одной колонке выравнивания, а также их вставки и делеции (изображаются знаком дефиса, гэпы).
Множественное выравнивание последовательностей часто используется для оценки консервативности доменов белков, третичных и вторичных структур и даже отдельных аминокислотных остатков или нуклеотидов.
Ввиду большей вычислительной сложности по сравнению с парным выравниванием множественное выравнивание требует более сложные алгоритмы. Многие соответствующие программы используют эвристические алгоритмы, поскольку поиск глобального оптимального выравнивания для многих последовательностей может занимать очень большое время.
Динамическое программирование и вычислительная сложность Для построения глобального оптимального выравнивания напрямую используется динамическое программирование. Для белковых последовательностей существует два набора параметров: штраф за гэп и матрица замен, содержащая в себе вероятности сопоставления пары аминокислотных остатков, основанных на схожести их химических свойств и эволюционной вероятности мутации. Для нуклеотидных последовательностей также используется штраф за гэп, но матрица замен гораздо проще, в ней учитываются только полные совпадения нуклеотидов или мисматчи, т. е. полные несовпадения.
Для n отдельных последовательностей наивный метод требует построения n-мерного эквивалента матрицы, которую используют для парного выравнивания. С ростом n пространство поиска возрастает экспоненциально. Таким образом, наивный алгоритм имеет вычислительную сложность O(Длина последовательностейNпоследовательностей). Поиск глобального оптимума для n последовательностей относится к NP-полным задачам.
В 1989 году на основе алгоритма Каррильо — Липмана Альтшуль представил практический подход, который использовал парные выравнивания для ограничения n-мерного пространства поиска. При таком подходе динамическое программирование выполняется на каждой паре последовательностей из входного набора и ищется только область, расположенная вблизи n-мерного пересечения этих путей. Программа оптимизирует сумму всех пар символов в каждой позиции в выравнивании (сумма парных весов)
Прогрессивное выравнивание Широко используемый подход — прогрессивное выравнивание, применяющий эвристический алгоритм, разработан Paulien Hogeweg and Ben Hesper в 1984 году. Все методы прогрессивного выравнивания имеют две важные стадии: построение бинарного дерева (путеводное дерево), где листья являются последовательностями, и построение множественного выравнивания путём добавления последовательностей к растущему выравниванию согласно путеводному дереву. Само путеводное дерево может быть построено кластеризующими методами, такими как и метод присоединения соседей.
Прогрессивное выравнивание не гарантирует получение глобального оптимального выравнивания. Проблема состоит в том, что ошибки, полученные на любой стадии растущего множественного выравнивания, доходят до конечного выравнивания. Кроме того, выравнивание может быть особенно плохим в случае набора сильно отдалённых друг от друга последовательностей. Большинство современных прогрессивных методов имеют изменённую функцию вычисления веса со вторичной весовой функцией, которая присваивает коэффициенты для отдельных элементов набора данных в виде нелинейной моды основанной на их филогенетическом расстоянии от ближайших соседей.
Методы прогрессивного выравнивания достаточно эффективны, чтобы применять их для большого числа (100-1000) последовательностей. Самый популярный метод прогрессивного выравнивания принадлежит к семейству Clustal, в частности, взвешенный вариант ClustalW, доступ к которому можно получить через такие порталы как GenomeNet, EBI, EMBNet . ClustalW активно используется для построения филогенетических деревьев, несмотря на предупреждения автора, что непроверенные вручную выравнивания не должны использоваться ни при построении деревьев, ни в качестве входных данных для предсказания структуры белков. Текущая версия Clustal — Clustal Omega, которая работает на основе путеводных деревьев и HMM профиль-профильных методов для белковых выравниваний. Также предлагаются различные инструменты для построения прогрессивного выравнивания последовательностей ДНК. Один из них – MAFFT ().
Другой распространённый метод прогрессивного выравнивания, T-Coffee, медленнее, чем Clustal и его производные, но в основном даёт более точные выравнивания для отдалённо связанных последовательностей. T-Coffee строит библиотеку парных выравниваний, которую затем использует для построения множественного выравнивания.
Поскольку прогрессивные методы являются эвристическими, они не гарантируют схождения к глобальному оптимуму; качество выравнивания и его биологическое значение бывает трудно оценить. Полупрогрессивный метод, который улучшает качество выравнивания и не использует эвристику c потерями, справляется за полиномиальное время (PSAlign ).
Итеративные методы Набор методов для построения множественных выравниваний, в которых происходит снижение ошибок, наследуемых в прогрессивных методах, классифицируют как «итеративные». Они работают аналогично прогрессивным методам, но при этом неоднократно перестраивают исходные выравнивания при добавлении новых последовательностей. Прогрессивные методы сильно зависят от качества начальных выравниваний, поскольку они в неизменном виде, а стало быть и с ошибками, попадут в конечный результат. Иными словами, если последовательность уже попала в выравнивание, её дальнейшее положение не изменится. Такое приближение улучшает эффективность, но отрицательно сказывается на точности результата. В отличие от прогрессивных методов, итеративные методы могут возвращаться к первоначально посчитанным парным выравниваниям и подвыравниваниям, содержащим подмножества последовательностей из запроса, и таким образом оптимизировать общую целевую функцию и повышать качество.
Существует большое количество разнообразных итеративных методов. Например, PRRN/PRRP использует алгоритм восхождения к вершине для оптимизации веса множественного выравнивания и итеративно корректирует веса выравнивания и области со множеством гэпов. PRRP работает эффективнее, когда улучшает выравнивание, предварительно построенное быстрым методом.
Ещё одна итеративная программа, DIALIGN, использует необычный подход, сосредотачивая внимание на локальных выравниваниях подсегментов или мотивов последовательностей без введения штрафа за гэп. Выравнивание отдельных мотивов представляется в матричном виде, сходном с диаграммой с точками (dot-plot) в парном выравнивании. Альтернативный метод, который использует быстрые локальные выравнивания как точки заякоривания для более медленной процедуры построения глобального выравнивания, представлен в софте CHAOS/DIALIGN.
Третий популярный итерационный метод называется MUSCLE. Он улучшен по сравнению с прогрессивными методами, поскольку использует более точные расстояния для оценки связи двух последовательностей. Расстояния обновляются между итерациями (хотя в первоначальном виде MUSCLE содержал только 2—3 итерации).
Консенсусные методы Консенсусные методы пытаются выбрать оптимальное множественное выравнивание из различных множественных выравниваний одного и того же набора входных данных. Существуют два наиболее распространённых консенсусных метода: M-COFFEE и MergeAlign. M-COFFEE использует множественные выравнивания, генерируемые 7 различными методами для получения консенсусных выравниваний. MergeAlign способен генерировать консенсусные выравнивания из любого числа входных выравниваний, полученных из различных моделей эволюции последовательности и методов построения. Опция по умолчанию для MergeAlign — выведение консенсусного выравнивания, используя выравнивания, полученные из 91 различных моделей эволюции белковой последовательности.
Скрытые марковские модели Скрытые марковские модели (HMMs) — вероятностные модели, которые могут оценить правдоподобие для всех возможных комбинаций гэпов, совпадений или несовпадений для того, чтобы определить наиболее вероятное множественное выравнивание или их набор. HMMs могут давать одно выравнивание с высоким весом, но также могут генерировать семейство возможных выравниваний, которые затем могут быть оценены по их биологической значимости. HMMs могут быть использованы для получения как глобальных, так и локальных выравниваний. Несмотря на то, что методы, основанные на HMM, появились сравнительно недавно, они зарекомендовали себя как методы со значительными улучшениями вычислительной сложности, особенно для последовательностей, содержащих перекрывающиеся области.
Стандартные методы, основанные на HMM, представляют множественное выравнивание в виде направленного ациклического графа, известного как граф частичного порядка, который состоит из серий узлов, представляющих собой возможные состояния в колонках выравнивания. В этом представлении абсолютно консервативная колонка (т. е. последовательности во множественном выравнивании имеют в этой позиции определённый символ) кодируется как один узел со множеством исходящих соединений с символами, возможными в следующей позиции выравнивания. В терминах стандартной скрытой марковской модели наблюдаемые состояния — отдельные колонки выравнивания, а «скрытые» состояния представляют собой предполагаемую предковую последовательность, от которой последовательности из входного набора могли произойти. Эффективный метод динамического программирования, алгоритм Витерби, широко используется для получения хорошего выравнивания. Он отличается от прогрессивных методов тем, что выравнивание первых последовательностей перестраивается при добавлении каждой новой последовательности. Тем не менее, как и прогрессивные методы, на этот алгоритм может повлиять порядок, в котором последовательности из входного набора поступают в выравнивание, особенно в случае эволюционно слабо связанных последовательностей.
Несмотря на то, что HMM-методы более сложны, чем часто используемые прогрессивные методы, существует несколько программ для получения выравниваний, например, POA, а также похожий, но более обобщённый метод в пакетах SAMHughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996. и HMMER. SAM используется для получения выравниваний для предсказания структуры белков в эксперименте CASP для дрожжевых белков. HHsearch, основанный на парном сравнении HMMs, используется для поиска отдалённо связанных последовательностей. Сервер, запускающий HHsearch (HHpred) был самым быстрым из 10 лучших автоматических серверов по предсказанию структур белков в CASP7 и CASP8.
Генетические алгоритмы и моделирование отжига