Выравнивание множественных последовательностей

Множественное выравнивание последовательностей: сравнение ДНК, РНК и белков для поиска эволюционных связей и мутаций. Методы, сложность и применение в биоинформатике.

16 мин чтения

100%

Источник: Multiple sequence alignment — Wikipedia

Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.

Содержание

Введение

Выравнивание более двух молекулярных последовательностей

Множественное выравнивание последовательностей (MSA) — это процесс или результат выравнивания трех и более биологических последовательностей, как правило, белков, ДНК или РНК. Эти выравнивания используются для установления эволюционных взаимосвязей посредством филогенетического анализа и позволяют выявить гомологичные признаки в последовательностях. Выравнивания показывают события мутаций, такие как точечные мутации (изменения отдельных аминокислот или нуклеотидов), вставки и делеции, а также используются для оценки консервации последовательностей и определения наличия и активности белковых доменов, третичных и вторичных структур, а также отдельных аминокислот или нуклеотидов. Множественное выравнивание последовательностей требует более сложных методологий, чем попарное выравнивание, поскольку оно более вычислительно сложно. Большинство программ для множественного выравнивания последовательностей используют эвристические методы вместо глобальной оптимизации, так как поиск оптимального выравнивания для более чем нескольких последовательностей умеренной длины требует неприемлемо больших вычислительных ресурсов. Однако эвристические методы обычно не гарантируют получение высококачественных решений и, как показано, могут не давать почти оптимальных результатов на эталонных тестовых примерах.

Графический подход

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

Выровняемость трассировки

При определении наиболее подходящих выравниваний для каждой MSA обычно генерируется траектория. Траектория – это набор реализованных, или соответствующих и выровненных, вершин, имеющий определенный вес, основанный на ребрах, выбранных между соответствующими вершинами. При выборе траекторий для набора последовательностей необходимо выбирать траекторию с максимальным весом, чтобы получить наилучшее выравнивание последовательностей.

Методы выравнивания

Существуют различные методы выравнивания, используемые при анализе множественных последовательностей для достижения максимальных оценок и точности выравнивания. Каждый из них обычно основан на определенной эвристике, учитывающей особенности эволюционного процесса. Большинство из них стремятся смоделировать эволюцию, чтобы получить наиболее реалистичное выравнивание и наилучшим образом предсказать родственные связи между последовательностями.

Динамическое программирование

