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

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

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

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

Методы, основанные на филогенетическом анализе[править | править вики-текст]

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

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

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

Поиск мотивов[править | править вики-текст]

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

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

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

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

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

Визуализация выравнивания и контроль качества[править | править вики-текст]

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

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

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

Использование в филогенетике[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  1. Help with matrices used in sequence comparison tools. European Bioinformatics Institute. Проверено 3 марта 2010.
  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.
  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.
  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.
  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.
  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. PMID 2734293.
  7. Genetic analysis software. National Center for Biotechnology Information. Проверено 3 марта 2010.
  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.
  9. 1 2 3 4 5 6 7 8 Mount DM (2004). «Bioinformatics: Sequence and Genome Analysis 2nd ed.». Cold Spring Harbor.
  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.
  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. PMID 7984417.
  12. EMBL-EBI-ClustalW2-Multiple Sequence Alignment.
  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.
  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.
  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.
  16. 1 2 Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B (2003). «Fast and sensitive multiple alignment of large genomic sequences». BMC Bioinformatics 4. DOI:10.1186/1471-2105-4-66.
  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. PMID 15034147.
  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.
  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.
  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.
  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.
  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.
  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, fasc. 4. — P. 419–426. — ISSN 1460-2059&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 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, fasc. 30. — P. 10557–10562. — ISSN 1091-6490&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 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, fasc. 5883. — P. 1632–1635. — ISSN 1095-9203&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0036-8075, 1095-9203. — DOI:10.1126/science.1158395.
  29. Dmitry Lupyan, Alejandra Leo-Macias, Angel R. Ortiz A new progressive-iterative algorithm for multiple structure alignment (англ.) // Bioinformatics. — 2005-08-01. — Vol. 21, fasc. 15. — P. 3255–3263. — ISSN 1460-2059&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 1367-4803, 1460-2059. — DOI:10.1093/bioinformatics/bti527.
  30. 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.
  31. 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.
  32. 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.
  33. 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.
  34. 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, fasc. 21. — P. 2699–2704. — ISSN 1460-2059&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 1367-4803, 1460-2059. — DOI:10.1093/bioinformatics/btt463.
  35. 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.
  36. Aidan Budd. Manual Editing and Adjustment of MSAs (Multiple Sequence Alignments). www.embl.de. Проверено 23 апреля 2016.
  37. J. Castresana Selection of Conserved Blocks from Multiple Alignments for Their Use in Phylogenetic Analysis (англ.) // Molecular Biology and Evolution. — 2000-04-01. — Vol. 17, fasc. 4. — P. 540–552. — ISSN 1537-1719&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 0737-4038, 1537-1719.
  38. 1 2 A. Löytynoja, M. C. Milinkovitch SOAP, cleaning multiple alignments from unstable blocks (англ.) // Bioinformatics. — 2001-06-01. — Vol. 17, fasc. 6. — P. 573–574. — ISSN 1460-2059&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 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, fasc. 6. — P. 1625–1637. — ISSN 1537-1719&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 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, fasc. 8. — P. 1759–1767. — ISSN 1537-1719&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 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, fasc. 3. — P. 401–418. — ISSN 1076-836X&f=1003&t=1&v1=&f=4&t=2&v2=&f=21&t=3&v3=&f=1016&t=3&v4=&f=1016&t=3&v5=&bf=4&b=&d=0&ys=&ye=&lng=&ft=&mt=&dt=&vol=&pt=&iss=&ps=&pe=&tr=&tro=&cc=UNION&i=1&v=tagged&s=0&ss=0&st=0&i18n=ru&rlf=&psz=20&bs=20&ce=hJfuypee8JzzufeGmImYYIpZKRJeeOeeWGJIZRrRRrdmtdeee88NJJJJpeeefTJ3peKJJ3UWWPtzzzzzzzzzzzzzzzzzbzzvzzpy5zzjzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzztzzzzzzzbzzzzzzzzzzzzzzzzzzzzzzzzzzzvzzzzzzyeyTjkDnyHzTuueKZePz9decyzzLzzzL*.c8.NzrGJJvufeeeeeJheeyzjeeeeJh*peeeeKJJJJJJJJJJmjHvOJJJJJJJJJfeeeieeeeSJJJJJSJJJ3TeIJJJJ3..E.UEAcyhxD.eeeeeuzzzLJJJJ5.e8JJJheeeeeeeeeeeeyeeK3JJJJJJJJ*s7defeeeeeeeeeeeeeeeeeeeeeeeeeSJJJJJJJJZIJJzzz1..6LJJJJJJtJJZ4....EK*&debug=false 1063-5157, 1076-836X. — DOI:10.1080/10635150590947041.
  43. Aidan Budd. Multiple Sequence Alignments: Exercises and Demonstrations. www.embl.de. Проверено 23 апреля 2016.

Ссылки[править | править вики-текст]