Мно́жественное выра́внивание после́довательностей (англ. multiple sequence alignment, MSA) — выравнивание трёх и более биологических последовательностей, обычно белков, ДНК или РНК. В большинстве случаев предполагается, что входной набор последовательностей имеет эволюционную связь. Используя множественное выравнивание, можно оценить эволюционное происхождение последовательностей, проведя филогенетический анализ.
Визуальное представление выравнивания иллюстрирует мутационные события как точечные мутации (изменение одной аминокислоты или одного нуклеотида) в виде различающихся символов в одной колонке выравнивания, а также их вставки и делеции (изображаются знаком дефиса, гэпы).
Множественное выравнивание последовательностей часто используется для оценки консервативности доменов белков, третичных и вторичных структур и даже отдельных аминокислотных остатков или нуклеотидов.
Ввиду большей вычислительной сложности по сравнению с парным выравниванием множественное выравнивание требует более сложные алгоритмы. Многие соответствующие программы используют эвристические алгоритмы, поскольку поиск глобального оптимального выравнивания для многих последовательностей может занимать очень большое время.
Динамическое программирование и вычислительная сложность
Для построения глобального оптимального выравнивания напрямую используется динамическое программирование. Для белковых последовательностей существует два набора параметров: штраф за гэп и матрица замен, содержащая в себе вероятности сопоставления пары аминокислотных остатков, основанных на схожести их химических свойств и эволюционной вероятности мутации. Для нуклеотидных последовательностей также используется штраф за гэп, но матрица замен гораздо проще, в ней учитываются только полные совпадения нуклеотидов или мисматчи, т. е. полные несовпадения.
Для n отдельных последовательностей наивный метод требует построения n-мерного эквивалента матрицы, которую используют для парного выравнивания. С ростом n пространство поиска возрастает экспоненциально. Таким образом, наивный алгоритм имеет вычислительную сложность O(Длина последовательностейNпоследовательностей). Поиск глобального оптимума для n последовательностей относится к NP-полным задачам.
В 1989 году на основе алгоритма Каррильо — Липмана Альтшуль представил практический подход, который использовал парные выравнивания для ограничения n-мерного пространства поиска. При таком подходе динамическое программирование выполняется на каждой паре последовательностей из входного набора и ищется только область, расположенная вблизи n-мерного пересечения этих путей. Программа оптимизирует сумму всех пар символов в каждой позиции в выравнивании (сумма парных весов)
Прогрессивное выравнивание
Широко используемый подход — прогрессивное выравнивание, применяющий эвристический алгоритм, разработан Paulien Hogeweg and Ben Hesper в 1984 году. Все методы прогрессивного выравнивания имеют две важные стадии: построение бинарного дерева (путеводное дерево), где листья являются последовательностями, и построение множественного выравнивания путём добавления последовательностей к растущему выравниванию согласно путеводному дереву. Само путеводное дерево может быть построено кластеризующими методами, такими как UPGMA и метод присоединения соседей.
Прогрессивное выравнивание не гарантирует получение глобального оптимального выравнивания. Проблема состоит в том, что ошибки, полученные на любой стадии растущего множественного выравнивания, доходят до конечного выравнивания. Кроме того, выравнивание может быть особенно плохим в случае набора сильно отдалённых друг от друга последовательностей. Большинство современных прогрессивных методов имеют изменённую функцию вычисления веса со вторичной весовой функцией, которая присваивает коэффициенты для отдельных элементов набора данных в виде нелинейной моды основанной на их филогенетическом расстоянии от ближайших соседей.
Методы прогрессивного выравнивания достаточно эффективны, чтобы применять их для большого числа (100-1000) последовательностей. Самый популярный метод прогрессивного выравнивания принадлежит к семейству Clustal, в частности, взвешенный вариант ClustalW, доступ к которому можно получить через такие порталы как GenomeNet, EBI, EMBNet Архивная копия от 1 мая 2011 на Wayback Machine. ClustalW активно используется для построения филогенетических деревьев, несмотря на предупреждения автора, что непроверенные вручную выравнивания не должны использоваться ни при построении деревьев, ни в качестве входных данных для предсказания структуры белков. Текущая версия Clustal — Clustal Omega, которая работает на основе путеводных деревьев и HMM профиль-профильных методов для белковых выравниваний. Также предлагаются различные инструменты для построения прогрессивного выравнивания последовательностей ДНК. Один из них – MAFFT (англ. Multiple Alignment using Fast Fourier Transform).
Другой распространённый метод прогрессивного выравнивания, T-Coffee, медленнее, чем Clustal и его производные, но в основном даёт более точные выравнивания для отдалённо связанных последовательностей. T-Coffee строит библиотеку парных выравниваний, которую затем использует для построения множественного выравнивания.
Поскольку прогрессивные методы являются эвристическими, они не гарантируют схождения к глобальному оптимуму; качество выравнивания и его биологическое значение бывает трудно оценить. Полупрогрессивный метод, который улучшает качество выравнивания и не использует эвристику c потерями, справляется за полиномиальное время (PSAlign Архивная копия от 18 июля 2011 на Wayback Machine).
Итеративные методы
Набор методов для построения множественных выравниваний, в которых происходит снижение ошибок, наследуемых в прогрессивных методах, классифицируют как «итеративные». Они работают аналогично прогрессивным методам, но при этом неоднократно перестраивают исходные выравнивания при добавлении новых последовательностей. Прогрессивные методы сильно зависят от качества начальных выравниваний, поскольку они в неизменном виде, а стало быть и с ошибками, попадут в конечный результат. Иными словами, если последовательность уже попала в выравнивание, её дальнейшее положение не изменится. Такое приближение улучшает эффективность, но отрицательно сказывается на точности результата. В отличие от прогрессивных методов, итеративные методы могут возвращаться к первоначально посчитанным парным выравниваниям и подвыравниваниям, содержащим подмножества последовательностей из запроса, и таким образом оптимизировать общую целевую функцию и повышать качество.
Существует большое количество разнообразных итеративных методов. Например, 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, а также похожий, но более обобщённый метод в пакетах SAM и HMMER. SAM используется для получения выравниваний для предсказания структуры белков в эксперименте CASP для дрожжевых белков. HHsearch, основанный на парном сравнении HMMs, используется для поиска отдалённо связанных последовательностей. Сервер, запускающий HHsearch (HHpred) был самым быстрым из 10 лучших автоматических серверов по предсказанию структур белков в CASP7 и CASP8.
Генетические алгоритмы и моделирование отжига
Стандартные оптимизационные методы в компьютерной науке, которые позволяют моделировать, но не прямо воспроизводить физический процесс, также используются для более эффективного построения множественных выравниваний. Один из таких методов, генетический алгоритм, был использован для построения множественного выравнивания последовательностей, основанного на гипотетическом эволюционном процессе, который обеспечил расхождение последовательностей. Этот метод работает с помощью разделения серий возможных MSA на фрагменты и повторной переорганизации этих фрагментов со вводом разрывов в различные позиции. Основная целевая функция оптимизируется в ходе этого процесса обычно с помощью максимизации «сумм пар» методами динамического программирования. Этот метод реализован для белковых последовательностей в программном обеспечении SAGA (англ. Sequence Alignment by Genetic Algorithm), а для последовательностей РНК — в RAGA.
С помощью метода моделирования отжига существующее множественное выравнивание, построенное другим методом, уточняется в сериях перестроек для нахождения более хороших участков выравнивания, чем было до этого. Как и в случае генетического алгоритма, при моделировании отжига максимизируется целевая функция как функция сумм пар. В моделировании отжига используется условный «температурный фактор», который определяет уровень протекающих перестроек и уровень правдоподобности каждой перестройки. Типично использование чередующихся периодов с высоким уровнем перестроек и малым уровнем правдоподобия (для обнаружения наиболее удалённых регионов в выравнивании) с периодами с низким уровнем перестроек и высоким уровнем правдоподобия для более тщательного изучения локальных минимумов вблизи новых колонок выравнивания. Этот подход был осуществлён в программе MSASA (англ. Multiple Sequence Alignment by Simulated Annealing).
Методы, основанные на филогенетическом анализе
Большинство методов множественного выравнивания старается минимизировать количество вставок/делеций (гэпов), из-за чего продуцирует компактные выравнивания. Такой подход может привести к ошибкам в выравнивании, если выровненные последовательности содержали негомологичные регионы и если гэпы информативны при филогенетическом анализе. Эти проблемы обычны в новых последовательностях, которые бедно аннотированы и могут содержать сдвиги рамки считывания, неправильные домены или негомологичные сплайсированные экзоны.
Первый метод, основанный на анализе филогении, был разработан Лойтиноджом и Голдманом в 2005 году. В 2008 году те же авторы выпустили соответствующее программное обеспечение — PRANK. PRANK совершенствует выравнивания, когда есть вставки. Тем не менее, он работает медленнее, чем прогрессивные и/или итеративные методы, которые были разработаны за несколько лет до того.
В 2012 году появились два новых метода, основанных филогенетическом анализе. Первый, названный PAGAN, был разработан командой PRANK, а второй, названный ProGraphMSA, был разработан Жалковским. Их программных обеспечения были разработаны независимо, но имеют общие черты: оба используют алгоритмы на графах для улучшения распознавания негомологичных регионов, а усовершенствования в коде делают их быстрее PRANK.
Поиск мотивов
Поиск мотивов или, иначе, анализ профилей — это метод поиска локализации мотива в глобальном множественном выравнивании как средство получения лучшего MSA и средней величины веса получаемой матрицы с целью использования её для поиска других последовательностей со сходными мотивами. Было разработано множество методов для определения мотивов, но все они основываются на обнаружении коротких высококонсервативных паттернов в большем по длине выравнивания паттерне и конструировании матрицы, подобной матрице замен. Эта матрица отражает нуклеотидный или аминокислотный состав для каждой позиции в предполагаемом мотиве. Затем выравнивание может быть уточнено с помощью этих матриц. В стандартном анализе профилей эта матрица включает в себя вхождения как для каждого возможного символа, так и для гэпа. В противоположность этому, статистический алгоритм поиска паттернов сначала ищет мотивы, а затем использует найденные мотивы для построения множественного выравнивая. Во многих случаях, когда исходное множество последовательностей содержит небольшое количество последовательностей или только высоко родственные последовательности, добавляются псевдокаунты для нормализации распределения, отражённого в весовой матрице. В частности, это помогает избегать нулей в матрице вероятностей, чтобы не получить значение бесконечности в позиционной весовой матрице.
Анализ блоков — это метод поиска мотивов, осуществляемый в регионах выравнивания без гэпов. Блоки могут быть сгенерированы из множественного выравнивания или получены из невыровненных последовательностей путём предварительного расчёта множества общих мотивов из известных семейств генов. Оценка блоков обычно основывается на пространстве символов с высокой частотой встречаемости, а не на вычислении в явном виде матриц замен. Сервер BLOCKS предоставляет альтернативный метод для локализации таких мотивов в невыровненных последовательностях.
Статистическое сопоставление паттернов осуществляется с помощью алгоритма максимизации ожидания и семплирования по Гиббсу. Для поиска мотивов наиболее часто используется сервер MEME, использующий алгоритм максимизации ожидания и метод скрытых марковских моделей, а также MEME/MAST, использующий дополнительно алгоритм MAST.
Множественное выравнивание некодирующих последовательностей
Некоторые участки ДНК, не кодирующие белок, особенно сайты связывания транскрипционных факторов (TFBS), являются более консервативными и не обязательно эволюционно связанными, так как эти сайты могут встречаться в негомологичных последовательностях. Таким образом, допущения, используемые для выравнивания белковых последовательностей и кодирующих регионов ДНК, не подходят для последовательностей сайтов связывания транскрипционных факторов. Несмотря на то что выравнивание кодирующих белок участков ДНК для гомологичных последовательностей с помощью операторов мутации осмысленно, выравнивание последовательностей сайтов связывания для одного и того же транскрипционного фактора не может основываться на эволюционно связанных мутационных операциях. Аналогичным образом эволюционный оператор точечных мутаций может быть использован для определения редакционного расстояния для кодирующих последовательностей, но малопригоден для последовательностей сайтов связывания транскрипционных факторов из-за того, что любое изменение последовательности должно сохранять определённый уровень специфичности для выполнения функции связывания. Это становится особенно значимо, когда выравнивание последовательностей сайтов связывания транскрипционных факторов нужно с целью построения наблюдаемых моделей для предсказания неизвестных локусов таких же TFBS. Следовательно, методы множественного выравнивания необходимо корректировать, учитывая основные эволюционные гипотезы, и использовать определённые операторы, как в методе EDNA, учитывающем термодинамику для выравнивания сайтов связывания.
Визуализация выравнивания и контроль качества
Необходимость использования эвристических подходов для множественного выравнивания приводит к тому, что произвольно выбранное множество белков может с большой вероятностью быть выровнено неверно. Например, оценка некоторых ведущих программ выравнивания при помощи BAliBase benchmark показала, что по меньшей мере 24 % всех выровненных пар аминокислот выровнены неверно. Эти ошибки могут возникать из-за уникальных вставок в один и более участок последовательностей. Они также могут быть обусловлены более сложным эволюционным процессом, приводящим к возникновению белков, которые сложно выровнять только по последовательности, и для качественного выравнивания необходимо знать что-то ещё, например, структуру. По мере увеличения количества выравниваемых последовательностей и их расхождения возрастает ошибка из-за эвристического характера алгоритмов множественного выравнивания. Визуализаторы множественного выравнивания позволяют наглядно оценивать выравнивание часто с помощью проверки качества выравнивания для аннотированных функциональных участков у двух и более последовательностей. Многие визуализаторы также позволяют редактировать выравнивание, корректируя ошибки (обычно минорного характера), для получения оптимального курируемого выравнивания подходящего для использования в филогенетическом анализе или сравнительного моделирования.
Как бы то ни было, по мере увеличения числа последовательностей, в особенности в полногеномных исследованиях, которые включают много множественных выравниваний, становится невозможным вручную курировать все выравнивания. Кроме того, ручное курирование субъективно. И, наконец, даже самый лучший специалист не может с уверенностью выровнять многие неоднозначные случаи у сильно разошедшихся последовательностей. В таких случаях обычно практикуется использование автоматических процедур для исключения ненадёжно выровненных регионов множественного выравнивания. С целью получения филогенетических реконструкций широко используется программа Gblocks для удаления блоков выравнивания с предположительно низким качеством, в соответствии с всевозможными границами (катоффами) по количеству последовательностей с гэпами в колонках выравнивания. В то же время эти критерии могут чрезмерно отфильтровывать регионы с вставками/делециями, которые могли бы быть надёжно выровнены, а эти регионы могли бы быть полезны для выявления положительного отбора. Немногие алгоритмы выравнивания выдают сайт-специфичный вес выравнивания, который мог был позволить отбирать высоко консервативные регионы. Такую возможность впервые дала программа SOAP, которая тестирует устойчивость каждой колонки к колебанию параметров в популярной программе выравнивания ClustalW. Программа T-Coffee использует библиотеку выравниваний для создания конечного множественного выравнивания и выдаёт множественное выравнивание, окрашенное в соответствии с оценкой доверия, которая отражает соответствие между различными выравниваниями в библиотеке по каждому из выровненных остатков. TCS (англ. Transitive Consistency Score) является её расширением, которое использует библиотеку попарных выравниваний T-Coffee для оценки каждого третьего множественного выравнивания. Попарные проекции могут быть созданы использованием быстрых или медленных методов, таким образом, можно найти компромисс между скоростью и точностью вычислений. Другая программа выравнивания, FSA (англ. Fast statistical alignment), использует статистические модели, позволяющие вычислить погрешность выравнивания, и может выдавать множественное выравнивание с оценкой уровня его достоверности. Оценка HoT (англ. Heads-Or-Tails) может быть использована для измерения погрешностей сайт-специфических выравниваний, в которых погрешности могут возникать из-за существования множества ко-оптимальных решений. Программа GUIDANCE вычисляет аналогичную сайт-специфичную меру доверия, базирующуюся на устойчивости выравнивания к неопределённости в направляющем дереве, которое используется, как было сказано выше, в программах прогрессивного выравнивания. В то же время статистически более обоснованным подходом к оценке неопределённостей выравнивания является использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. Байесовский подход позволяет рассчитать постериорные вероятности оценок филогении и выравнивания, которые измеряют уровень уверенности в этих оценках. В этом случае постерионная вероятность может быть вычислена для каждого сайта в выравнивании. Такой подход реализован в программе Bali-Phy.
Использование в филогенетике
Множественное выравнивание последовательностей может быть использовано для построения филогенетического дерева. Это возможно по двум причинам. Во-первых, функциональные домены, известные для аннотированных последовательностей, могут быть использованы для выравнивания неаннотированных последовательностей. Во-вторых, консервативные регионы могут иметь функциональную значимость. Из-за этого возможно использование множественных выравниваний для анализа и нахождения эволюционных связей через гомологию последовательностей. Точечные мутации и вставки/деления могут быть также обнаружены.
Определение местоположения консервативных доменов с помощью множественного выравнивания может быть также использовано для идентифицированная функционально важных сайтов, таких как сайты связывания, регуляторные сайты или сайты ответственные за другие ключевые функции. При анализе множественного выравнивания полезно рассматривать различные характеристики. К таким полезным характеристикам выравнивания относятся идентичность, схожесть и гомология последовательностей. Идентичность определяет, что последовательности имеют одинаковые остатки в соответствующих положениях. Схожесть определяется сходными остатками в количественном соотношении. Например, с точки зрения нуклеотидных последовательностей пиримидины считаются похожими между собой, как и пурины. Сходство в конечном счёте приводит к гомологии, так, чем более сходны последовательности, тем более близкими гомологами они являются. Также сходство последовательностей может помочь в нахождении общего происхождения.