Множественное выравнивание последовательностей: различия между версиями

Интерактивная навигация по истории

[непроверенная версия]

← Предыдущая правка Следующая правка →

Содержимое удалено Содержимое добавлено

ВизуальныйВики-текст

Линейный

Версия от 00:04, 24 апреля 2016

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

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

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

Динамическое программирование и вычислительная сложность

Для построения глобального оптимального выравнивания напрямую используется динамическое программирование. Для белковых последовательностей существует два набора параметров: штраф за гэп и матрица замен, содержащая в себе вероятности сопоставления пары аминокислотных остатков, основанных на схожести их химических свойств и эволюционной вероятности мутации. Для нуклеотидных последовательностей также используется штраф за гэп, но матрица замен гораздо проще, там учитываются только идентичные совпадения и мисматчи (несовпадения) ^[1].

Для n отдельных последовательностей, наивный метод требует построения n-мерного эквивалента матрицы, которую используют для парного выравнивания. С ростом n пространство поиска возрастает экспоненциально. Таким образом, наивный алгоритм имеет вычислительную сложность O(Длина последовательностей^{Nпоследовательностей}). Поиск глобального оптимума для n последовательностей относится к NP-полным задачам ^[2]^[3]^[4].

В 1989 году на основе алгоритма Карилло-Липмана ^[5], Альтшуль представил практический подход, который использовал парные выравнивания для ограничения n-мерного пространства поиска ^[6]. При таком подходе динамическое программирование выполняется на каждой паре последовательностей из входного набора и ищется только область, расположенная вблизи n-мерного пересечения этих путей. Программа оптимизирует сумму всех пар символов в каждой позиции в выравнивании (сумма парных скоров) ^[7]

Прогрессивное выравнивание

Широко используемый подход - прогрессивное выравнивание, применяющий эвристический алгоритм, разработан Paulien Hogeweg and Ben Hesper в 1984 ^[8]. Все методы прогрессивного выравнивания имеют две важные стадии: построение бинарного дерева (путеводное дерево), где листья являются последовательностями, и построение множественного выравнивания путем добавления последовательностей к растущему выравниванию согласно путеводному дереву. Само путеводное дерево может быть построено кластеризующими методами такими как UPGMA и метод ближайшего соседа. ^[9].

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

Методы прогрессивного выравнивания достаточно эффективны, чтобы применять их для большого (100-1000) числа последовательностей. Самый популярный метод прогрессивного выравнивания принадлежит к семейству Clustal ^[10], в частности взвешенный вариант ClustalW ^[11], доступ к которому можно получить через такие порталы как GenomeNet, EBI, EMBNet. ClustalW активно используется для построения филогенетических деревьев, несмотря на предупреждения автора, что неопубликованные выравнивания не должны использоваться ни при построении деревьев, ни в качестве входных данных для предсказания структуры белков. Текущая версия Clustal - ClastalW2, однако EMBL-EBI объявил, что срок работы ClustalW2 истечет к августу 2015. Они рекомендуют Clustal Omega, которая работает на основе путеводных деревьев и HMM профиль-профильных методов для белковых выравниваний. Также они предлагают различные инструменты для построения прогрессивного выравнивания последовательностей ДНК. Один из них – MAFFT (Multiple Alignment using Fast Fourier Transform) ^[12].

Другой распространенный метод прогрессивного выравнивания, T-Coffee ^[13], медленнее чем Clustal и его производные, но в основном дает более точные выравнивания для отдаленно связанных последовательностей. T-Coffee строит библиотеку парных выравниваний, которую затем использует для построения множественного выравнивания.

Поскольку прогрессивные методы являются эвристическими, они не гарантируют схождения к глобальному оптимуму; качество выравнивания и его биологическое значение может быть трудно оценить. Полупрогрессивный метод, который улучшает качество выравнивания и не использует эвристику, приводящую к потере данных, справляется за полиномиальное время (PSAlign) ^[14].

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

Набор методов для построения множественных выравниваний, в которых происходит снижение ошибок, наследуемых в прогрессивных методах, классифицируют как «итеративные». Они работают аналогично прогрессивным методам, но при этом неоднократно перестраивают исходные выравнивания при добавлении новых последовательностей. Прогрессивные методы сильно зависят от качества начальных выравниваний, поскольку они в неизменном виде, а стало быть и с ошибками, попадут в конечный результат. Т.е., если последовательность уже попала в выравнивание, ее дальнейшее положение не изменится. Такое приближение улучшает эффективность, но негативно сказывается на точности результата. В отличие от прогрессивных методов, итеративные методы могу возвращаться к первоначально посчитанным парным выравниваниям и подвыравниваниям, содержащим подмножества последовательностей из запроса, и таким образом, оптимизировать общую целевую функцию и повышать качество^[9].

Существует большое число разнообразных итеративных методов. Например, PRRN/PRRP использует алгоритм восхождения к вершине для оптимизации скора множественного выравнивания ^[15] и итеративно корректирует веса выравнивания и области со множеством гэпов ^[9]. PRRP работает эффективнее, когда улучшает выравнивание, предварительно построенное быстрым методом ^[9].

Еще одна итеративная программа, DIALIGN, использует необычный подход, сосредотачивая внимание на локальных выравниваниях подсегментов или мотивов последовательностей без введения штрафа за гэп ^[16].Выравнивание отдельных мотивов представляется в матричной виде, сходном с диаграммой с точками (dot-plot) в парном выравнивании. Альтернативный метод, который использует быстрые локальные выравнивания как точки заякоривания для более медленной процедуры построения глобального выравнивания представлен в софте CHAOS/DIALIGN^[16].

Третий популярный итерационный метод называется MUSCLE. Он улучшен по сравнению с прогрессивными методами, поскольку использует более точные расстояния для оценки связи двух последовательностей ^[17] . Расстояния обновляются между итерациями (хотя, в первоначальном виде MUSCLE содержал только 2-3 итерации).

Консенсусные методы

Консенсусные методы пытаются найти оптимальное множественное выравнивание из различных множественных выравниваний одного и того же набора входных данных. Существуют два наиболее распространенных консенсусных метода, M-COFFEE и MergeAlign ^[18]. M-COFFEE использует множественные выравнивания, генерируемые 7 различными методами для получения консенсусных выравниваний. MergeAlign способен генерировать консенсусные выравнивания из любого числа входных выравниваний, полученных из различных моделей эволюции последовательности и методов построения. Опция по умолчанию для MergeAlign – выведение консенсусного выравнивания, используя выравнивания, полученные из 91 различных моделей эволюции белковой последовательности.

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

Скрытые Марковские модели (HMMs) – вероятностные модели, которые могу оценить вероятности для всех возможных комбинаций гэпов, совпадений или несовпадений, для того, чтобы определить наиболее вероятное множественное выравнивание или их набор. HMMs могут давать одно выравнивание с высоким скором, но также могут генерировать семейство возможных выравниваний, которые затем могут быть оценены по их биологической значимости. HMMs могут быть использованы для получения как глобальных, так и локальных выравниваний. Несмотря на то, что методы, основанные на HMM, появились сравнительно недавно, они зарекомендовали себя как методы со значительными улучшениями вычислительной сложности, особенно для последовательностей, содержащих перекрывающиеся области ^[9].

Стандартные методы, основанные на HMM, представляют множественное выравнивание в виде направленного ациклического графа, известного как граф частичного порядка, который состоит из серий узлов, представляющих собой возможные состояния в колонках выравнивания. В этом представлении абсолютно консервативная колонка (т.е. последовательности во множественном выравнивании имеют в этой позиции определенный символ) кодируется как один узел со множеством исходящих соединений с символами, возможными в следующей позиции выравнивания. В терминах стандартной скрытой Марковской модели, наблюдаемые состояния – отдельные колонки выравнивания, а «скрытые» состояния представляют собой предполагаемую предковую последовательность из которой последовательности из входного набора могли произойти. Эффективный метод динамического программирования, алгоритм Витерби, широко используется для получения хорошего выравнивания^[19] . Он отличается от прогрессивных методов тем, что выравнивание первых последовательностей перестраивается при добавлении каждой новой последовательности. Тем не менее, как и прогрессивные методы, на этот алгоритм может повлиять порядок, в котором последовательности из входного набора поступают в выравнивание, особенно в случае эволюционно слабо связанных последовательностей ^[9].

Несмотря на то, что HMM-методы более сложные, чем часто используемые прогрессивные методы, существует несколько программ для получения выравниваний. Например, POA ^[20], похожий, но более обобщенный метод в пакетах SAM ^[21] и HMMER () ^[22]с. SAM используется для получения выравниваний для предсказания структуры белков в эксперименте CASP для дрожжевых белков. HHsearch, основанный на парном сравнении HMMs, ^[23] используется для поиска отдаленно связанных последовательностей. Сервер, запускающий HHsearch (HHpred ()) был самым быстрым из 10 лучших автоматических серверов по предсказанию структур белков в CASP7 и CASP8.

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