Прямой метод получения MSA использует технику динамического программирования для идентификации глобально оптимального решения выравнивания. Для белков этот метод обычно включает два набора параметров: штраф за гэп и матрицу подстановок, присваивающую оценки или вероятности выравниванию каждой возможной пары аминокислот на основе сходства химических свойств аминокислот и эволюционной вероятности мутации. Для нуклеотидных последовательностей используется аналогичный штраф за гэп, но типична гораздо более простая матрица подстановок, в которой учитываются только идентичные совпадения и несовпадения. Оценки в матрице подстановок могут быть либо все положительными, либо смесью положительных и отрицательных в случае глобального выравнивания, но должны быть как положительными, так и отрицательными в случае локального выравнивания. Для n отдельных последовательностей наивный метод требует построения n-мерного эквивалента матрицы, формируемой при стандартном попарном выравнивании последовательностей. Таким образом, пространство поиска увеличивается экспоненциально с ростом n и также сильно зависит от длины последовательности. В обозначениях «большого O», обычно используемых для измерения вычислительной сложности, наивный MSA требует O(ДлинаNпоследовательностей) времени для выполнения. Поиск глобального оптимума для n последовательностей таким образом был показан как NP-полная задача. В 1989 году, основываясь на алгоритме Каррильо-Липмана, Алтшуль представил практический метод, использующий попарные выравнивания для ограничения n-мерного пространства поиска. В этом подходе выполняются попарные выравнивания динамическим программированием для каждой пары последовательностей в запрошенном наборе, и поиск n-кратного выравнивания осуществляется только в пространстве вблизи n-мерного пересечения этих выравниваний. Программа MSA оптимизирует сумму всех пар символов в каждой позиции выравнивания (так называемая сумма баллов пар) и была реализована в программном обеспечении для построения множественных выравниваний последовательностей. В 2019 году Хоссейнинасаб и ван Хове показали, что с использованием диаграмм принятия решений MSA может быть смоделирована со сложностью по пространству, выраженной полиномом. Прогрессивное выравнивание строит окончательный MSA, объединяя попарные выравнивания, начиная с самой похожей пары и переходя к наиболее отдаленно связанным. Все методы прогрессивного выравнивания требуют двух этапов: первого, на котором взаимосвязи между последовательностями представлены в виде дерева, называемого направляющим деревом, и второго, на котором MSA строится путем последовательного добавления последовательностей к растущему MSA в соответствии с направляющим деревом. Начальное направляющее дерево определяется эффективным методом кластеризации, таким как метод ближайших соседей или UPGMA, и может использовать расстояния, основанные на количестве идентичных двухбуквенных подпоследовательностей (как в FASTA, а не в выравнивании динамическим программированием). ClustalW широко используется для построения филогенетических деревьев, несмотря на явные предупреждения автора о том, что необработанные выравнивания не следует использовать в таких исследованиях и в качестве входных данных для прогнозирования структуры белка с помощью гомологического моделирования. EMBL EBI объявила, что срок действия ClustalW2 истечет в августе 2015 года. Они рекомендуют Clustal Omega, который работает на основе посевных направляющих деревьев и методов профиль-профиль на основе скрытых марковских моделей для выравнивания белков. MAFFT (Multiple Alignment using Fast Fourier Transform) является альтернативным инструментом для прогрессивного выравнивания ДНК. Другой распространенный метод прогрессивного выравнивания, называемый T-Coffee, медленнее, чем Clustal и его производные, но обычно обеспечивает более точные выравнивания для отдаленно связанных наборов последовательностей. T-Coffee вычисляет попарные выравнивания, объединяя прямое выравнивание пары с косвенными выравниваниями, которые выравнивают каждую последовательность пары с третьей последовательностью. Он использует выходные данные Clustal, а также другую программу локального выравнивания LALIGN, которая находит несколько областей локального выравнивания между двумя последовательностями. Полученное выравнивание и филогенетическое дерево используются в качестве руководства для получения новых и более точных весовых коэффициентов. Поскольку прогрессивные методы являются эвристиками, которые не гарантируют сходимость к глобальному оптимуму, оценка качества выравнивания может быть затруднена, а их истинное биологическое значение может быть неясным. Полупрогрессивный метод, улучшающий качество выравнивания и не использующий эвристику с потерями при работе за полиномиальное время, был реализован в программе PSAlign.

