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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Множественное выравнивание последовательностей''' (multiple sequence alignment) это [[Выравнивание_последовательностей|выравнивание]] трех и более биологических последовательностей, обычно [[белков]], [[ДНК]], или [[РНК]]. В большинстве случаев выравнивание производится специальными программами (например [[ClustalW]], [[Muscle]], [[MAFFT]]). На вход эти программам подаются биологические последовательности, которые предполагаются гомологичными, то есть произошедшими из общего предка посредством мутаций. Выравнивание помогает сделать явной гомологию входных последовательностей, выделить их консервативные участки, провести филогенетический анализ. Для проведения полного анализа используются программные платформы, например, [[UGENE]].
'''Множественное выравнивание последовательностей''' (multiple sequence alignment) это [[Выравнивание_последовательностей|выравнивание]] трех и более биологических последовательностей, обычно [[белков]], [[ДНК]], или [[РНК]]. В большинстве случаев предполагается, что входной набор последовательностей имеет эволюционную связь. Используя множественное выравнивание, можно оценить эволюционное происхождение последовательностей, проведя филогенетический анализ.


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

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

==Динамическое программирование и вычислительная сложность==
Для построения глобального оптимального выравнивания напрямую используется динамическое программирование. Для белковых последовательностей существует два набора параметров: штраф за гэп и матрица замен, содержащая в себе вероятности сопоставления пары аминокислотных остатков, основанных на схожести их химических свойств и эволюционной вероятности мутации. Для нуклеотидных последовательностей также используется штраф за гэп, но матрица замен гораздо проще, там учитываются только идентичные совпадения и мисматчи (несовпадения) <ref>{{cite web | title=Help with matrices used in sequence comparison tools | publisher=European Bioinformatics Institute | url=http://www.ebi.ac.uk/help/matrix.html | accessdate=March 3, 2010}}</ref>.

Для n отдельных последовательностей, наивный метод требует построения n-мерного эквивалента матрицы, которую используют для парного выравнивания. С ростом n пространство поиска возрастает экспоненциально. Таким образом, наивный алгоритм имеет вычислительную сложность O(Длина последовательностей<sup>Nпоследовательностей</sup>). Поиск глобального оптимума для n последовательностей относится к NP-полным задачам <ref name="wang">{{cite journal | doi = 10.1089/cmb.1994.1.337 | author = Wang L, Jiang T | year = 1994 | title = On the complexity of multiple sequence alignment | url = | journal = J Comput Biol | volume = 1 | issue = 4| pages = 337–348 | pmid = 8790475 }}</ref><ref name="just">{{cite journal | doi = 10.1089/106652701753307511 | author = Just W | year = 2001 | title = Computational complexity of multiple sequence alignment with SP-score | url = | journal = J Comput Biol | volume = 8 | issue = 6| pages = 615–23 | pmid = 11747615 }}</ref><ref name=elias>{{cite journal | journal=J Comput Biol | volume=13 | pages=1323–1339 | year=2006 | author=Elias, Isaac | title=Settling the intractability of multiple alignment | url=http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.1323 | pmid=17037961 | doi =10.1089/cmb.2006.13.1323 | issue=7 }}</ref>.

В 1989 году на основе алгоритма Карилло-Липмана <ref name="carrillo">{{cite journal | author = Carrillo H, Lipman DJ | year = 1988 | title = The Multiple Sequence Alignment Problem in Biology | url = | journal = SIAM Journal of Applied Mathematics | volume = 48 | issue = 5| pages = 1073–1082 | doi=10.1137/0148063}}</ref>, Альтшуль представил практический подход, который использовал парные выравнивания для ограничения n-мерного пространства поиска <ref name="altschul">{{cite journal | doi = 10.1073/pnas.86.12.4412 | author = Lipman DJ, Altschul SF, Kececioglu JD | year = 1989 | title = A tool for multiple sequence alignment | url = | journal = Proc Natl Acad Sci U S A | volume = 86 | issue = 12| pages = 4412–4415 | pmid = 2734293 | pmc = 287279 }}</ref>. При таком подходе динамическое программирование выполняется на каждой паре последовательностей из входного набора и ищется только область, расположенная вблизи n-мерного пересечения этих путей. Программа оптимизирует сумму всех пар символов в каждой позиции в выравнивании (сумма парных скоров) <ref>{{cite web | title=Genetic analysis software | publisher=National Center for Biotechnology Information | url=http://www.ncbi.nlm.nih.gov/CBBresearch/Schaffer/msa.html | accessdate=March 3, 2010}}</ref>

==Прогрессивное выравнивание ==
Широко используемый подход - прогрессивное выравнивание, применяющий эвристический алгоритм, разработан Paulien Hogeweg and Ben Hesper в 1984 <ref name="hogeweg1984">{{cite journal |author=Hogeweg P, Hesper B |year=1984 |title=The alignment of sets of sequences and the construction of phyletic trees: an integrated method |journal=J Mol Evol |volume=20 |pages=1750186 |pmid=6433036}}</ref>. Все методы прогрессивного выравнивания имеют две важные стадии: построение бинарного дерева (путеводное дерево), где листья являются последовательностями, и построение множественного выравнивания путем добавления последовательностей к растущему выравниванию согласно путеводному дереву. Само путеводное дерево может быть построено кластеризующими методами такими как [[UPGMA]] и метод ближайшего соседа. <ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>.

Прогрессивное выравнивание не гарантирует получение глобального оптимального выравнивания. Проблема состоит в том, что ошибки, полученные на любой стадии растущего множественного выравнивания, доходят до конечного выравнивания. Кроме того, выравнивание может быть особенно плохим в случае набора сильно отдаленных друг от друга последовательностей. Большинство современных прогрессивных методов имеют измененную функцию вычисления скора с вторичной весовой функцией, которая присваивает коэффициенты для отдельных элементов набора данных в виде нелинейной моды основанной на их филогенетическом расстоянии от ближайших соседей<ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>.

Методы прогрессивного выравнивания достаточно эффективны, чтобы применять их для большого (100-1000) числа последовательностей. Самый популярный метод прогрессивного выравнивания принадлежит к семейству Clustal <ref name="higgins1988">{{cite journal |author=[[Desmond G. Higgins|Higgins DG]], Sharp PM |year=1988 |title=CLUSTAL: a package for performing multiple sequence alignment on a microcomputer |journal=Gene |volume=73 |issue=1 |pages=237–244 |doi=10.1016/0378-1119(88)90330-7 |pmid=3243435}}</ref>, в частности взвешенный вариант ClustalW <ref name="thomson1994">{{cite journal |author=Thompson JD, [[Desmond G. Higgins|Higgins DG]], Gibson TJ |year=1994 |title=CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice |journal=Nucleic Acids Res |volume=22 |pages=4673–4680 |doi=10.1093/nar/22.22.4673 |pmid=7984417 |issue=22 |pmc=308517}}</ref>, доступ к которому можно получить через такие порталы как [http://align.genome.jp/ GenomeNet], [http://www.ebi.ac.uk/Tools/clustalw2/index.html EBI], [http://www.ch.embnet.org/software/ClustalW.html EMBNet]. ClustalW активно используется для построения филогенетических деревьев, несмотря на предупреждения автора, что неопубликованные выравнивания не должны использоваться ни при построении деревьев, ни в качестве входных данных для предсказания структуры белков. Текущая версия Clustal - ClastalW2, однако EMBL-EBI объявил, что срок работы ClustalW2 истечет к августу 2015. Они рекомендуют Clustal Omega, которая работает на основе путеводных деревьев и HMM профиль-профильных методов для белковых выравниваний. Также они предлагают различные инструменты для построения прогрессивного выравнивания последовательностей ДНК. Один из них – MAFFT (Multiple Alignment using Fast Fourier Transform) <ref name=EMBL-EBI>{{cite web|title=EMBL-EBI-ClustalW2-Multiple Sequence Alignment|url=http://www.ebi.ac.uk/Tools/msa/clustalw2/|website=CLUSTALW2}}</ref>.

Другой распространенный метод прогрессивного выравнивания, T-Coffee <ref name="notredame2000">{{cite journal |author=Notredame C, [[Desmond G. Higgins|Higgins DG]], Heringa J |year=2000 |title=T-Coffee: A novel method for fast and accurate multiple sequence alignment |journal=J Mol Biol |volume=302 |issue=1 |pages=205–217 |doi=10.1006/jmbi.2000.4042 |pmid=10964570}}</ref>, медленнее чем Clustal и его производные, но в основном дает более точные выравнивания для отдаленно связанных последовательностей. T-Coffee строит библиотеку парных выравниваний, которую затем использует для построения множественного выравнивания.

Поскольку прогрессивные методы являются эвристическими, они не гарантируют схождения к глобальному оптимуму; качество выравнивания и его биологическое значение может быть трудно оценить. Полупрогрессивный метод, который улучшает качество выравнивания и не использует эвристику, приводящую к потере данных, справляется за полиномиальное время ([http://faculty.cs.tamu.edu/shsze/psalign/ PSAlign]) <ref name="sze2006">{{cite journal |author=Sze SH, Lu Y, Yang Q |year=2006 |title=A polynomial time solvable formulation of multiple sequence alignment |journal=J Comput Biol |volume=13 |issue=2 |pages=309–319 |doi=10.1089/cmb.2006.13.309 |pmid=16597242}}</ref>.

==Итеративные методы==
Набор методов для построения множественных выравниваний, в которых происходит снижение ошибок, наследуемых в прогрессивных методах, классифицируют как «итеративные». Они работают аналогично прогрессивным методам, но при этом неоднократно перестраивают исходные выравнивания при добавлении новых последовательностей. Прогрессивные методы сильно зависят от качества начальных выравниваний, поскольку они в неизменном виде, а стало быть и с ошибками, попадут в конечный результат. Т.е., если последовательность уже попала в выравнивание, ее дальнейшее положение не изменится. Такое приближение улучшает эффективность, но негативно сказывается на точности результата. В отличие от прогрессивных методов, итеративные методы могу возвращаться к первоначально посчитанным парным выравниваниям и подвыравниваниям, содержащим подмножества последовательностей из запроса, и таким образом, оптимизировать общую целевую функцию и повышать качество<ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>.

Существует большое число разнообразных итеративных методов [14]. Например, [http://web.archive.org/web/20080703101054/http://prrn.hgc.jp/ PRRN/PRRP] использует алгоритм восхождения к вершине для оптимизации скора множественного выравнивания <ref name="gotoh">{{cite journal | doi = 10.1006/jmbi.1996.0679 | author = Gotoh O | year = 1996 | title = Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments | url = | journal = J Mol Biol | volume = 264 | issue = 4| pages = 823–38 | pmid = 8980688 }}</ref> и итеративно корректирует веса выравнивания и области со множеством гэпов <ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>]. PRRP работает эффективнее, когда улучшает выравнивание, предварительно построенное быстрым методом <ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>.

Еще одна итеративная программа, DIALIGN, использует необычный подход, сосредотачивая внимание на локальных выравниваниях подсегментов или мотивов последовательностей без введения штрафа за гэп <ref name="brudno">{{cite journal | author = Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B | year = 2003 | title = Fast and sensitive multiple alignment of large genomic sequences | url = | journal = BMC Bioinformatics | volume = 4 | issue = | page = 66 | doi=10.1186/1471-2105-4-66}}</ref>.Выравнивание отдельных мотивов представляется в матричной виде, сходном с диаграммой с точками (dot-plot) в парном выравнивании. Альтернативный метод, который использует быстрые локальные выравнивания как точки заякоривания для более медленной процедуры построения глобального выравнивания представлен в софте CHAOS/DIALIGN (http://dialign.gobics.de/chaos-dialign-submission)<ref name="brudno">{{cite journal | author = Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B | year = 2003 | title = Fast and sensitive multiple alignment of large genomic sequences | url = | journal = BMC Bioinformatics | volume = 4 | issue = | page = 66 | doi=10.1186/1471-2105-4-66}}</ref>.

Третий популярный итерационный метод называется MUSCLE. Он улучшен по сравнению с прогрессивными методами, поскольку использует более точные расстояния для оценки связи двух последовательностей <ref name="edgar">{{cite journal | doi = 10.1093/nar/gkh340 | author = Edgar RC | year = 2004 | title = MUSCLE: multiple sequence alignment with high accuracy and high throughput | url = | journal = Nucleic Acids Research | volume = 32 | issue = 5| pages = 1792–97 | pmid=15034147 | pmc=390337}}</ref> . Расстояния обновляются между итерациями (хотя, в первоначальном виде MUSCLE содержал только 2-3 итерации).

==Консенсусные методы==
Консенсусные методы пытаются найти оптимальное множественное выравнивание из различных множественных выравниваний одного и того же набора входных данных. Существуют два наиболее распространенных консенсусных метода, [http://www.tcoffee.org/Projects/mcoffee/ M-COFFEE] и [http://www.stevekellylab.com/software/mergealign MergeAlign] <ref name="mergealign">{{cite journal | doi = 10.1186/1471-2105-13-117 | author = Collingridge PW, Kelly S | year = 2012 | title = MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments | url = http://www.biomedcentral.com/1471-2105/13/117 | journal = BMC Bioinformatics | volume = 13 | issue = 117 | pmid=22646090}}</ref>. M-COFFEE использует множественные выравнивания, генерируемые 7 различными методами для получения консенсусных выравниваний. MergeAlign способен генерировать консенсусные выравнивания из любого числа входных выравниваний, полученных из различных моделей эволюции последовательности и методов построения. Опция по умолчанию для MergeAlign – выведение консенсусного выравнивания, используя выравнивания, полученные из 91 различных моделей эволюции белковой последовательности.

==Скрытые марковские модели==
Скрытые Марковские модели (HMMs) – вероятностные модели, которые могу оценить вероятности для всех возможных комбинаций гэпов, совпадений или несовпадений, для того, чтобы определить наиболее вероятное множественное выравнивание или их набор. HMMs могут давать одно выравнивание с высоким скором, но также могут генерировать семейство возможных выравниваний, которые затем могут быть оценены по их биологической значимости. HMMs могут быть использованы для получения как глобальных, так и локальных выравниваний. Несмотря на то, что методы, основанные на HMM, появились сравнительно недавно, они зарекомендовали себя как методы со значительными улучшениями вычислительной сложности, особенно для последовательностей, содержащих перекрывающиеся области <ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>.

Стандартные методы, основанные на HMM, представляют множественное выравнивание в виде направленного ациклического графа, известного как граф частичного порядка, который состоит из серий узлов, представляющих собой возможные состояния в колонках выравнивания. В этом представлении абсолютно консервативная колонка (т.е. последовательности во множественном выравнивании имеют в этой позиции определенный символ) кодируется как один узел со множеством исходящих соединений с символами, возможными в следующей позиции выравнивания. В терминах стандартной скрытой Марковской модели, наблюдаемые состояния – отдельные колонки выравнивания, а «скрытые» состояния представляют собой предполагаемую предковую последовательность из которой последовательности из входного набора могли произойти. Эффективный метод динамического программирования, алгоритм Витерби, широко используется для получения хорошего выравнивания<ref name="hughey">{{cite journal | author = Hughey R, Krogh A | year = 1996 | title = Hidden Markov models for sequence analysis: extension and analysis of the basic method | url = | journal = CABIOS | volume = 12 | issue = 2| pages = 95–107 | pmid = 8744772 | doi=10.1093/bioinformatics/12.2.95}}</ref> . Он отличается от прогрессивных методов тем, что выравнивание первых последовательностей перестраивается при добавлении каждой новой последовательности. Тем не менее, как и прогрессивные методы, на этот алгоритм может повлиять порядок, в котором последовательности из входного набора поступают в выравнивание, особенно в случае эволюционно слабо связанных последовательностей <ref name="Mount">{{cite journal |author= Mount DM |year=2004 |title= Bioinformatics: Sequence and Genome Analysis 2nd ed. |journal= Cold Spring Harbor |volume= |pages= |pmid=}}</ref>.

Несмотря на то, что HMM-методы более сложные, чем часто используемые прогрессивные методы, существует несколько программ для получения выравниваний. Например, [http://sourceforge.net/projects/poamsa/files/ POA] <ref name="grasso">{{cite journal | doi = 10.1093/bioinformatics/bth126 | author = Grasso C, Lee C | year = 2004 | title = Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems | url = | journal = Bioinformatics | volume = 20 | issue = 10| pages = 1546–56 | pmid = 14962922 }}</ref>, похожий, но более обобщенный метод в пакетах [http://compbio.soe.ucsc.edu/sam.html SAM] <ref name="hugheyT">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.</ref> и HMMER () <ref name="durbin">Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.</ref>с. SAM используется для получения выравниваний для предсказания структуры белков в эксперименте [[CASP]] для дрожжевых белков. HHsearch, основанный на парном сравнении HMMs, <ref>{{ cite journal| author = Battey JN, Kopp J, Bordoli L, Read RJ, Clarke ND, Schwede T| title = Automated server predictions in CASP7| journal = Proteins | year = 2007 | volume = 69 | issue = Suppl 8 | pages = 68–82 | pmid = 17894354| doi = 10.1002/prot.21761 }}</ref> используется для поиска отдаленно связанных последовательностей. Сервер, запускающий HHsearch (HHpred ()) был самым быстрым из 10 лучших автоматических серверов по предсказанию структур белков в CASP7 и CASP8.


[[Категория:Генетика]]
[[Категория:Генетика]]

Версия от 18:18, 12 апреля 2016

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

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

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

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

Для построения глобального оптимального выравнивания напрямую используется динамическое программирование. Для белковых последовательностей существует два набора параметров: штраф за гэп и матрица замен, содержащая в себе вероятности сопоставления пары аминокислотных остатков, основанных на схожести их химических свойств и эволюционной вероятности мутации. Для нуклеотидных последовательностей также используется штраф за гэп, но матрица замен гораздо проще, там учитываются только идентичные совпадения и мисматчи (несовпадения) [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].

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

Еще одна итеративная программа, DIALIGN, использует необычный подход, сосредотачивая внимание на локальных выравниваниях подсегментов или мотивов последовательностей без введения штрафа за гэп [16].Выравнивание отдельных мотивов представляется в матричной виде, сходном с диаграммой с точками (dot-plot) в парном выравнивании. Альтернативный метод, который использует быстрые локальные выравнивания как точки заякоривания для более медленной процедуры построения глобального выравнивания представлен в софте CHAOS/DIALIGN (http://dialign.gobics.de/chaos-dialign-submission)[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.

  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. PMC 287279. PMID 2734293.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  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 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. PMC 308517. PMID 7984417.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
  12. ↑ EMBL-EBI-ClustalW2-Multiple Sequence Alignment. CLUSTALW2.
  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) (ссылка)
  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) (ссылка)
  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: 66. doi:10.1186/1471-2105-4-66.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Википедия:Обслуживание CS1 (не помеченный открытым DOI) (ссылка)
  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.
  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) (ссылка)
  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.{{cite journal}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
Источник — https://ru.wikipedia.org/w/index.php?title=Множественное_выравнивание_последовательностей&oldid=77742270