Стандартные оптимизационные методы в компьютерной науке, которые симулируют, но не прямо воспроизводят физический процесс, также используются для более эффективного воспроизведения качества множественных выравниваний. Один такой метод, генетический алгоритм, был использован для воспроизведения MSA в попытке симулировать гипотетический эволюционный процесс, который обеспечил расхождение последовательностей. Этот метод работает с помощью разделения серий возможных MSA на фрагменты и повторно переорганизовывая эти фрагменты с вводом гэпов в различные позиции. Основная объектная функция оптимизируется в ходе этой симуляции, обычно с помощью максимизации "сумм пар" у MSA методов основанных на динамическом программировании. Это методреализован для белковых последовательностей в программном обеспечении SAGA (Sequence Alignment by Genetic Algorithm)^[24], а последовательностей РНК - в RAGA^[25].

С помощью метода симуляции отжига существующее множественное выравнивание, построенное другим методом, уточняется в сериях перестроек для нахождения более хороших регионов участков выравнивания, чем было до этого. Как и генетический алгоритм, симуляция отжига максимизирует объектную функцию как функцию сумм пар. Симуляция отжига использует метафорический "температурный фактор", который определяет уровень протекающих перестроек и уровень правдоподобности каждой перестройки. Типично использование чередующихся периодов с высоким уровнем перестроек и малым уровнем правдоподобия (для обнаружения наиболее удаленных регионов в выравнивании) с периодами с более низким уровнем перестроек и более высоким уровнем правдоподобия для более тщательного изучения локальных минимумов вблизи новых колонок выравнивания. Этот подход был осуществлен в программе MSASA (Multiple Sequence Alignment by Simulated Annealing)^[26].

Методы, основанные на анализе филогении

Большинство методов множественного выравнивая стараются минимизировать количество вставок/делеций (гэпов), из-за чего продуцируют компактные выравнивания. Такой подход может привести к некоторым проблемам, если выровненные последовательности содержали негомологичные регионы и если гэпы информативны при филогенетическом анализе. Эти проблемы обычны в новых последовательностях, которые бедно аннотированы и могут содержать сдвиги рамки считывания, неправильные домены или негомологичные сплайсированные экзоны.

Первый метод, основанный на анализе филогении, был разработан Löytynoja и Голдманом в 2005 году^[27]. В 2008 году эти авторы выпустили соответствующее программное обеспечение - PRANK^[28]. PRANK совершенствует выравнивания, когда есть вставки. Тем не менее, он работает медленнее, чем прогрессивные и/или итеративные методы, которые были разработаны за несколько лет до.

В 2012 году появились два новых метода, основанных на анализе филогении. Первый, названный PAGAN, был разработан командой PRANK. А другой, названный ProGraphMSA, был разработан Szalkowski^[29]. Оба программных обеспечения были разработаны независимо, но имеют общие черты. Оба используют графические алгоритмы для улучшения распознавания негомологичных регионов, а усовершенствования в коде делают их быстрее PRANK.

Поиск мотивов

Поиск мотивов или иначе анализ профилей - это метод поиска локализации мотива в глобальном множественном выравнивании, как средство получения лучшего MSA и средней величины оценки (скора) получаемой матрицы с целью использования ее для поиска других последовательностей со сходными мотивами. Было разработано множество методов для определения мотивов, но все они основываются на обнаружении коротких высоко консервативных паттернов среди большего выравнивания и построении матрицы схожести к матрице замен, что отражает нуклеотидный или аминокислотный состав для каждой позиции в предполагаемом мотиве. Затем выравнивание может быть уточнено с помощью этих матриц. В стандартном анализе профилей, эта матрица включает в себя вхождения как для каждого возможного символа, так и для гэпа^[9]. В противоположность этому, статистический алгоритм поиска паттернов может обнаружить мотивы скорее как предшественник для множественного выравнивания, чем как источник. Во многих случаях, когда множество запросов содержит небольшое количество последовательностей или только высоко родственные последовательности, добавляются псевдокаунты для нормализации распределения, отраженного в матрице скора. В частности, это помогает корректировать нулевую вероятность вхождения в матрицу малых значений, но отличных от нуля.

Анализ блоков - это метод нахождения мотивов, который ограничивает мотивы регионами без гэпов в выравнивании. Блоки могут быть сгенерированы из множественного выравнивания или получены из невыровненных последовательностей путем предварительного расчета множества общих мотивов из известных семейств генов^[30]. Оценка блоков обычно основывается на пространстве символов с высокой частотой встречаемости, а не на вычислении в явном виде матриц замен. BLOCKS сервер предоставляет альтернативный метод для локализации таких мотивов в невыровненных последовательностях.

Статистическое сопоставление паттернов осуществляется с помощью алгоритма максимизации ожидания и Гиббс семплер алгоритма (семплирования по Гиббсу). Для поиска мотивов наиболее часто используется сервер MEME, использующий алгоритм максимизации ожидания и метод скрытых марковских моделей, а также MEME/MAST^[31]^[32], использующий дополнительно алгоритм MAST.

Множественное выравнивание некодирующих последовательностей

Декодирующие ДНК регионы, особенно TFBS, являются более консервативными и не обязательно эволюционно связанными, а так же могут встречаться у неродственных предков. Таким образом, допущения, используемые для выравнивания белковых последовательностей и кодирующих регионов ДНК, по природе не подходят для TFBS последовательностей. Не смотря на то, что выравнивание кодирующих ДНК регионов для гомологичных последовательностей с помощью операторов мутации значимо, выравнивание последовательностей сайтов связывания для одного и того же транскрипционного фактора не может основываться на эволюционно связанных мутационных операциях. Аналогичным образом эволюционный оператор точечных мутаций может быть использован для определения редукционного расстояния для кодирующих последовательностей, но имеет малую значимость для TFBS последовательностей из-за того, что любое изменение последовательности должно сохранять определенный уровень специфичности для выполнения функции связывания. Это становится особенно значимо когда выравнивание TFBS последовательностей нужно с целью построения наблюдаемых моделей для предсказания неизвестных локусов таких же TFBS. Поэтому методы множественного выравнивания нуждаются в корректировке, учитывающей основные эволюционные гипотезы и использующей определенные операторы, как в опубликованной работе, содержащей встроенные термодинамические базы данных^[33] для выравнивания сайтов связывания поиском по наиболее низким термодинамическим выравниваниям, которые сохраняют специфичность сайтов связывания, EDNA.

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

Необходимость использования эвристики для множественного выравнивания приводит к тому, что произвольно выбранное множество белков имеет хороший шанс иметь выравнивание содержащее ошибки. Например, оценка некоторых ведущих программ выравнивания при помощи BAliBase benchmark показало, что по меньшей мере 24% всех выровненных пар аминокислот выровнены неверно^[34]. Эти ошибки могут возникать из-за уникальных вставок в один и более регион последовательностей или из-за более сложного эволюционного процесса, приводящего к возникновению белков, которые в одиночку легко не выравниваются. По мере увеличения количества выравниваемых последовательностей и их расхождения возрастает ошибка из-за эвристического характера алгоритмов множественного выравнивания. Визуализаторы множественного выравнивания позволяют наглядно оценивать выравнивание часто с помощью проверки качества выравнивания для аннотированных функциональных участков у двух и более последовательностей. Многие также позволяют редактировать выравнивание, корректируя ошибки (обычно минорного характера), для получения оптимального "курируемого" выравнивания подходящего для использования в филогенетическом анализе или сравнительного моделирования^[35].

Как бы то ни было, по мере увеличения числа последовательностей, в особенности в полногеномных исследованиях, которые включают много множественных выравниваний, становится невозможным вручную курировать все выравнивания. Кроме того, ручное курирование - субъективно. И, наконец, даже самый лучший специалист не может с уверенностью выровнять многие неоднозначные случаи у сильно разошедшихся последовательностей. В таких случаях обычно практикуется использование автоматических процедур для исключения ненадежно выровненных регионов MSA. С целью получения филогенетических реконструкций (смотри ниже) широко используется программа Gblocks для удаления блоков выравнивания с предположительно низким качеством, в соответствии с всевозможными границами (катоффами) по количеству последовательностей с нэпами в колонках выравнивания^[36]. Как бы то ни было, эти критерии могут чрезмерно отфильтровывать регионы с вставками/делециями, которые могли бы быть надежно выровнены, а эти регионы могли бы быть полезны для детекции положительного отбора. Немногие алгоритмы выравнивания выдают сайт-специфичные оценки (скоры), которые позволяют отбирать высоко консервативные регионы. Такую возможность впервые дала программа SOAP^[37], которая тестирует устойчивость каждой колонки к колебанию параметров в популярной программе выравнивания CLUSTALW. Программа T-Coffee^[38] использует библиотеку выравниваний для создания конечного множественного выравнивания, и выдает MSA окрашенное в соответствии с оценкой доверия, которая отражает соответствие между различными выравниваниями в библиотеке по каждому из выровненных остатков. TCS (Transitive Consistency Score) является ее расширением, которое использует библиотеку попарных выравниваний T-Coffee для оценки каждого третьего множественного выравнивания. Попарные проекции могут быть созданы использованием быстрых или медленных методов, таким образом можно найти компромисс между скоростью и аккуратностью вычислений^[39]^[40]. Другая программа выравнивания, FSA, может выдавать множественное выравнивание с оценкой уровня достоверности, которая используется статистической модели, которая позволяет вычислить погрешность выравнивания. Оценка HoT (Heads-Or-Tails) может быть использована для измерения погрешностей сайт-специфических выравниваний, в которых погрешности могут возникать из-за существования множества ко-оптимальных решений. Программа GUIDANCE^[41] вычисляет аналогичную сайт-специфичную меру доверия, базирующуюся на устойчивости выравнивания к неопределенности в направляющем дереве, которое используется в программах прогрессивного выравнивания. В тоже время статистически более обоснованным подходом к оценке неопределенностей выравнивания является использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. Байесовский подход позволяет рассчитать постериорные вероятности оценок филогении и выравнивания, которые измеряют уровень уверенности в этих оценках. В этом случае постерионная вероятность может быть вычислена для каждого сайта в выравнивании. Такой подход реализован в программе Bali-Phy^[42].