A direct method for producing an MSA uses the dynamic programming technique to identify the globally optimal alignment solution. For proteins, this method usually involves two sets of parameters: a gap penalty and a substitution matrix assigning scores or probabilities to the alignment of each possible pair of amino acids based on the similarity of the amino acids' chemical properties and the evolutionary probability of the mutation. For nucleotide sequences, a similar gap penalty is used, but a much simpler substitution matrix, wherein only identical matches and mismatches are considered, is typical. The scores in the substitution matrix may be either all positive or a mix of positive and negative in the case of a global alignment, but must be both positive and negative, in the case of a local alignment. For n individual sequences, the naive method requires constructing the n dimensional equivalent of the matrix formed in standard pairwise sequence alignment. The search space thus increases exponentially with increasing n and is also strongly dependent on sequence length. Expressed with the big O notation commonly used to measure computational complexity, a naïve MSA takes O(LengthNseqs) time to produce. To find the global optimum for n sequences this way has been shown to be an NP complete problem. In 1989, based on Carrillo Lipman Algorithm, Altschul introduced a practical method that uses pairwise alignments to constrain the n dimensional search space. In this approach pairwise dynamic programming alignments are performed on each pair of sequences in the query set, and only the space near the n dimensional intersection of these alignments is searched for the n way alignment. The MSA program optimizes the sum of all of the pairs of characters at each position in the alignment (the so called sum of pair score) and has been implemented in a software program for constructing multiple sequence alignments. In 2019, Hosseininasab and van Hoeve showed that by using decision diagrams, MSA may be modeled in polynomial space complexity. Progressive alignment builds up a final MSA by combining pairwise alignments beginning with the most similar pair and progressing to the most distantly related. All progressive alignment methods require two stages: a first stage in which the relationships between the sequences are represented as a tree, called a guide tree, and a second step in which the MSA is built by adding the sequences sequentially to the growing MSA according to the guide tree. The initial guide tree is determined by an efficient clustering method such as neighbor joining or UPGMA, and may use distances based on the number of identical two letter sub sequences (as in FASTA rather than a dynamic programming alignment). ClustalW is used extensively for phylogenetic tree construction, in spite of the author's explicit warnings that unedited alignments should not be used in such studies and as input for protein structure prediction by homology modeling. EMBL EBI announced that CLustalW2 will be expired in August 2015. They recommend Clustal Omega which performs based on seeded guide trees and HMM profile profile techniques for protein alignments. An alternative tool for progressive DNA alignments is MAFFT (Multiple Alignment using Fast Fourier Transform). Another common progressive alignment method called T Coffee is slower than Clustal and its derivatives but generally produces more accurate alignments for distantly related sequence sets. T Coffee calculates pairwise alignments by combining the direct alignment of the pair with indirect alignments that aligns each sequence of the pair to a third sequence. It uses the output from Clustal as well as another local alignment program LALIGN, which finds multiple regions of local alignment between two sequences. The resulting alignment and phylogenetic tree are used as a guide to produce new and more accurate weighting factors. Because progressive methods are heuristics that are not guaranteed to converge to a global optimum, alignment quality can be difficult to evaluate and their true biological significance can be obscure. A semi progressive method that improves alignment quality and does not use a lossy heuristic while running in polynomial time has been implemented in the program PSAlign.

Итеративные методы

Набор методов для построения MSA с одновременным снижением ошибок, свойственных прогрессивным методам, классифицируется как "итеративный", поскольку они работают аналогично прогрессивным методам, но многократно перевыстраивают исходные последовательности, а также добавляют новые последовательности в формирующуюся MSA. Одна из причин сильной зависимости прогрессивных методов от высококачественного начального выравнивания заключается в том, что эти выравнивания всегда включаются в конечный результат – то есть, после включения последовательности в MSA её выравнивание больше не пересматривается. Это приближение повышает эффективность, но снижает точность. В отличие от этого, итеративные методы могут возвращаться к ранее вычисленным попарным выравниваниям или под-MSA, включающим подмножества запрошенной последовательности, для оптимизации общей целевой функции, такой как получение высокого балла выравнивания. Программный пакет PRRN/PRRP использует алгоритм поиска с подъемом по склону для оптимизации оценки выравнивания MSA и итеративно корректирует как веса выравнивания, так и локально расходящиеся или "пробельные" области формирующейся MSA. PRRP наиболее эффективно работает при уточнении выравнивания, предварительно построенного более быстрым методом. Выравнивание отдельных мотивов затем достигается с помощью матричного представления, аналогичного точечной матрице в попарном выравнивании. Альтернативный метод, использующий быстрые локальные выравнивания в качестве опорных точек или "зародышей" для более медленной процедуры глобального выравнивания, реализован в пакете CHAOS/DIALIGN. Метрика расстояния обновляется между итерациями (хотя в исходной версии MUSCLE содержалось всего 2–3 итерации в зависимости от того, была ли включена доработка).

Методы консенсуса

Методы консенсуса стремятся найти оптимальное множественное выравнивание последовательностей, основываясь на нескольких различных выравниваниях одного и того же набора последовательностей. Существует два широко используемых метода консенсуса: M COFFEE и MergeAlign. M COFFEE использует множественные выравнивания последовательностей, сгенерированные семью различными методами, для создания консенсусных выравниваний. MergeAlign способен генерировать консенсусные выравнивания из любого количества входных выравниваний, полученных с использованием различных моделей эволюции последовательностей или различных методов множественного выравнивания последовательностей. По умолчанию MergeAlign выводит консенсусное выравнивание, используя выравнивания, сгенерированные 91 различной моделью эволюции белковых последовательностей.