JalView и UGENE являются свободно доступными программами для визуализации множественных выравниваний.

Использование в филогенетике

Множественное выравнивание последовательностей может быть использовано для построения филогенетического дерева. Это возможно по двум причинам. Во-первых, функциональные домены, известные для аннотированных последовательностей, могут быть использованы для выравнивая неаннотированных последовательностей. Во-вторых, консервативные регионы могут иметь функциональную значимость. Из-за этого возможно использование MAS для анализа и нахождения эволюционных связей через гомологию последовательностей. Точечные мутации и вставки или делении могут быть также обнаружены.

Определение местоположения консервативных доменов с помощью множественного выравнивания может быть также использовано для идентифицированная функционально важных сайтов, таких как сайты связывания, регуляторные сайты, или сайты ответственные за другие ключевые функции. При анализе множественного выравнивания полезно рассматривать различные характеристики. К таким полезным характеристикам выравнивания относится идентичность, схожесть и гомология последовательностей. Идентичность определяет, что последовательности имеют одинаковые остатки в соответствующих положениях. Схожесть определяется сходными остатками в количественном соотношении. Например, с точки зрения нуклеотидных последовательностей пиримидины считаются похожими между собой, как и пурины. Сходство в конечном счете приводит к гомологии, так, чем более сходны последовательности, тем более они гомологичны. Также сходство последовательностей может помочь в нахождении общего происхождения^[43].

Примечания

↑ Help with matrices used in sequence comparison tools (неопр.). European Bioinformatics Institute. Дата обращения: 3 марта 2010.
↑ Wang L, Jiang T (1994). "On the complexity of multiple sequence alignment". J Comput Biol. 1 (4): 337—348. doi:10.1089/cmb.1994.1.337. PMID 8790475.
↑ Just W (2001). "Computational complexity of multiple sequence alignment with SP-score". J Comput Biol. 8 (6): 615—23. doi:10.1089/106652701753307511. PMID 11747615.
↑ Elias, Isaac (2006). "Settling the intractability of multiple alignment". J Comput Biol. 13 (7): 1323—1339. doi:10.1089/cmb.2006.13.1323. PMID 17037961.
↑ Carrillo H, Lipman DJ (1988). "The Multiple Sequence Alignment Problem in Biology". SIAM Journal of Applied Mathematics. 48 (5): 1073—1082. doi:10.1137/0148063.
↑ Lipman DJ, Altschul SF, Kececioglu JD (1989). "A tool for multiple sequence alignment". Proc Natl Acad Sci U S A. 86 (12): 4412—4415. doi:10.1073/pnas.86.12.4412. PMC 287279. PMID 2734293.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
↑ Genetic analysis software (неопр.). National Center for Biotechnology Information. Дата обращения: 3 марта 2010.
↑ Hogeweg P, Hesper B (1984). "The alignment of sets of sequences and the construction of phyletic trees: an integrated method". J Mol Evol. 20: 1750186. PMID 6433036.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ Mount DM (2004). "Bioinformatics: Sequence and Genome Analysis 2nd ed". Cold Spring Harbor.
↑ Higgins DG, Sharp PM (1988). "CLUSTAL: a package for performing multiple sequence alignment on a microcomputer". Gene. 73 (1): 237—244. doi:10.1016/0378-1119(88)90330-7. PMID 3243435.
↑ Thompson JD, Higgins DG, Gibson TJ (1994). "CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice". Nucleic Acids Res. 22 (22): 4673—4680. doi:10.1093/nar/22.22.4673. PMC 308517. PMID 7984417.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
↑ EMBL-EBI-ClustalW2-Multiple Sequence Alignment (неопр.). CLUSTALW2.
↑ Notredame C, Higgins DG, Heringa J (2000). "T-Coffee: A novel method for fast and accurate multiple sequence alignment". J Mol Biol. 302 (1): 205—217. doi:10.1006/jmbi.2000.4042. PMID 10964570.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
↑ Sze SH, Lu Y, Yang Q (2006). "A polynomial time solvable formulation of multiple sequence alignment". J Comput Biol. 13 (2): 309—319. doi:10.1089/cmb.2006.13.309. PMID 16597242.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
↑ Gotoh O (1996). "Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments". J Mol Biol. 264 (4): 823—38. doi:10.1006/jmbi.1996.0679. PMID 8980688.
↑ ¹ ² Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B (2003). "Fast and sensitive multiple alignment of large genomic sequences". BMC Bioinformatics. 4: 66. doi:10.1186/1471-2105-4-66.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Википедия:Обслуживание CS1 (не помеченный открытым DOI) (ссылка)
↑ Edgar RC (2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research. 32 (5): 1792—97. doi:10.1093/nar/gkh340. PMC 390337. PMID 15034147.
↑ Collingridge PW, Kelly S (2012). "MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments". BMC Bioinformatics. 13 (117). doi:10.1186/1471-2105-13-117. PMID 22646090.{{cite journal}}: Википедия:Обслуживание CS1 (не помеченный открытым DOI) (ссылка)
↑ Hughey R, Krogh A (1996). "Hidden Markov models for sequence analysis: extension and analysis of the basic method". CABIOS. 12 (2): 95—107. doi:10.1093/bioinformatics/12.2.95. PMID 8744772.
↑ Grasso C, Lee C (2004). "Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems". Bioinformatics. 20 (10): 1546—56. doi:10.1093/bioinformatics/bth126. PMID 14962922.
↑ Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.
↑ Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.
↑ Battey JN, Kopp J, Bordoli L, Read RJ, Clarke ND, Schwede T (2007). "Automated server predictions in CASP7". Proteins. 69 (Suppl 8): 68—82. doi:10.1002/prot.21761. PMID 17894354.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
↑ C. Notredame, D. G. Higgins. SAGA: sequence alignment by genetic algorithm // Nucleic Acids Research. — 1996-04-15. — Т. 24, вып. 8. — С. 1515–1524. — ISSN 0305-1048.
↑ C. Notredame, E. A. O'Brien, D. G. Higgins. RAGA: RNA sequence alignment by genetic algorithm // Nucleic Acids Research. — 1997-11-15. — Т. 25, вып. 22. — С. 4570–4580. — ISSN 0305-1048.
↑ Jin Kim, Sakti Pramanik, Moon Jung Chung. Multiple sequence alignment using simulated annealing (англ.) // Computer applications in the biosciences : CABIOS. — 1994-07-01. — Vol. 10, iss. 4. — P. 419–426. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/10.4.419.
↑ Ari Löytynoja, Nick Goldman. An algorithm for progressive multiple alignment of sequences with insertions (англ.) // Proceedings of the National Academy of Sciences of the United States of America. — 2005-07-26. — Vol. 102, iss. 30. — P. 10557–10562. — ISSN 1091-6490 0027-8424, 1091-6490. — doi:10.1073/pnas.0409137102.
↑ Ari Löytynoja, Nick Goldman. Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis (англ.) // Science. — 2008-06-20. — Vol. 320, iss. 5883. — P. 1632–1635. — ISSN 1095-9203 0036-8075, 1095-9203. — doi:10.1126/science.1158395.
↑ Adam M. Szalkowski. Fast and robust multiple sequence alignment with phylogeny-aware gap placement // BMC bioinformatics. — 2012-01-01. — Т. 13. — С. 129. — ISSN 1471-2105. — doi:10.1186/1471-2105-13-129.
↑ S. Henikoff, J. G. Henikoff. Automated assembly of protein blocks for database searching // Nucleic Acids Research. — 1991-12-11. — Т. 19, вып. 23. — С. 6565–6572. — ISSN 0305-1048.
↑ T. L. Bailey, C. Elkan. Fitting a mixture model by expectation maximization to discover motifs in biopolymers // Proceedings / ... International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. — 1994-01-01. — Т. 2. — С. 28–36. — ISSN 1553-0833.
↑ T. L. Bailey, M. Gribskov. Combining evidence using p-values: application to sequence homology searches // Bioinformatics (Oxford, England). — 1998-01-01. — Т. 14, вып. 1. — С. 48–54. — ISSN 1367-4803.
↑ Rafik A. Salama, Dov J. Stekel. A non-independent energy-based multiple sequence alignment improves prediction of transcription factor binding sites (англ.) // Bioinformatics. — 2013-11-01. — Vol. 29, iss. 21. — P. 2699–2704. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/btt463.
↑ Paulo A. S. Nuin, Zhouzhi Wang, Elisabeth R. M. Tillier. The accuracy of several multiple sequence alignment programs for proteins // BMC bioinformatics. — 2006-01-01. — Т. 7. — С. 471. — ISSN 1471-2105. — doi:10.1186/1471-2105-7-471.
↑ Aidan Budd. Manual Editing and Adjustment of MSAs (Multiple Sequence Alignments) (неопр.). www.embl.de. Дата обращения: 23 апреля 2016.
↑ J. Castresana. Selection of Conserved Blocks from Multiple Alignments for Their Use in Phylogenetic Analysis (англ.) // Molecular Biology and Evolution. — 2000-04-01. — Vol. 17, iss. 4. — P. 540–552. — ISSN 1537-1719 0737-4038, 1537-1719.
↑ A. Löytynoja, M. C. Milinkovitch. SOAP, cleaning multiple alignments from unstable blocks (англ.) // Bioinformatics. — 2001-06-01. — Vol. 17, iss. 6. — P. 573–574. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/17.6.573.
↑ A. Löytynoja, M. C. Milinkovitch. SOAP, cleaning multiple alignments from unstable blocks (англ.) // Bioinformatics. — 2001-06-01. — Vol. 17, iss. 6. — P. 573–574. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/17.6.573.
↑ Jia-Ming Chang, Paolo Di Tommaso, Cedric Notredame. TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction (англ.) // Molecular Biology and Evolution. — 2014-06-01. — Vol. 31, iss. 6. — P. 1625–1637. — ISSN 1537-1719 0737-4038, 1537-1719. — doi:10.1093/molbev/msu117.
↑ Jia-Ming Chang, Paolo Di Tommaso, Vincent Lefort, Olivier Gascuel, Cedric Notredame. TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction // Nucleic Acids Research. — 2015-07-01. — Т. 43, вып. W1. — С. W3–6. — ISSN 1362-4962. — doi:10.1093/nar/gkv310.
↑ Osnat Penn, Eyal Privman, Giddy Landan, Dan Graur, Tal Pupko. An Alignment Confidence Score Capturing Robustness to Guide Tree Uncertainty (англ.) // Molecular Biology and Evolution. — 2010-08-01. — Vol. 27, iss. 8. — P. 1759–1767. — ISSN 1537-1719 0737-4038, 1537-1719. — doi:10.1093/molbev/msq066.
↑ Benjamin D. Redelings, Marc A. Suchard. Joint Bayesian Estimation of Alignment and Phylogeny (англ.) // Systematic Biology. — 2005-06-01. — Vol. 54, iss. 3. — P. 401–418. — ISSN 1076-836X 1063-5157, 1076-836X. — doi:10.1080/10635150590947041.
↑ Aidan Budd. Multiple Sequence Alignments: Exercises and Demonstrations (неопр.). www.embl.de. Дата обращения: 23 апреля 2016.

Ссылки

[1] Help with matrices used in sequence comparison tools (неопр.). European Bioinformatics Institute. Дата обращения: 3 марта 2010.

[wang-2] Wang L, Jiang T (1994). "On the complexity of multiple sequence alignment". J Comput Biol. 1 (4): 337—348. doi:10.1089/cmb.1994.1.337. PMID 8790475.

[just-3] Just W (2001). "Computational complexity of multiple sequence alignment with SP-score". J Comput Biol. 8 (6): 615—23. doi:10.1089/106652701753307511. PMID 11747615.

[elias-4] Elias, Isaac (2006). "Settling the intractability of multiple alignment". J Comput Biol. 13 (7): 1323—1339. doi:10.1089/cmb.2006.13.1323. PMID 17037961.

[carrillo-5] Carrillo H, Lipman DJ (1988). "The Multiple Sequence Alignment Problem in Biology". SIAM Journal of Applied Mathematics. 48 (5): 1073—1082. doi:10.1137/0148063.

[altschul-6] Lipman DJ, Altschul SF, Kececioglu JD (1989). "A tool for multiple sequence alignment". Proc Natl Acad Sci U S A. 86 (12): 4412—4415. doi:10.1073/pnas.86.12.4412. PMC 287279. PMID 2734293.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)