Скрытые модели Маркова

Скрытые марковские модели — это вероятностные модели, способные присваивать вероятности всем возможным комбинациям пропусков, соответствий и несовпадений для определения наиболее вероятной МСА или набора возможных МСА. HMM могут выдавать один результат с наивысшим баллом, но также могут генерировать семейство возможных выравниваний, которые затем можно оценить на предмет биологической значимости. HMM могут создавать как глобальные, так и локальные выравнивания. Хотя методы, основанные на HMM, были разработаны относительно недавно, они обеспечивают значительное повышение вычислительной скорости, особенно для последовательностей, содержащих перекрывающиеся области. Это отличается от методов прогрессивного выравнивания тем, что выравнивание предыдущих последовательностей обновляется при каждом добавлении новой последовательности. Однако, как и в случае прогрессивных методов, на этот метод может влиять порядок, в котором последовательности из набора запросов включаются в выравнивание, особенно если последовательности слабо связаны между собой. Аналогичный, более общий метод реализован в программном пакете Sequence Alignment and Modeling System (SAM) и HMMER. SAM использовался в качестве источника выравниваний для прогнозирования структуры белка с целью участия в эксперименте по прогнозированию структуры CASP и разработки базы данных прогнозируемых белков для дрожжевого вида S. cerevisiae. HHsearch — это программный пакет для обнаружения удалённо родственных последовательностей белков на основе попарного сравнения HMM. Сервер, работающий на HHsearch (HHpred), был самым быстрым из 10 автоматических серверов прогнозирования структуры в конкурсах по прогнозированию структуры CASP7 и CASP8.

Методы, учитывающие филогенезию

Большинство методов множественного выравнивания последовательностей стремятся минимизировать количество вставок/удалений (пробелов) и, как следствие, создают компактные выравнивания. Это вызывает ряд проблем, если выравниваемые последовательности содержат негомологичные области, или если пробелы несут информативную нагрузку при филогенетическом анализе. Такие проблемы часто встречаются в недавно полученных последовательностях, которые плохо аннотированы и могут содержать сдвиги рамки считывания, неверные домены или негомологичные сплайсированные экзоны. Первый подобный метод был разработан в 2005 году Лёйтёной и Голдманом. Те же авторы выпустили программный пакет PRANK в 2008 году. PRANK улучшает выравнивания при наличии вставок. Однако, он работает медленнее, чем прогрессивные и/или итеративные методы, которые разрабатывались на протяжении многих лет. В 2012 году появилось два новых инструмента, учитывающих филогенетические связи. Один из них – PAGAN, разработанный той же командой, что и PRANK. Другой – ProGraphMSA, разработанный Szalkowski. Оба программных пакета были разработаны независимо, но имеют общие черты, в частности, использование графовых алгоритмов для улучшения распознавания негомологичных областей и оптимизацию кода, что делает их быстрее, чем PRANK.

Определение мотивов

Поиск мотивов, также известный как профильный анализ, — это метод локализации мотивов последовательности в глобальных МСА, который служит как для получения более качественной МСА, так и для создания матрицы оценок, используемой при поиске других последовательностей на предмет схожих мотивов. Разработано множество методов выделения мотивов, но все они основаны на идентификации коротких, высококонсервативных паттернов внутри большего выравнивания и построении матрицы, аналогичной матрице подстановок, отражающей аминокислотный или нуклеотидный состав каждой позиции в предполагаемом мотиве. Затем выравнивание можно уточнить, используя эти матрицы. В стандартном профильном анализе матрица включает записи для каждого возможного символа, а также для гэпов. Оценка блоков обычно опирается на интервалы между высокочастотными символами, а не на вычисление явной матрицы подстановок. Статистическое сопоставление с образцами было реализовано с использованием как алгоритма максимизации ожиданий, так и сэмплирования Гиббса. Один из наиболее распространенных инструментов поиска мотивов, известный как MEME, использует максимизацию ожиданий и скрытые марковские модели для генерации мотивов, которые затем используются в качестве инструментов поиска его сопутствующей программой MAST в объединенном пакете MEME/MAST.