[7] Genetic analysis software (неопр.). National Center for Biotechnology Information. Дата обращения: 3 марта 2010.

[hogeweg1984-8] Hogeweg P, Hesper B (1984). "The alignment of sets of sequences and the construction of phyletic trees: an integrated method". J Mol Evol. 20: 1750186. PMID 6433036.

[Mount-9] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ Mount DM (2004). "Bioinformatics: Sequence and Genome Analysis 2nd ed". Cold Spring Harbor.

[higgins1988-10] Higgins DG, Sharp PM (1988). "CLUSTAL: a package for performing multiple sequence alignment on a microcomputer". Gene. 73 (1): 237—244. doi:10.1016/0378-1119(88)90330-7. PMID 3243435.

[thomson1994-11] Thompson JD, Higgins DG, Gibson TJ (1994). "CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice". Nucleic Acids Res. 22 (22): 4673—4680. doi:10.1093/nar/22.22.4673. PMC 308517. PMID 7984417.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)

[EMBL-EBI-12] EMBL-EBI-ClustalW2-Multiple Sequence Alignment (неопр.). CLUSTALW2.

[notredame2000-13] Notredame C, Higgins DG, Heringa J (2000). "T-Coffee: A novel method for fast and accurate multiple sequence alignment". J Mol Biol. 302 (1): 205—217. doi:10.1006/jmbi.2000.4042. PMID 10964570.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)

[sze2006-14] Sze SH, Lu Y, Yang Q (2006). "A polynomial time solvable formulation of multiple sequence alignment". J Comput Biol. 13 (2): 309—319. doi:10.1089/cmb.2006.13.309. PMID 16597242.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)

[gotoh-15] Gotoh O (1996). "Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments". J Mol Biol. 264 (4): 823—38. doi:10.1006/jmbi.1996.0679. PMID 8980688.

[brudno-16] ¹ ² Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B (2003). "Fast and sensitive multiple alignment of large genomic sequences". BMC Bioinformatics. 4: 66. doi:10.1186/1471-2105-4-66.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Википедия:Обслуживание CS1 (не помеченный открытым DOI) (ссылка)

[edgar-17] Edgar RC (2004). "MUSCLE: multiple sequence alignment with high accuracy and high throughput". Nucleic Acids Research. 32 (5): 1792—97. doi:10.1093/nar/gkh340. PMC 390337. PMID 15034147.

[mergealign-18] Collingridge PW, Kelly S (2012). "MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments". BMC Bioinformatics. 13 (117). doi:10.1186/1471-2105-13-117. PMID 22646090.{{cite journal}}: Википедия:Обслуживание CS1 (не помеченный открытым DOI) (ссылка)

[hughey-19] Hughey R, Krogh A (1996). "Hidden Markov models for sequence analysis: extension and analysis of the basic method". CABIOS. 12 (2): 95—107. doi:10.1093/bioinformatics/12.2.95. PMID 8744772.

[grasso-20] Grasso C, Lee C (2004). "Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems". Bioinformatics. 20 (10): 1546—56. doi:10.1093/bioinformatics/bth126. PMID 14962922.

[hugheyT-21] Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.

[durbin-22] Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.

[23] Battey JN, Kopp J, Bordoli L, Read RJ, Clarke ND, Schwede T (2007). "Automated server predictions in CASP7". Proteins. 69 (Suppl 8): 68—82. doi:10.1002/prot.21761. PMID 17894354.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)

[24] C. Notredame, D. G. Higgins. SAGA: sequence alignment by genetic algorithm // Nucleic Acids Research. — 1996-04-15. — Т. 24, вып. 8. — С. 1515–1524. — ISSN 0305-1048.

[25] C. Notredame, E. A. O'Brien, D. G. Higgins. RAGA: RNA sequence alignment by genetic algorithm // Nucleic Acids Research. — 1997-11-15. — Т. 25, вып. 22. — С. 4570–4580. — ISSN 0305-1048.

[26] Jin Kim, Sakti Pramanik, Moon Jung Chung. Multiple sequence alignment using simulated annealing (англ.) // Computer applications in the biosciences : CABIOS. — 1994-07-01. — Vol. 10, iss. 4. — P. 419–426. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/10.4.419.

[27] Ari Löytynoja, Nick Goldman. An algorithm for progressive multiple alignment of sequences with insertions (англ.) // Proceedings of the National Academy of Sciences of the United States of America. — 2005-07-26. — Vol. 102, iss. 30. — P. 10557–10562. — ISSN 1091-6490 0027-8424, 1091-6490. — doi:10.1073/pnas.0409137102.