Некодирующая многократная последовательность выравнивания

Некодирующие области ДНК, особенно сайты связывания факторов транскрипции (TFBS), консервативны, но не обязательно имеют общее эволюционное происхождение и могут возникать независимо у разных предков. Таким образом, принципы, используемые для выравнивания последовательностей белков и кодирующих областей ДНК, принципиально отличаются от тех, что применимы к последовательностям TFBS. В то время как выравнивание кодирующих областей ДНК гомологичных последовательностей с использованием операторов мутаций является осмысленным, выравнивание последовательностей сайтов связывания для одного и того же фактора транскрипции не может основываться на эволюционно связанных мутациях. Аналогично, эволюционный оператор точечных мутаций может быть использован для определения расстояния редактирования для кодирующих последовательностей, но это имеет ограниченное значение для последовательностей TFBS, поскольку любое изменение последовательности должно сохранять определенный уровень специфичности для обеспечения функционирования сайта связывания. Это особенно важно при попытке выровнять известные последовательности TFBS для построения моделей с учителем, предназначенных для предсказания неизвестных местоположений того же TFBS. Следовательно, методы множественного выравнивания последовательностей должны учитывать лежащую в основе эволюционную гипотезу и используемые операторы, как, например, в работах, использующих термодинамическую информацию соседних оснований для выравнивания сайтов связывания с целью поиска термодинамически оптимального выравнивания, сохраняющего специфичность сайта связывания.

Генетические алгоритмы и имитационное отжигание

Стандартные методы оптимизации в информатике, оба из которых вдохновлены, но не напрямую воспроизводят физические процессы, также использовались в попытке более эффективно получать качественные МСА. Один из таких методов, генетические алгоритмы, применялся для создания МСА, стремясь смоделировать гипотетический эволюционный процесс, приведший к расхождению в наборе запросов. Метод заключается в разделении серии возможных МСА на фрагменты и их многократном переупорядочивании с введением пробелов в различных позициях. В ходе моделирования оптимизируется целевая функция, как правило, функция максимизации "суммы пар", впервые представленная в методах МСА, основанных на динамическом программировании. Реализация этой техники для белковых последовательностей доступна в программном обеспечении SAGA (Sequence Alignment by Genetic Algorithm), а её аналог для РНК называется RAGA. Метод имитированного отжига позволяет уточнить существующую МСА, полученную другим методом, посредством серии переупорядочиваний, направленных на поиск областей пространства выравнивания, превосходящих исходное выравнивание. Подобно методу генетических алгоритмов, имитированный отжиг максимизирует целевую функцию, такую как функция суммы пар. Имитированный отжиг использует метафорический "температурный коэффициент", определяющий скорость переупорядочиваний и вероятность каждой перестановки; типичный подход предполагает чередование периодов высокой скорости переупорядочивания с относительно низкой вероятностью (для исследования более отдалённых областей пространства выравнивания) и периодов низкой скорости и высокой вероятности для более детального изучения локальных минимумов вблизи недавно "заселённых" областей. Этот подход реализован в программе MSASA (Multiple Sequence Alignment by Simulated Annealing).

Математическое программирование и точные алгоритмы решения

Математическое программирование и, в частности, модели смешанного целочисленного программирования, представляют собой еще один подход к решению задач MSA. Преимущество таких моделей оптимизации заключается в том, что они позволяют находить оптимальное решение MSA более эффективно, чем традиционный метод динамического программирования. Это отчасти обусловлено возможностью применения методов декомпозиции к задачам математического программирования, когда модель MSA разбивается на более мелкие части и итеративно решается до достижения оптимального решения. Примеры алгоритмов, используемых для решения моделей смешанного целочисленного программирования для задач MSA, включают метод ветвей и цен и декомпозицию Бендерса.

Визуализация выравнивания и контроль качества

Необходимость использования эвристик для множественного выравнивания означает, что для любого набора белков всегда существует значительная вероятность ошибок в выравнивании. Например, оценка нескольких ведущих программ выравнивания с использованием эталонного набора данных BAliBase показала, что как минимум 24% всех пар выровненных аминокислот были выровнены некорректно. Эти ошибки могут возникать из-за уникальных вставок в один или несколько участков последовательностей, или в результате более сложного эволюционного процесса, приводящего к белкам, которые трудно выровнять только по последовательности. С увеличением числа последовательностей и степени их расхождения количество ошибок будет возрастать просто из-за эвристической природы алгоритмов множественного выравнивания (MSA). Программы просмотра множественного выравнивания последовательностей позволяют визуально оценивать выравнивания, часто путем проверки качества выравнивания аннотированных функциональных участков на двух или более последовательностях. Многие из них также позволяют редактировать выравнивание для исправления этих (обычно незначительных) ошибок, чтобы получить оптимальное, “отредактированное” выравнивание, пригодное для использования в филогенетическом анализе или сравнительном моделировании. Однако, с увеличением числа последовательностей, особенно в полногеномных исследованиях, включающих множество MSA, ручная проверка всех выравниваний становится невозможной. Более того, ручная проверка субъективна. И, наконец, даже лучший эксперт не может уверенно выровнять наиболее неоднозначные случаи сильно расходящихся последовательностей. В таких случаях обычной практикой является использование автоматических процедур для исключения из MSA регионов, выровненных с низкой достоверностью. Для реконструкции филогенетических деревьев (см. ниже) широко используется программа Gblocks для удаления блоков выравнивания, подозреваемых в низком качестве, на основе различных пороговых значений для числа участков с пробелами в столбцах выравнивания. Однако, эти критерии могут чрезмерно отфильтровывать регионы с событиями вставки/удаления, которые все еще могут быть выровнены надежно, и которые могут быть полезны для других целей, таких как обнаружение положительного отбора. Некоторые алгоритмы выравнивания выдают оценки для каждого сайта, позволяющие выбирать регионы с высокой степенью достоверности. Первой такой возможностью предоставила программа SOAP, которая проверяет устойчивость каждого столбца к изменениям параметров популярной программы выравнивания CLUSTALW. Программа T-Coffee использует библиотеку выравниваний при построении окончательного MSA, и выходной MSA окрашивается в соответствии со степенями достоверности, отражающими согласованность между различными выравниваниями в библиотеке для каждого выровненного остатка. Ее расширение, TCS (Transitive Consistency Score), использует библиотеки парных выравниваний T-Coffee для оценки MSA, полученных из других источников. Попарные проекции могут быть построены с использованием быстрых или медленных методов, обеспечивая компромисс между скоростью и точностью. Другая программа выравнивания, способная выдавать MSA с оценками достоверности, – FSA, которая использует статистическую модель, позволяющую оценить неопределенность выравнивания. Оценка HoT (Heads Or Tails) может использоваться для измерения неопределенности выравнивания для конкретного сайта из-за существования нескольких равноценных решений. Программа GUIDANCE рассчитывает аналогичную меру достоверности для конкретного сайта на основе устойчивости выравнивания к неопределенности в направляющем дереве, используемом в программах прогрессивного выравнивания. Альтернативный, более статистически обоснованный подход к оценке неопределенности выравнивания – использование вероятностных эволюционных моделей для совместной оценки филогенетических деревьев и выравнивания. Байесовский подход позволяет рассчитать апостериорные вероятности оцененных филогенетических деревьев и выравнивания, что является мерой уверенности в этих оценках. В этом случае апостериорная вероятность может быть рассчитана для каждого сайта в выравнивании. Такой подход был реализован в программе BAli-Phy. Существуют бесплатные программы для визуализации множественных выравниваний последовательностей, например Jalview и UGENE.