[28] Ari Löytynoja, Nick Goldman. Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis (англ.) // Science. — 2008-06-20. — Vol. 320, iss. 5883. — P. 1632–1635. — ISSN 1095-9203 0036-8075, 1095-9203. — doi:10.1126/science.1158395.

[29] Adam M. Szalkowski. Fast and robust multiple sequence alignment with phylogeny-aware gap placement // BMC bioinformatics. — 2012-01-01. — Т. 13. — С. 129. — ISSN 1471-2105. — doi:10.1186/1471-2105-13-129.

[30] S. Henikoff, J. G. Henikoff. Automated assembly of protein blocks for database searching // Nucleic Acids Research. — 1991-12-11. — Т. 19, вып. 23. — С. 6565–6572. — ISSN 0305-1048.

[31] T. L. Bailey, C. Elkan. Fitting a mixture model by expectation maximization to discover motifs in biopolymers // Proceedings / ... International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology. — 1994-01-01. — Т. 2. — С. 28–36. — ISSN 1553-0833.

[32] T. L. Bailey, M. Gribskov. Combining evidence using p-values: application to sequence homology searches // Bioinformatics (Oxford, England). — 1998-01-01. — Т. 14, вып. 1. — С. 48–54. — ISSN 1367-4803.

[33] Rafik A. Salama, Dov J. Stekel. A non-independent energy-based multiple sequence alignment improves prediction of transcription factor binding sites (англ.) // Bioinformatics. — 2013-11-01. — Vol. 29, iss. 21. — P. 2699–2704. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/btt463.

[34] Paulo A. S. Nuin, Zhouzhi Wang, Elisabeth R. M. Tillier. The accuracy of several multiple sequence alignment programs for proteins // BMC bioinformatics. — 2006-01-01. — Т. 7. — С. 471. — ISSN 1471-2105. — doi:10.1186/1471-2105-7-471.

[35] Aidan Budd. Manual Editing and Adjustment of MSAs (Multiple Sequence Alignments) (неопр.). www.embl.de. Дата обращения: 23 апреля 2016.

[36] J. Castresana. Selection of Conserved Blocks from Multiple Alignments for Their Use in Phylogenetic Analysis (англ.) // Molecular Biology and Evolution. — 2000-04-01. — Vol. 17, iss. 4. — P. 540–552. — ISSN 1537-1719 0737-4038, 1537-1719.

[37] A. Löytynoja, M. C. Milinkovitch. SOAP, cleaning multiple alignments from unstable blocks (англ.) // Bioinformatics. — 2001-06-01. — Vol. 17, iss. 6. — P. 573–574. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/17.6.573.

[38] A. Löytynoja, M. C. Milinkovitch. SOAP, cleaning multiple alignments from unstable blocks (англ.) // Bioinformatics. — 2001-06-01. — Vol. 17, iss. 6. — P. 573–574. — ISSN 1460-2059 1367-4803, 1460-2059. — doi:10.1093/bioinformatics/17.6.573.

[39] Jia-Ming Chang, Paolo Di Tommaso, Cedric Notredame. TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction (англ.) // Molecular Biology and Evolution. — 2014-06-01. — Vol. 31, iss. 6. — P. 1625–1637. — ISSN 1537-1719 0737-4038, 1537-1719. — doi:10.1093/molbev/msu117.

[40] Jia-Ming Chang, Paolo Di Tommaso, Vincent Lefort, Olivier Gascuel, Cedric Notredame. TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction // Nucleic Acids Research. — 2015-07-01. — Т. 43, вып. W1. — С. W3–6. — ISSN 1362-4962. — doi:10.1093/nar/gkv310.

[41] Osnat Penn, Eyal Privman, Giddy Landan, Dan Graur, Tal Pupko. An Alignment Confidence Score Capturing Robustness to Guide Tree Uncertainty (англ.) // Molecular Biology and Evolution. — 2010-08-01. — Vol. 27, iss. 8. — P. 1759–1767. — ISSN 1537-1719 0737-4038, 1537-1719. — doi:10.1093/molbev/msq066.

[42] Benjamin D. Redelings, Marc A. Suchard. Joint Bayesian Estimation of Alignment and Phylogeny (англ.) // Systematic Biology. — 2005-06-01. — Vol. 54, iss. 3. — P. 401–418. — ISSN 1076-836X 1063-5157, 1076-836X. — doi:10.1080/10635150590947041.

[43] Aidan Budd. Multiple Sequence Alignments: Exercises and Demonstrations (неопр.). www.embl.de. Дата обращения: 23 апреля 2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

@@ Строка 45: / Строка 45: @@
 == Генетические алгоритмы и симуляция отжига ==