The necessary use of heuristics for multiple alignment means that for an arbitrary set of proteins, there is always a good chance that an alignment will contain errors. For example, an evaluation of several leading alignment programs using the BAliBase benchmark found that at least 24% of all pairs of aligned amino acids were incorrectly aligned. These errors can arise because of unique insertions into one or more regions of sequences, or through some more complex evolutionary process leading to proteins that do not align easily by sequence alone. As the number of sequence and their divergence increases many more errors will be made simply because of the heuristic nature of MSA algorithms. Multiple sequence alignment viewers enable alignments to be visually reviewed, often by inspecting the quality of alignment for annotated functional sites on two or more sequences. Many also enable the alignment to be edited to correct these (usually minor) errors, in order to obtain an optimal 'curated' alignment suitable for use in phylogenetic analysis or comparative modeling. However, as the number of sequences increases and especially in genome wide studies that involve many MSAs it is impossible to manually curate all alignments. Furthermore, manual curation is subjective. And finally, even the best expert cannot confidently align the more ambiguous cases of highly diverged sequences. In such cases it is common practice to use automatic procedures to exclude unreliably aligned regions from the MSA. For the purpose of phylogeny reconstruction (see below) the Gblocks program is widely used to remove alignment blocks suspect of low quality, according to various cutoffs on the number of gapped sequences in alignment columns. However, these criteria may excessively filter out regions with insertion/deletion events that may still be aligned reliably, and these regions might be desirable for other purposes such as detection of positive selection. A few alignment algorithms output site specific scores that allow the selection of high confidence regions. Such a service was first offered by the SOAP program, which tests the robustness of each column to perturbation in the parameters of the popular alignment program CLUSTALW. The T Coffee program uses a library of alignments in the construction of the final MSA, and its output MSA is colored according to confidence scores that reflect the agreement between different alignments in the library regarding each aligned residue. Its extension, TCS (Transitive Consistency Score), uses T Coffee libraries of pairwise alignments to evaluate any third party MSA. Pairwise projections can be produced using fast or slow methods, thus allowing a trade off between speed and accuracy. Another alignment program that can output an MSA with confidence scores is FSA, which uses a statistical model that allows calculation of the uncertainty in the alignment. The HoT (Heads Or Tails) score can be used as a measure of site specific alignment uncertainty due to the existence of multiple co optimal solutions. The GUIDANCE program calculates a similar site specific confidence measure based on the robustness of the alignment to uncertainty in the guide tree that is used in progressive alignment programs. An alternative, more statistically justified approach to assess alignment uncertainty is the use of probabilistic evolutionary models for joint estimation of phylogeny and alignment. A Bayesian approach allows calculation of posterior probabilities of estimated phylogeny and alignment, which is a measure of the confidence in these estimates. In this case, a posterior probability can be calculated for each site in the alignment. Such an approach was implemented in the program BAli Phy. There are free programs available for visualization of multiple sequence alignments, for example Jalview and UGENE.

Филогенетическое применение

Для создания филогенетического дерева можно использовать множественные выравнивания последовательностей. Это становится возможным по двум причинам. Во-первых, функциональные домены, известные по аннотированным последовательностям, могут быть использованы для выравнивания неаннотированных последовательностей. Во-вторых, можно выявить консервативные регионы, известные своей функциональной значимостью. Это позволяет использовать множественные выравнивания последовательностей для анализа и определения эволюционных взаимосвязей на основе гомологии между последовательностями. Можно обнаружить точечные мутации, а также вставки или делеции (называемые инделами). Множественные выравнивания последовательностей также могут быть использованы для идентификации функционально важных участков, таких как сайты связывания, активные центры или участки, соответствующие другим ключевым функциям, путем локализации консервативных доменов. При анализе множественных выравниваний последовательностей полезно учитывать различные аспекты последовательностей при их сравнении. К этим аспектам относятся идентичность, сходство и гомология. Идентичность означает, что последовательности имеют одинаковые остатки в соответствующих позициях. С другой стороны, сходство подразумевает количественную похожесть остатков в сравниваемых последовательностях. Например, в случае нуклеотидных последовательностей пиримидины считаются сходными друг с другом, как и пурины. Сходство в конечном итоге ведет к гомологии: чем более похожи последовательности, тем выше вероятность их гомологичности. Это сходство в последовательностях, в свою очередь, может помочь в определении общего происхождения.