-Стандартные оптимизационные методы в компьютерной науке, которые симулируют, но не прямо воспроизводят физический процесс, также используются для более эффективного воспроизведения качества MSAs. Один такой метод, генетический алгоритм, был использован для воспроизведения MSA в попытке симулировать гипотетический эволюционный процесс, который обеспечил расхождение последовательностей. Этот метод работает с помощью разделения серий возможных MSA на фрагменты и повторно переорганизовывая эти фрагменты с вводом гэпов в различные позиции. Основная объектная функция оптимизируется в ходе этой симуляции, обычно с помощью максимизации "сумм пар" у MSA методов основанных на динамическом программировании. Метод белковых последовательностей реализован в программном обеспечении SAGA (Sequence Alignment by Genetic Algorithm), а последовательностей РНК - в RAGA.
+Стандартные оптимизационные методы в компьютерной науке, которые симулируют, но не прямо воспроизводят физический процесс, также используются для более эффективного воспроизведения качества множественных выравниваний. Один такой метод, [[генетический алгоритм]], был использован для воспроизведения MSA в попытке симулировать гипотетический эволюционный процесс, который обеспечил расхождение последовательностей. Этот метод работает с помощью разделения серий возможных MSA на фрагменты и повторно переорганизовывая эти фрагменты с вводом гэпов в различные позиции. Основная объектная функция оптимизируется в ходе этой симуляции, обычно с помощью максимизации "сумм пар" у MSA методов основанных на [[Динамическое программирование|динамическом программировании]]. Это методреализован для белковых последовательностей в программном обеспечении SAGA (Sequence Alignment by Genetic Algorithm)<ref>{{Статья|автор=C. Notredame, D. G. Higgins|заглавие=SAGA: sequence alignment by genetic algorithm|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/8628686|издание=Nucleic Acids Research|год=1996-04-15|том=24|выпуск=8|страницы=1515–1524|issn=0305-1048}}</ref>, а последовательностей РНК - в RAGA<ref>{{Статья|автор=C. Notredame, E. A. O'Brien, D. G. Higgins|заглавие=RAGA: RNA sequence alignment by genetic algorithm|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/9358168|издание=Nucleic Acids Research|год=1997-11-15|том=25|выпуск=22|страницы=4570–4580|issn=0305-1048}}</ref>.
-С помощью метода отжига существующее множественное выравнивание, построенное другим методом, уточняется в сериях перестроек для нахождения более хороших регионов участков выравнивания, чем было до этого. Как и генетический алгоритм, симуляция отжига максимизирует объектную функцию как функцию сумм пар. Симуляция отжига использует метафорический "температурный фактор", который определяет уровень протекающих перестроек и уровень правдоподобности каждой перестройки. Типично использование чередующихся периодов с высоким уровнем перестроек и малым уровнем правдоподобия (для обнаружения наиболее удаленных регионов в выравнивании) с периодами с более низким уровнем перестроек и более высоким уровнем правдоподобия для более тщательного изучения локальных минимумов вблизи новых колонок выравнивания. Этот подход был осуществлен в программе MSASA (Multiple Sequence Alignment by Simulated Annealing).
+С помощью метода [[:en:Simulated_annealing|симуляции отжига]] существующее множественное выравнивание, построенное другим методом, уточняется в сериях перестроек для нахождения более хороших регионов участков выравнивания, чем было до этого. Как и генетический алгоритм, симуляция отжига максимизирует объектную функцию как функцию сумм пар. Симуляция отжига использует метафорический "температурный фактор", который определяет уровень протекающих перестроек и уровень правдоподобности каждой перестройки. Типично использование чередующихся периодов с высоким уровнем перестроек и малым уровнем правдоподобия (для обнаружения наиболее удаленных регионов в выравнивании) с периодами с более низким уровнем перестроек и более высоким уровнем правдоподобия для более тщательного изучения локальных минимумов вблизи новых колонок выравнивания. Этот подход был осуществлен в программе MSASA (Multiple Sequence Alignment by Simulated Annealing)<ref>{{Статья|автор=Jin Kim, Sakti Pramanik, Moon Jung Chung|заглавие=Multiple sequence alignment using simulated annealing|ссылка=http://bioinformatics.oxfordjournals.org/content/10/4/419|язык=en|издание=Computer applications in the biosciences : CABIOS|год=1994-07-01|том=10|выпуск=4|страницы=419–426|issn=1367-4803, 1460-2059|doi=10.1093/bioinformatics/10.4.419}}</ref>.
 == Методы, основанные на анализе филогении ==
-Большинство методов множественного выравнивая стараются минимизировать количество вставок/делеций (гэпов), из-за чего продуцируют компактные выравнивания. Такой подход может привести к некоторым проблемам, если выровненные последовательности содержали негомологичные регионы и если гэпы информативны при филогенетическом анализе. Эти проблемы обычны в новых последовательностях, которые бедно аннотированы и могут содержать сдвиги рамки считывания, неправильные домены или негомологичные сплайсированные экзоны.
+Большинство методов множественного выравнивая стараются минимизировать количество [[Делеция|вставок/делеций]] (гэпов), из-за чего продуцируют компактные выравнивания. Такой подход может привести к некоторым проблемам, если выровненные последовательности содержали не[[Гомология (биология)|гомологичные]] регионы и если гэпы информативны при [[Филогенетика|филогенетическом анализе]]. Эти проблемы обычны в новых последовательностях, которые бедно аннотированы и могут содержать [[:en:Translational_frameshift|сдвиги рамки считывания]], неправильные домены или негомологичные [[Сплайсинг|сплайсированные экзоны]].
-Первый метод, основанный на анализе филогении, был разработан Löytynoja и Голдманом в 2005 году. В 2008 году эти авторы выпустили соответствующее программное обеспечение - ''PRANK. PRANK'' совершенствует выравнивания, когда есть вставки. Тем не менее, он работает медленнее, чем прогрессивные и/или итеративные методы, которые были разработаны за несколько лет до.
+Первый метод, основанный на анализе филогении, был разработан Löytynoja и Голдманом в 2005 году<ref>{{Статья|автор=Ari Löytynoja, Nick Goldman|заглавие=An algorithm for progressive multiple alignment of sequences with insertions|ссылка=http://www.pnas.org/content/102/30/10557|язык=en|издание=Proceedings of the National Academy of Sciences of the United States of America|год=2005-07-26|том=102|выпуск=30|страницы=10557–10562|issn=0027-8424, 1091-6490|doi=10.1073/pnas.0409137102}}</ref>. В 2008 году эти авторы выпустили соответствующее программное обеспечение - ''PRANK''<ref>{{Статья|автор=Ari Löytynoja, Nick Goldman|заглавие=Phylogeny-Aware Gap Placement Prevents Errors in Sequence Alignment and Evolutionary Analysis|ссылка=http://science.sciencemag.org/content/320/5883/1632|язык=en|издание=Science|год=2008-06-20|том=320|выпуск=5883|страницы=1632–1635|issn=0036-8075, 1095-9203|doi=10.1126/science.1158395}}</ref>''. PRANK'' совершенствует выравнивания, когда есть вставки. Тем не менее, он работает медленнее, чем прогрессивные и/или итеративные методы, которые были разработаны за несколько лет до.
-В 2012 году появились два новых метода, основанных на анализе филогении. Первый, названный ''PAGAN'', был разработан командой ''PRANK''. А другой, названный ''ProGraphMSA,'' был разработан Szalkowski. Оба программных обеспечения были разработаны независимо, но имеют общие черты. Оба используют графические алгоритмы для улучшения распознавания негомологичных регионов, а усовершенствования в коде делают их быстрее ''PRANK''.
+В 2012 году появились два новых метода, основанных на анализе филогении. Первый, названный ''PAGAN'', был разработан командой ''PRANK''. А другой, названный ''ProGraphMSA,'' был разработан Szalkowski<ref>{{Статья|автор=Adam M. Szalkowski|заглавие=Fast and robust multiple sequence alignment with phylogeny-aware gap placement|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/22694311|издание=BMC bioinformatics|год=2012-01-01|том=13|страницы=129|issn=1471-2105|doi=10.1186/1471-2105-13-129}}</ref>. Оба программных обеспечения были разработаны независимо, но имеют общие черты. Оба используют [[Направленный ациклический граф|графические алгоритмы]] для улучшения распознавания негомологичных регионов, а усовершенствования в коде делают их быстрее ''PRANK''.
 == Поиск мотивов ==
-Поиск мотивов или иначе анализ профилей - это метод поиска локализации мотива в глобальном множественном выравнивании, как средство получения лучшего MSA и средней величины оценки (скора) получаемой матрицы с целью использования ее для поиска других последовательностей со сходными мотивами. Было разработано множество методов для определения мотивов, но все они основываются на обнаружении коротких высоко консервативных паттернов среди большего выравнивания и построении матрицы схожести к матрице замен, что отражает нуклеотидный или аминокислотный состав для каждой позиции в предполагаемом мотиве. Затем выравнивание может быть уточнено с помощью этих матриц. В стандартном анализе профилей, эта матрица включает в себя вхождения как для каждого возможного символа, так и для гэпа. В противоположность этому, статистический алгоритм поиска паттернов может обнаружить мотивы скорее как предшественник для множественного выравнивания, чем как источник. Во многих случаях, когда множество запросов содержит небольшое количество последовательностей или только высоко родственные последовательности, добавляются псевдокаунты для нормализации распределения, отраженного в матрице скора. В частности, это помогает корректировать нулевую вероятность вхождения в матрицу малых значений, но отличных от нуля.
+Поиск мотивов или иначе анализ профилей - это метод поиска локализации [[Мотив (молекулярная биология)|мотива]] в глобальном множественном выравнивании, как средство получения лучшего MSA и средней величины оценки (скора) получаемой матрицы с целью использования ее для поиска других последовательностей со сходными мотивами. Было разработано множество методов для определения мотивов, но все они основываются на обнаружении коротких высоко консервативных паттернов среди большего выравнивания и построении матрицы схожести к матрице замен, что отражает нуклеотидный или аминокислотный состав для каждой позиции в предполагаемом мотиве. Затем выравнивание может быть уточнено с помощью этих матриц. В стандартном анализе профилей, эта матрица включает в себя вхождения как для каждого возможного символа, так и для гэпа<ref name="Mount" />. В противоположность этому, статистический алгоритм поиска паттернов может обнаружить мотивы скорее как предшественник для множественного выравнивания, чем как источник. Во многих случаях, когда множество запросов содержит небольшое количество последовательностей или только высоко родственные последовательности, добавляются [[:en:Pseudocount|псевдокаунты]] для нормализации распределения, отраженного в матрице скора. В частности, это помогает корректировать нулевую вероятность вхождения в матрицу малых значений, но отличных от нуля.
-Анализ блоков - это метод нахождения мотивов, который ограничивает мотивы регионами без гэпов в выравнивании. Блоки могут быть сгенерированы из множественного выравнивания или  получены из невыровненных последовательностей путем предварительного расчета множества общих мотивов из известных семейств генов. Оценка блоков обычно основывается на пространстве символов с высокой частотой встречаемости, а не на вычислении в явном виде матриц замен. BLOCKS сервер предоставляет альтернативный метод для локализации таких мотивов в невыровненных последовательностях.
+Анализ блоков - это метод нахождения мотивов, который ограничивает мотивы регионами без гэпов в выравнивании. Блоки могут быть сгенерированы из множественного выравнивания или  получены из невыровненных последовательностей путем предварительного расчета множества общих мотивов из известных семейств генов<ref>{{Статья|автор=S. Henikoff, J. G. Henikoff|заглавие=Automated assembly of protein blocks for database searching|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/1754394|издание=Nucleic Acids Research|год=1991-12-11|том=19|выпуск=23|страницы=6565–6572|issn=0305-1048}}</ref>. Оценка блоков обычно основывается на пространстве символов с высокой частотой встречаемости, а не на вычислении в явном виде матриц замен. [http://blocks.fhcrc.org BLOCKS] сервер предоставляет альтернативный метод для локализации таких мотивов в невыровненных последовательностях.
-Статистическое сопоставление паттернов осуществляется с помощью алгоритма максимизации ожидания и Гиббс семплер алгоритма (семплирования по Гиббсу). Для поиска мотивов наиболее часто используется сервер MEME, использующий алгоритм максимизации ожидания и метод скрытых марковских моделей, а также MEME/MAST, использующий дополнительно алгоритм MAST.
+Статистическое сопоставление паттернов осуществляется с помощью алгоритма [[EM-алгоритм|максимизации ожидания]] и [[Семплирование по Гиббсу|Гиббс семплер]] алгоритма (семплирования по Гиббсу). Для поиска мотивов наиболее часто используется сервер [[MEME]], использующий алгоритм максимизации ожидания и метод скрытых марковских моделей, а также [http://nbcr-222.ucsd.edu/meme.html MEME/MAST]<ref>{{Статья|автор=T. L. Bailey, C. Elkan|заглавие=Fitting a mixture model by expectation maximization to discover motifs in biopolymers|ссылка=http://www.ncbi.nlm.nih.gov/pubmed/7584402|издание=Proceedings / ... International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology|год=1994-01-01|том=2|страницы=28–36|issn=1553-0833}}</ref><ref>{{Статья|автор=T. L. Bailey, M. Gribskov|заглавие=Combining evidence using p-values: application to sequence homology searches|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/9520501|издание=Bioinformatics (Oxford, England)|год=1998-01-01|том=14|выпуск=1|страницы=48–54|issn=1367-4803}}</ref>, использующий дополнительно алгоритм MAST.
 == Множественное выравнивание некодирующих последовательностей ==
-Декодирующие ДНК регионы, особенно TFBS, являются более консервативными и не обязательно эволюционно связанными, а так же могут встречаться у неродственных предков. Таким образом, допущения, используемые для выравнивания белковых последовательностей и кодирующих регионов ДНК, по природе не подходят для TFBS последовательностей. Не смотря на то, что выравнивание кодирующих ДНК регионов для гомологичных последовательностей с помощью операторов мутации значимо, выравнивание последовательностей сайтов связывания для одного и того же транскрипционного фактора не может основываться на эволюционно связанных мутационных операциях. Аналогичным образом эволюционный оператор точечных мутаций может быть использован для определения редукционного расстояния  для кодирующих последовательностей, но имеет малую значимость для TFBS последовательностей из-за того, что любое изменение последовательности должно сохранять определенный уровень специфичности для выполнения функции связывания. Это становится особенно значимо когда выравнивание TFBS последовательностей нужно с целью построения наблюдаемых моделей для предсказания неизвестных локусов таких же TFBS. Поэтому методы множественного выравнивания нуждаются в корректировке, учитывающей основные эволюционные гипотезы и использующей определенные операторы, как в опубликованной работе, содержащей встроенные термодинамические базы данных для выравнивания сайтов связывания поиском по наиболее низким термодинамическим выравниваниям, которые сохраняют специфичность сайтов связывания, EDNA.
+Декодирующие ДНК регионы, особенно TFBS, являются более консервативными и не обязательно эволюционно связанными, а так же могут встречаться у неродственных предков. Таким образом, допущения, используемые для выравнивания белковых последовательностей и кодирующих регионов ДНК, по природе не подходят для TFBS последовательностей. Не смотря на то, что выравнивание кодирующих ДНК регионов для гомологичных последовательностей с помощью операторов мутации значимо, выравнивание последовательностей сайтов связывания для одного и того же транскрипционного фактора не может основываться на эволюционно связанных мутационных операциях. Аналогичным образом эволюционный оператор точечных мутаций может быть использован для определения редукционного расстояния  для кодирующих последовательностей, но имеет малую значимость для TFBS последовательностей из-за того, что любое изменение последовательности должно сохранять определенный уровень специфичности для выполнения функции связывания. Это становится особенно значимо когда выравнивание TFBS последовательностей нужно с целью построения наблюдаемых моделей для предсказания неизвестных локусов таких же TFBS. Поэтому методы множественного выравнивания нуждаются в корректировке, учитывающей основные эволюционные гипотезы и использующей определенные операторы, как в опубликованной работе, содержащей встроенные термодинамические базы данных<ref>{{Статья|автор=Rafik A. Salama, Dov J. Stekel|заглавие=A non-independent energy-based multiple sequence alignment improves prediction of transcription factor binding sites|ссылка=http://bioinformatics.oxfordjournals.org/content/29/21/2699|язык=en|издание=Bioinformatics|год=2013-11-01|том=29|выпуск=21|страницы=2699–2704|issn=1367-4803, 1460-2059|doi=10.1093/bioinformatics/btt463}}</ref> для выравнивания сайтов связывания поиском по наиболее низким термодинамическим выравниваниям, которые сохраняют специфичность сайтов связывания, [https://sourceforge.net/projects/msa-edna/ EDNA].
 == Визуализация выравнивания и контроль качества ==
-Необходимость использования эвристики для множественного выравнивания приводит к тому, что произвольно выбранное множество белков имеет хороший шанс иметь выравнивание содержащее ошибки. Например, оценка некоторых ведущих программ выравнивания при помощи BAliBase benchmark показало, что по меньшей мере 24% всех выровненных пар аминокислот выровнены неверно. Эти ошибки могут возникать из-за уникальных вставок в один и более регион последовательностей или из-за более сложного эволюционного процесса, приводящего к возникновению белков, которые в одиночку легко не выравниваются. По мере увеличения количества выравниваемых последовательностей и их расхождения возрастает ошибка из-за эвристического характера алгоритмов множественного выравнивания. Визуализаторы множественного выравнивания позволяют наглядно оценивать выравнивание часто с помощью проверки качества выравнивания для аннотированных функциональных участков у двух и более последовательностей. Многие также позволяют редактировать выравнивание, корректируя ошибки (обычно минорного характера), для получения оптимального "курируемого" выравнивания подходящего для использования в филогенетическом анализе или сравнительного моделирования.
+Необходимость использования эвристики для множественного выравнивания приводит к тому, что произвольно выбранное множество белков имеет хороший шанс иметь выравнивание содержащее ошибки. Например, оценка некоторых ведущих программ выравнивания при помощи BAliBase benchmark показало, что по меньшей мере 24% всех выровненных пар аминокислот выровнены неверно<ref>{{Статья|автор=Paulo A. S. Nuin, Zhouzhi Wang, Elisabeth R. M. Tillier|заглавие=The accuracy of several multiple sequence alignment programs for proteins|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/17062146|издание=BMC bioinformatics|год=2006-01-01|том=7|страницы=471|issn=1471-2105|doi=10.1186/1471-2105-7-471}}</ref>. Эти ошибки могут возникать из-за уникальных вставок в один и более регион последовательностей или из-за более сложного эволюционного процесса, приводящего к возникновению белков, которые в одиночку легко не выравниваются. По мере увеличения количества выравниваемых последовательностей и их расхождения возрастает ошибка из-за эвристического характера алгоритмов множественного выравнивания. [[:en:List_of_alignment_visualization_software|Визуализаторы множественного выравнивания]] позволяют наглядно оценивать выравнивание часто с помощью проверки качества выравнивания для аннотированных функциональных участков у двух и более последовательностей. Многие также позволяют редактировать выравнивание, корректируя ошибки (обычно минорного характера), для получения оптимального "курируемого" выравнивания подходящего для использования в филогенетическом анализе или сравнительного моделирования<ref>{{Cite web|url=http://www.embl.de/~seqanal/MSAcambridgeGenetics2007/MSAmanualAdjustments/MSAmanualAdjustments.html|title=Manual Editing and Adjustment of MSAs (Multiple Sequence Alignments)|author=Aidan Budd|publisher=www.embl.de|accessdate=2016-04-23}}</ref>.
-Как бы то ни было, по мере увеличения числа последовательностей, в особенности в полногеномных исследованиях, которые включают много множественных выравниваний, становится невозможным вручную курировать все выравнивания. Кроме того, ручное курирование - субъективно. И, наконец, даже самый лучший специалист не может с уверенностью выровнять многие неоднозначные случаи у сильно разошедшихся последовательностей. В таких случаях обычно практикуется использование автоматических процедур для исключения ненадежно выровненных регионов MSA. С целью получения филогенетических реконструкций (смотри ниже) широко используется программа Gblocks для удаления блоков выравнивания с предположительно низким качеством, в соответствии с всевозможными границами (катоффами) по количеству последовательностей с нэпами в колонках выравнивания. Как бы то ни было, эти критерии могут чрезмерно отфильтровывать регионы с вставками/делециями, которые могли бы быть надежно выровнены, а эти регионы могли бы быть  полезны для детекции положительного отбора. Немногие алгоритмы выравнивания выдают сайт-специфичные оценки (скоры), которые позволяют отбирать высоко консервативные регионы. Такую возможность впервые дала программа SOAP, которая тестирует устойчивость каждой колонки к колебанию параметров в популярной программе выравнивания CLUSTALW. Программа T-Coffee использует библиотеку выравниваний для создания конечного множественного выравнивания, и выдает MSA окрашенное в соответствии с оценкой доверия, которая отражает соответствие между различными выравниваниями в библиотеке по каждому из выровненных остатков. TCS ('''T'''ransitive '''C'''onsistency '''S'''core) является ее расширением, которое использует библиотеку попарных выравниваний T-Coffee для оценки каждого третьего множественного выравнивания. Попарные проекции могут быть созданы использованием быстрых или медленных методов, таким образом позволяя вычислить погрешность выравнивания. Оценка HoT (Heads-Or-Tails) может быть использована для измерения погрешностей сайт-специфических выравниваний, в которых погрешности могут возникать из-за существования множества ко-оптимальных решений. Программа GUIDANCE вычисляет аналогичную сайт-специфичную меру доверия, базирующуюся на устойчивости выравнивания к неопределенности в направляющем дереве, которое используется в программах прогрессивного выравнивания. В тоже время статистически более обоснованным подходом к оценке неопределенностей выравнивания является использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. Байесовский подход позволяет рассчитать постериорные вероятности оценок филогении и выравнивания, которые измеряют уровень уверенности в этих оценках. В этом случае постерионная вероятность может быть вычислена для каждого сайта в выравнивании. Такой подход реализован в программе Bali-Phy.
+Как бы то ни было, по мере увеличения числа последовательностей, в особенности в полногеномных исследованиях, которые включают много множественных выравниваний, становится невозможным вручную курировать все выравнивания. Кроме того, ручное курирование - субъективно. И, наконец, даже самый лучший специалист не может с уверенностью выровнять многие неоднозначные случаи у сильно разошедшихся последовательностей. В таких случаях обычно практикуется использование автоматических процедур для исключения ненадежно выровненных регионов MSA. С целью получения филогенетических реконструкций (смотри ниже) широко используется программа Gblocks для удаления блоков выравнивания с предположительно низким качеством, в соответствии с всевозможными границами (катоффами) по количеству последовательностей с нэпами в колонках выравнивания<ref>{{Статья|автор=J. Castresana|заглавие=Selection of Conserved Blocks from Multiple Alignments for Their Use in Phylogenetic Analysis|ссылка=http://mbe.oxfordjournals.org/content/17/4/540|язык=en|издание=Molecular Biology and Evolution|год=2000-04-01|том=17|выпуск=4|страницы=540–552|issn=0737-4038, 1537-1719}}</ref>. Как бы то ни было, эти критерии могут чрезмерно отфильтровывать регионы с вставками/делециями, которые могли бы быть надежно выровнены, а эти регионы могли бы быть  полезны для детекции положительного отбора. Немногие алгоритмы выравнивания выдают сайт-специфичные оценки (скоры), которые позволяют отбирать высоко консервативные регионы. Такую возможность впервые дала программа SOAP<ref>{{Статья|автор=A. Löytynoja, M. C. Milinkovitch|заглавие=SOAP, cleaning multiple alignments from unstable blocks|ссылка=http://bioinformatics.oxfordjournals.org/content/17/6/573|язык=en|издание=Bioinformatics|год=2001-06-01|том=17|выпуск=6|страницы=573–574|issn=1367-4803, 1460-2059|doi=10.1093/bioinformatics/17.6.573}}</ref>, которая тестирует устойчивость каждой колонки к колебанию параметров в популярной программе выравнивания CLUSTALW. Программа T-Coffee<ref>{{Статья|автор=A. Löytynoja, M. C. Milinkovitch|заглавие=SOAP, cleaning multiple alignments from unstable blocks|ссылка=http://bioinformatics.oxfordjournals.org/content/17/6/573|язык=en|издание=Bioinformatics|год=2001-06-01|том=17|выпуск=6|страницы=573–574|issn=1367-4803, 1460-2059|doi=10.1093/bioinformatics/17.6.573}}</ref> использует библиотеку выравниваний для создания конечного множественного выравнивания, и выдает MSA окрашенное в соответствии с оценкой доверия, которая отражает соответствие между различными выравниваниями в библиотеке по каждому из выровненных остатков. [http://tcoffee.crg.cat/apps/tcoffee/do:core TCS] ('''T'''ransitive '''C'''onsistency '''S'''core) является ее расширением, которое использует библиотеку попарных выравниваний T-Coffee для оценки каждого третьего множественного выравнивания. Попарные проекции могут быть созданы использованием быстрых или медленных методов, таким образом можно найти компромисс между скоростью и аккуратностью вычислений<ref>{{Статья|автор=Jia-Ming Chang, Paolo Di Tommaso, Cedric Notredame|заглавие=TCS: A New Multiple Sequence Alignment Reliability Measure to Estimate Alignment Accuracy and Improve Phylogenetic Tree Reconstruction|ссылка=http://mbe.oxfordjournals.org/content/31/6/1625|язык=en|издание=Molecular Biology and Evolution|год=2014-06-01|том=31|выпуск=6|страницы=1625–1637|issn=0737-4038, 1537-1719|doi=10.1093/molbev/msu117}}</ref><ref>{{Статья|автор=Jia-Ming Chang, Paolo Di Tommaso, Vincent Lefort, Olivier Gascuel, Cedric Notredame|заглавие=TCS: a web server for multiple sequence alignment evaluation and phylogenetic reconstruction|ссылка=https://www.ncbi.nlm.nih.gov/pubmed/25855806|издание=Nucleic Acids Research|год=2015-07-01|том=43|выпуск=W1|страницы=W3–6|issn=1362-4962|doi=10.1093/nar/gkv310}}</ref>. Другая программа выравнивания, FSA, может выдавать множественное выравнивание с оценкой уровня достоверности, которая используется статистической модели, которая позволяет  вычислить погрешность выравнивания. Оценка HoT (Heads-Or-Tails) может быть использована для измерения погрешностей сайт-специфических выравниваний, в которых погрешности могут возникать из-за существования множества ко-оптимальных решений. Программа GUIDANCE<ref>{{Статья|автор=Osnat Penn, Eyal Privman, Giddy Landan, Dan Graur, Tal Pupko|заглавие=An Alignment Confidence Score Capturing Robustness to Guide Tree Uncertainty|ссылка=http://mbe.oxfordjournals.org/content/27/8/1759|язык=en|издание=Molecular Biology and Evolution|год=2010-08-01|том=27|выпуск=8|страницы=1759–1767|issn=0737-4038, 1537-1719|doi=10.1093/molbev/msq066}}</ref> вычисляет аналогичную сайт-специфичную меру доверия, базирующуюся на устойчивости выравнивания к неопределенности в направляющем дереве, которое используется в программах прогрессивного выравнивания. В тоже время статистически более обоснованным подходом к оценке неопределенностей выравнивания является использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. [[Байесовская вероятность|Байесовский подход]] позволяет рассчитать постериорные вероятности оценок филогении и выравнивания, которые измеряют уровень уверенности в этих оценках. В этом случае постерионная вероятность может быть вычислена для каждого сайта в выравнивании. Такой подход реализован в программе Bali-Phy<ref>{{Статья|автор=Benjamin D. Redelings, Marc A. Suchard|заглавие=Joint Bayesian Estimation of Alignment and Phylogeny|ссылка=http://sysbio.oxfordjournals.org/content/54/3/401|язык=en|издание=Systematic Biology|год=2005-06-01|том=54|выпуск=3|страницы=401–418|issn=1063-5157, 1076-836X|doi=10.1080/10635150590947041}}</ref>.
 [https://en.wikipedia.org/w/index.php?title=JalView&action=edit&redlink=1 JalView] и [[UGENE]] являются свободно доступными программами для визуализации множественных выравниваний.
 == Использование в филогенетике ==
-Множественное выравнивание последовательностей может быть использовано для построения филогенетического дерева. Это возможно по двум причинам. Во-первых, функциональные домены, известные для аннотированных последовательностей, могут быть использованы для выравнивая неаннотированных последовательностей. Во-вторых, консервативные регионы могут иметь функциональную значимость. Из-за этого возможно использование MAS для анализа и нахождения эволюционных связей через гомологию последовательностей. Точечные мутации и вставки или делении могут быть также обнаружены.
+Множественное выравнивание последовательностей может быть использовано для построения [[Филогенетическое дерево|филогенетического дерева]]. Это возможно по двум причинам. Во-первых, функциональные домены, известные для аннотированных последовательностей, могут быть использованы для выравнивая неаннотированных последовательностей. Во-вторых, консервативные регионы могут иметь функциональную значимость. Из-за этого возможно использование MAS для анализа и нахождения эволюционных связей через гомологию последовательностей. Точечные мутации и вставки или делении могут быть также обнаружены.
-Определение местоположения консервативных доменов с помощью множественного выравнивания может быть также использовано для идентифицированная функционально важных сайтов, таких как сайты связывания, регуляторные сайты, или сайты ответственные за другие ключевые функции. При анализе множественного выравнивания полезно рассматривать различные характеристики. К таким полезным характеристикам выравнивания относится идентичность, схожесть и гомология последовательностей. Идентичность определяет, что последовательности имеют одинаковые остатки в соответствующих положениях. Схожесть определяется сходными остатками в количественном соотношении. Например, с точки зрения нуклеотидных последовательностей пиримидины считаются похожими между собой, как и пурины. Сходство в конечном счете приводит к гомологии, так, чем более сходны последовательности, тем более они гомологичны. Сходство последовательностей может помочь в нахождении общего происхождения.
+Определение местоположения консервативных доменов с помощью множественного выравнивания может быть также использовано для идентифицированная функционально важных сайтов, таких как сайты связывания, регуляторные сайты, или сайты ответственные за другие ключевые функции. При анализе множественного выравнивания полезно рассматривать различные характеристики. К таким полезным характеристикам выравнивания относится [[Выравнивание последовательностей|идентичность, схожесть и гомология последовательностей]]. Идентичность определяет, что последовательности имеют одинаковые остатки в соответствующих положениях. Схожесть определяется сходными остатками в количественном соотношении. Например, с точки зрения нуклеотидных последовательностей [[Пиримидиновые основания|пиримидины]] считаются похожими между собой, как и [[Пурин|пурины]]. Сходство в конечном счете приводит к гомологии, так, чем более сходны последовательности, тем более они гомологичны. Также сходство последовательностей может помочь в нахождении общего происхождения<ref>{{Cite web|url=http://www.embl.de/~seqanal/courses/commonCourseContent/commonMsaExercises.html|title=Multiple Sequence Alignments: Exercises and Demonstrations|author=Aidan Budd|publisher=www.embl.de|accessdate=2016-04-23}}</ref>.
 == Примечания ==