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

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

Вычислительные алгоритмы используются для создания и анализа MSA из-за сложности и невозможности ручной обработки последовательностей с учетом их биологически значимой длины. MSA требуют более сложных методологий, чем попарное выравнивание, поскольку они более сложны в вычислительном отношении . Большинство программ множественного выравнивания последовательностей используют эвристические методы, а не глобальную оптимизацию.потому что определение оптимального выравнивания между более чем несколькими последовательностями умеренной длины является чрезмерно затратным с точки зрения вычислений. С другой стороны, эвристические методы обычно не дают гарантий качества решения, а эвристические решения зачастую намного ниже оптимального решения на тестовых экземплярах. [1] [2] [3]

Описание проблемы [ править ]

Заданные последовательности , похожие на форму ниже:

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

Для возврата из каждой конкретной последовательности , чтобы , удалить все пробелы.

Графический подход [ править ]

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

Трассировка выравниваний [ править ]

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

Методы выравнивания [ править ]

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

Динамическое программирование [ править ]

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

Для n отдельных последовательностей наивный метод требует построения n- мерного эквивалента матрицы, сформированной при стандартном попарном выравнивании последовательностей . Таким образом, пространство поиска увеличивается экспоненциально с увеличением n и также сильно зависит от длины последовательности. Выражаясь в нотации большого O, обычно используемой для измерения вычислительной сложности , на создание простого MSA требуется время O (Length Nseqs ) . Было показано, что найти глобальный оптимум для n последовательностей этим способом является NP-полной задачей. [5] [6] [7] В 1989 году, основанный на алгоритме Каррилло-Липмана, [8] Альтшул представил практический метод, который использует парное выравнивание для ограничения n-мерного пространства поиска. [9] В этом подходе парные выравнивания динамического программирования выполняются для каждой пары последовательностей в наборе запроса, и только пространство около n-мерного пересечения этих выравниваний ищется для n-стороннего выравнивания. Программа MSA оптимизирует сумму всех пар символов в каждой позиции в выравнивании (так называемая сумма парных баллов) и была реализована в виде программного обеспечения для построения множественных выравниваний последовательностей. [10]В 2019 году Хоссейнинасаб и ван Хов показали, что с помощью диаграмм решений MSA можно моделировать в полиномиальной пространственной сложности. [3]

Построение прогрессивного выравнивания [ править ]

Наиболее широко используемый подход к множественному выравниванию последовательностей использует эвристический поиск, известный как прогрессивный метод (также известный как иерархический или древовидный метод), разработанный Да-Фэем Фэном и Дулиттлом в 1987 году. [11] Прогрессивное выравнивание создает окончательный MSA путем комбинирования. попарные выравнивания, начинающиеся с наиболее похожей пары и переходящие к наиболее отдаленно связанным. Все методы прогрессивного выравнивания требуют двух этапов: первого этапа, на котором отношения между последовательностями представлены в виде дерева , называемого направляющим деревом , и второго этапа, на котором MSA строится путем последовательного добавления последовательностей к растущему MSA в соответствии с направляющее дерево. Исходное дерево направляющих определяется эффективнымметод кластеризации, такой как соединение соседей или UPGMA , и может использовать расстояния на основе количества идентичных двухбуквенных подпоследовательностей (как в FASTA, а не выравнивание динамического программирования). [12]

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

Методы прогрессивного выравнивания достаточно эффективны, чтобы реализовать их в большом масштабе для многих (от 100 до 1000) последовательностей. Услуги прогрессивного выравнивания обычно доступны на общедоступных веб-серверах, поэтому пользователям не нужно локально устанавливать интересующие их приложения. Наиболее популярный прогрессивный способ выравнивания был Clustal семьи, [13] , особенно взвешенный вариант ClustalW [14] , доступ к которым обеспечивается большое количество веб - порталов , в том числе GenomeNet , EBI и EMBNet. Различные порталы или реализации могут различаться по пользовательскому интерфейсу и делать разные параметры доступными для пользователя. ClustalW широко используется для построения филогенетического дерева, несмотря на явные предупреждения автора о том, что неотредактированные сопоставления не должны использоваться в таких исследованиях, а также в качестве входных данных для предсказания структуры белка путем моделирования гомологии. Текущая версия семейства Clustal - ClustalW2. EMBL-EBI объявила, что CLustalW2 истечет в августе 2015 года. Они рекомендуют Clustal Omega, который работает на основе засеянных направляющих деревьев и методов профиля-профиля HMM для выравнивания белков. Они предлагают различные инструменты MSA для прогрессивного выравнивания ДНК. Один из них - MAFFT (множественное выравнивание с использованием быстрого преобразования Фурье). [15]

Другой распространенный метод прогрессивного выравнивания, называемый T-Coffee [16] , медленнее, чем Clustal и его производные, но обычно дает более точное выравнивание для наборов отдаленно связанных последовательностей. T-Coffee вычисляет попарные выравнивания, комбинируя прямое выравнивание пары с непрямым выравниванием, которое выравнивает каждую последовательность пары с третьей последовательностью. Он использует выходные данные Clustal, а также другой программы локального выравнивания LALIGN, которая находит несколько областей локального выравнивания между двумя последовательностями. Полученное выравнивание и филогенетическое дерево используются в качестве руководства для получения новых и более точных весовых коэффициентов.

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

Итерационные методы [ править ]

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

Было реализовано множество слегка различных итерационных методов, которые стали доступными в программных пакетах; обзоры и сравнения были полезны, но обычно воздерживаются от выбора «лучшей» техники. [18] Программный пакет PRRN / PRRP использует алгоритм подъема в гору для оптимизации своей оценки выравнивания MSA [19] и итеративно корректирует как веса выравнивания, так и локально расходящиеся или «глючные» области растущей MSA. [12] PRRP лучше всего работает при уточнении выравнивания, ранее созданного более быстрым методом. [12]

Другая итеративная программа, DIALIGN, использует необычный подход, узко фокусируясь на локальных выравниваниях между подсегментами или мотивами последовательностей без введения штрафа за пропуски. [20] Выравнивание отдельных мотивов затем достигается с помощью матричного представления, аналогичного точечно-матричному графику при попарном выравнивании. Альтернативный метод, использующий быстрое локальное выравнивание в качестве опорных точек или « начальных точек» для более медленной процедуры глобального выравнивания, реализован в наборе CHAOS / DIALIGN . [20]

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

Консенсусные методы [ править ]

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

Скрытые марковские модели [ править ]

Профиль HMM, моделирующий множественное выравнивание последовательностей

Скрытые марковские модели - это вероятностные модели, которые могут назначать вероятности всем возможным комбинациям пробелов, совпадений и несовпадений, чтобы определить наиболее вероятную MSA или набор возможных MSA. HMM могут давать единственный результат с наивысшей оценкой, но также могут генерировать семейство возможных выравниваний, которые затем могут быть оценены на предмет биологической значимости. HMM могут производить как глобальные, так и локальные выравнивания. Хотя методы на основе HMM были разработаны относительно недавно, они предлагают значительные улучшения в скорости вычислений, особенно для последовательностей, содержащих перекрывающиеся области. [12]

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

Доступно несколько программ, в которых реализованы варианты методов на основе HMM и которые отличаются своей масштабируемостью и эффективностью, хотя правильное использование метода HMM более сложно, чем использование более распространенных прогрессивных методов. Самый простой - это POA (Partial-Order Alignment); [24] аналогичный, но более обобщенный метод реализован в пакетах SAM (Sequence Alignment and Modeling System). [25] и HMMER . [26] SAM использовался в качестве источника выравнивания для предсказания структуры белка, чтобы участвовать в эксперименте предсказания структуры CASP и для разработки базы данных предсказанных белков ввиды дрожжей S. cerevisiae . HHsearch [27] - это программный пакет для обнаружения отдаленно связанных белковых последовательностей на основе попарного сравнения HMM. Сервер, на котором запущен HHsearch ( HHpred ), был безусловно самым быстрым из 10 лучших серверов автоматического прогнозирования структуры в соревнованиях по прогнозированию структуры CASP7 и CASP8. [28]

Филогенетические методы [ править ]

Негомологичное выравнивание экзонов итерационным методом (а) и методом с учетом филогении (б)

Большинство методов множественного выравнивания последовательностей пытаются минимизировать количество вставок / делеций (пропусков) и, как следствие, производить компактные выравнивания. Это вызывает несколько проблем, если выравниваемые последовательности содержат негомологичные области, если пробелы являются информативными при филогенетическом анализе. Эти проблемы типичны для вновь полученных последовательностей, которые плохо аннотированы и могут содержать сдвиг рамки считывания , неправильные домены или негомологичные сплайсированные экзоны . Первый такой метод был разработан в 2005 году Лойтыной и Гольдманом. [29] Те же авторы выпустили программный пакет под названием PRANK в 2008 году. [30]PRANK улучшает выравнивание при наличии вставок. Тем не менее, он работает медленно по сравнению с прогрессивными и / или итерационными методами, которые разрабатывались в течение нескольких лет.

В 2012 году появились два новых инструмента, учитывающих филогенез. Один из них называется PAGAN и был разработан той же командой, что и PRANK. [31] Другой - ProGraphMSA, разработанный Шалковски. [32] Оба пакета программного обеспечения были разработаны независимо, но имеют общие черты, в частности, использование алгоритмов графа для улучшения распознавания негомологичных областей и улучшение кода, делающее это программное обеспечение быстрее, чем PRANK.

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

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

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

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

Статистическое сопоставление с образцом было реализовано с использованием алгоритма максимизации ожидания и сэмплера Гиббса . Один из наиболее распространенных инструментов поиска мотивов, известный как MEME , использует максимизацию ожиданий и скрытые методы Маркова для создания мотивов, которые затем используются в качестве инструментов поиска его сопутствующим MAST в комбинированном наборе MEME / MAST . [34] [35]

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

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

Оптимизация [ править ]

Генетические алгоритмы и имитация отжига [ править ]

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

Техника имитации отжига, с помощью которого существующий MSA, созданный другим методом, уточняется серией перестановок, предназначенных для поиска лучших областей пространства выравнивания, чем та, которую уже занимает выравнивание ввода. Как и метод генетического алгоритма, имитация отжига максимизирует целевую функцию, такую ​​как функция суммы пар. При моделировании отжига используется метафорический «температурный фактор», который определяет скорость, с которой происходят перегруппировки, и вероятность каждой перегруппировки; Типичное использование чередует периоды высоких скоростей перегруппировки с относительно низкой вероятностью (для исследования более отдаленных областей пространства выравнивания) с периодами более низких скоростей и более высокой вероятностью для более тщательного изучения локальных минимумов вблизи недавно «колонизированных» регионов.Этот подход реализован в программе MSASA (Multiple Sequence Alignment by Simulated Annealing).[39]

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

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

Имитация квантовых вычислений [ править ]

В январе 2017 года D-Wave Systems объявила, что ее программное обеспечение для квантовых вычислений с открытым исходным кодом qbsolv было успешно использовано для поиска более быстрого решения проблемы MSA. [41]

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

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

Однако по мере увеличения количества последовательностей, особенно в исследованиях на уровне всего генома, в которых задействовано много MSA, невозможно вручную провести все сопоставления. Кроме того, ручное курирование субъективно. И, наконец, даже лучший эксперт не может уверенно сопоставить более неоднозначные случаи сильно расходящихся последовательностей. В таких случаях обычной практикой является использование автоматических процедур для исключения ненадежно выровненных регионов из MSA. С целью реконструкции филогении (см. Ниже) программа Gblocks широко используется для удаления блоков выравнивания, подозреваемых в низком качестве, в соответствии с различными отсечениями количества последовательностей с пропусками в столбцах выравнивания. [43]Однако эти критерии могут излишне отфильтровывать области с событиями вставки / удаления, которые все еще могут быть надежно выровнены, и эти области могут быть желательны для других целей, таких как обнаружение положительного выбора. Несколько алгоритмов выравнивания выводят оценки для конкретных участков, что позволяет выбирать регионы с высокой степенью достоверности. Такая услуга была впервые предложена программой SOAP [44], которая проверяет устойчивость каждого столбца к возмущениям в параметрах популярной программы выравнивания CLUSTALW. Программа T-Coffee [45] использует библиотеку выравниваний при построении окончательного MSA, и ее выходной MSA окрашен в соответствии с оценками достоверности, которые отражают согласие между различными выравниваниями в библиотеке относительно каждого выровненного остатка. Его расширение,TCS  : ( ядро T ransitive C onsistency S ), использует библиотеки попарного выравнивания T-Coffee для оценки любого стороннего MSA. Парные прогнозы можно производить с использованием быстрых или медленных методов, что позволяет найти компромисс между скоростью и точностью. [46] [47] Другой программой выравнивания, которая может выводить MSA с оценками достоверности, является FSA [48], в которой используется статистическая модель, позволяющая рассчитать неопределенность при выравнивании. Оценка HoT («головы или хвосты») может использоваться в качестве меры неопределенности согласования для конкретного участка из-за наличия нескольких совместно оптимальных решений. [49] Программа GUIDANCE [50]вычисляет аналогичный показатель достоверности для конкретного объекта на основе устойчивости согласования к неопределенности в дереве направляющих, которое используется в программах прогрессивного согласования. Альтернативный, более статистически обоснованный подход к оценке неопределенности выравнивания - использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. Байесовский подход позволяет рассчитать апостериорные вероятности предполагаемой филогении и выравнивания, что является мерой достоверности этих оценок. В этом случае для каждого участка трассы можно рассчитать апостериорную вероятность. Такой подход реализован в программе BAli-Phy. [51]

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

Филогенетическое использование [ править ]

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

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

См. Также [ править ]

  • Кладистика
  • Обобщенное выравнивание дерева
  • Филогенетика
  • Программное обеспечение для выравнивания последовательностей
  • Множественные программы просмотра выравнивания последовательностей
  • Структурное выравнивание
  • Анализ последовательности без выравнивания

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

  1. ^ Thompson JD, Linard B, Lecompte O, Poch O (2011). «Комплексное сравнительное исследование нескольких методов выравнивания последовательностей: текущие проблемы и перспективы на будущее» . PLOS ONE . 6 (3): e18093. Bibcode : 2011PLoSO ... 618093T . DOI : 10.1371 / journal.pone.0018093 . PMC  3069049 . PMID  21483869 .
  2. ^ a b Nuin PA, Wang Z, Tillier ER (2006). «Точность нескольких программ выравнивания множественных последовательностей для белков» . BMC Bioinformatics . 7 : 471. DOI : 10,1186 / 1471-2105-7-471 . PMC 1633746 . PMID 17062146 .  
  3. ^ a b c Hosseininasab A, van Hoeve WJ (2019). «Точное согласование нескольких последовательностей с помощью синхронизированных диаграмм принятия решений». ИНФОРМС Журнал по вычислительной технике . DOI : 10.1287 / ijoc.2019.0937 .
  4. ^ «Помощь с матрицами, используемыми в инструментах сравнения последовательностей» . Европейский институт биоинформатики. Архивировано из оригинала на 11 марта 2010 года . Проверено 3 марта 2010 года .
  5. Перейти ↑ Wang L, Jiang T (1994). «О сложности множественного выравнивания последовательностей». J Comput Biol . 1 (4): 337–348. CiteSeerX 10.1.1.408.894 . DOI : 10,1089 / cmb.1994.1.337 . PMID 8790475 .  
  6. ↑ Just W (2001). «Вычислительная сложность множественного выравнивания последовательностей с SP-оценкой». J Comput Biol . 8 (6): 615–23. CiteSeerX 10.1.1.31.6382 . DOI : 10.1089 / 106652701753307511 . PMID 11747615 .  
  7. ^ Элиас, Исаак (2006). «Урегулирование неразрешимости множественного выравнивания». J Comput Biol . 13 (7): 1323–1339. CiteSeerX 10.1.1.6.256 . DOI : 10,1089 / cmb.2006.13.1323 . PMID 17037961 .  
  8. Перейти ↑ Carrillo H, Lipman DJ (1988). «Проблема множественного выравнивания последовательностей в биологии» . Журнал SIAM по прикладной математике . 48 (5): 1073–1082. DOI : 10.1137 / 0148063 .
  9. ^ Липман DJ, Altschul SF, Kececioglu JD (1989). «Инструмент для множественного выравнивания последовательностей» . Proc Natl Acad Sci USA . 86 (12): 4412–4415. Полномочный код : 1989PNAS ... 86.4412L . DOI : 10.1073 / pnas.86.12.4412 . PMC 287279 . PMID 2734293 .  
  10. ^ "Программное обеспечение для генетического анализа" . Национальный центр биотехнологической информации . Проверено 3 марта 2010 года .
  11. ^ Feng DF, Дулитл РФ (1987). «Прогрессивное выравнивание последовательностей как предварительное условие для исправления филогенетических деревьев». J Mol Evol . 25 (4): 351–360. Bibcode : 1987JMolE..25..351F . DOI : 10.1007 / BF02603120 . PMID 3118049 . S2CID 6345432 .  
  12. ^ a b c d e f g h Установите DM. (2004). Биоинформатика: анализ последовательности и генома 2-е изд. Пресса лаборатории Колд-Спринг-Харбор: Колд-Спринг-Харбор, Нью-Йорк.
  13. Перейти ↑ Higgins DG , Sharp PM (1988). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–244. DOI : 10.1016 / 0378-1119 (88) 90330-7 . PMID 3243435 . 
  14. ^ Томпсон JD, Хиггинс DG, Гибсон TJ (ноябрь 1994). «CLUSTAL W: повышение чувствительности прогрессивного множественного выравнивания последовательностей за счет взвешивания последовательностей, штрафов за пропуски в зависимости от позиции и выбора матрицы весов» . Nucleic Acids Res . 22 (22): 4673–80. DOI : 10.1093 / NAR / 22.22.4673 . PMC 308517 . PMID 7984417 .  
  15. ^ «EMBL-EBI-ClustalW2-Multiple Sequence Alignment» . CLUSTALW2 .
  16. ^ Notredame C, Хиггинс DG, Херинга J (сентябрь 2000). «T-Coffee: новый метод быстрого и точного выравнивания множественных последовательностей». J. Mol. Биол . 302 (1): 205–17. DOI : 10.1006 / jmbi.2000.4042 . PMID 10964570 . 
  17. ^ Зи SH, Lu Y, Ян Q (2006). «Полиномиально разрешимая формулировка множественного выравнивания последовательностей». J Comput Biol . 13 (2): 309–319. DOI : 10,1089 / cmb.2006.13.309 . PMID 16597242 . 
  18. ^ Hirosawa M, Totoki Y, Hoshida M, Ishikawa M (1995). «Комплексное исследование итерационных алгоритмов множественного выравнивания последовательностей». Comput Appl Biosci . 11 (1): 13–18. DOI : 10.1093 / биоинформатики / 11.1.13 . PMID 7796270 . 
  19. ^ Гото О (1996). «Значительное улучшение точности множественных выравниваний последовательностей белков за счет итеративного уточнения по оценке структурных выравниваний». J Mol Biol . 264 (4): 823–38. DOI : 10.1006 / jmbi.1996.0679 . PMID 8980688 . 
  20. ^ a b Brudno M, Chapman M, Göttgens B, Batzoglou S, Morgenstern B (декабрь 2003 г.). «Быстрое и чувствительное множественное выравнивание больших геномных последовательностей» . BMC Bioinformatics . 4 : 66. DOI : 10,1186 / 1471-2105-4-66 . PMC 521198 . PMID 14693042 .  
  21. ↑ Эдгар RC (2004). «МЫШЦЫ: множественное выравнивание последовательностей с высокой точностью и высокой производительностью» . Исследования нуклеиновых кислот . 32 (5): 1792–97. DOI : 10.1093 / NAR / gkh340 . PMC 390337 . PMID 15034147 .  
  22. ^ Collingridge PW, Келли S (2012). «MergeAlign: улучшение производительности множественного выравнивания последовательностей за счет динамической реконструкции согласованных множественных выравниваний последовательностей» . BMC Bioinformatics . 13 (117): 117. DOI : 10,1186 / 1471-2105-13-117 . PMC 3413523 . PMID 22646090 .  
  23. ^ Хьюи R, Крог А (1996). «Скрытые марковские модели для анализа последовательностей: расширение и анализ основного метода». КАБИОС . 12 (2): 95–107. CiteSeerX 10.1.1.44.3365 . DOI : 10.1093 / биоинформатики / 12.2.95 . PMID 8744772 .  
  24. Перейти ↑ Grasso C, Lee C (2004). «Комбинация выравнивания частичного порядка и последовательного последовательного выравнивания увеличивает скорость выравнивания и масштабируемость для решения очень больших проблем выравнивания» . Биоинформатика . 20 (10): 1546–56. DOI : 10.1093 / биоинформатики / bth126 . PMID 14962922 . 
  25. ^ Hughey R, Krogh A. SAM: Система программного обеспечения для выравнивания и моделирования последовательностей. Технический отчет UCSC-CRL-96-22, Калифорнийский университет, Санта-Крус, Калифорния, сентябрь 1996 г.
  26. Перейти ↑ Durbin R, Eddy S, Krogh A, Mitchison G. (1998). Анализ биологической последовательности: вероятностные модели белков и нуклеиновых кислот, Cambridge University Press, 1998.
  27. ^ Зёдинг J (2005). «Определение гомологии белков путем сравнения HMM-HMM». Биоинформатика . 21 (7): 951–960. CiteSeerX 10.1.1.519.1257 . DOI : 10.1093 / биоинформатики / bti125 . PMID 15531603 .  
  28. ^ Battey Ю.Н., Копп Дж, Bordoli л, чтение RJ, Кларк Д., Schwede Т (2007). «Автоматизированные предсказания сервера в CASP7» . Белки . 69 (Дополнение 8): 68–82. DOI : 10.1002 / prot.21761 . PMID 17894354 . S2CID 29879391 .  
  29. ^ Loytynoja, A. (2005). «Алгоритм прогрессивного множественного выравнивания последовательностей со вставками» . Труды Национальной академии наук . 102 (30): 10557–10562. Bibcode : 2005PNAS..10210557L . DOI : 10.1073 / pnas.0409137102 . PMC 1180752 . PMID 16000407 .  
  30. ^ Löytynoja A, Goldman N (июнь 2008). «Размещение пробелов с учетом филогении предотвращает ошибки в выравнивании последовательностей и эволюционном анализе». Наука . 320 (5883): 1632–5. Bibcode : 2008Sci ... 320.1632L . DOI : 10.1126 / science.1158395 . PMID 18566285 . S2CID 5211928 .  
  31. ^ Löytynoja A, Vilella AJ, Goldman N (июль 2012). «Точное расширение нескольких выравниваний последовательностей с использованием алгоритма графа с учетом филогении» . Биоинформатика . 28 (13): 1684–91. DOI : 10.1093 / биоинформатики / bts198 . PMC 3381962 . PMID 22531217 .  
  32. ^ Szalkowski AM (июнь 2012). «Быстрое и надежное множественное выравнивание последовательностей с учетом филогении размещения пробелов» . BMC Bioinformatics . 13 : 129. DOI : 10,1186 / 1471-2105-13-129 . PMC 3495709 . PMID 22694311 .  
  33. ^ Henikoff S, Henikoff JG (декабрь 1991). «Автоматическая сборка белковых блоков для поиска в базе данных» . Nucleic Acids Res . 19 (23): 6565–72. DOI : 10.1093 / NAR / 19.23.6565 . PMC 329220 . PMID 1754394 .  
  34. ^ Bailey TL, Elkan C (1994). «Подбор модели смеси путем максимизации ожиданий для обнаружения мотивов в биополимерах» (PDF) . Труды Второй Международной конференции по интеллектуальным системам для молекулярной биологии . Менло-Парк, Калифорния: AAAI Press. С. 28–36.
  35. ^ Bailey TL, Грибсков M (1998). «Объединение доказательств с использованием p-значений: приложение к поискам гомологии последовательностей» . Биоинформатика . 14 (1): 48–54. DOI : 10.1093 / биоинформатики / 14.1.48 . PMID 9520501 . 
  36. Перейти ↑ Salama RA, Stekel DJ (ноябрь 2013 г.). «Несамостоятельное выравнивание множественных последовательностей на основе энергии улучшает предсказание сайтов связывания факторов транскрипции» . Биоинформатика . 29 (21): 2699–704. DOI : 10.1093 / биоинформатики / btt463 . PMID 23990411 . 
  37. ^ Notredame C, Хиггинс DG (апрель 1996). «САГА: выравнивание последовательностей с помощью генетического алгоритма» . Nucleic Acids Res . 24 (8): 1515–24. DOI : 10.1093 / NAR / 24.8.1515 . PMC 145823 . PMID 8628686 .  
  38. ^ Notredame C, О'Брайен EA, Хиггинс DG (1997). «RAGA: выравнивание последовательностей РНК с помощью генетического алгоритма» . Nucleic Acids Res . 25 (22): 4570–80. DOI : 10.1093 / NAR / 25.22.4570 . PMC 147093 . PMID 9358168 .  
  39. ^ Ким Дж, Pramanik S, Chung МДж (1994). «Множественное выравнивание последовательностей с использованием имитации отжига». Comput Appl Biosci . 10 (4): 419–26. DOI : 10.1093 / биоинформатики / 10.4.419 . PMID 7804875 . 
  40. ^ Althaus E, Капрар A, Lenhof HP, Reinert K (2006). «Алгоритм ветвления и отсечения для множественного выравнивания последовательностей». Математическое программирование . 105 (2–3): 387–425. DOI : 10.1007 / s10107-005-0659-3 . S2CID 17715172 . 
  41. ^ D-Wave Initiates Open Quantum Software Environment 11 января 2017 г.
  42. ^ «Ручное редактирование и настройка MSA» . Европейская лаборатория молекулярной биологии. 2007. Архивировано из оригинального 24 сентября 2015 года . Проверено 7 марта 2010 года .
  43. ^ Castresana J (апрель 2000). «Выбор консервативных блоков из нескольких выравниваний для их использования в филогенетическом анализе» . Мол. Биол. Evol . 17 (4): 540–52. DOI : 10.1093 / oxfordjournals.molbev.a026334 . PMID 10742046 . 
  44. ^ Löytynoja A, Milinkovitch MC (июнь 2001). «SOAP, очищающий множественные выравнивания от нестабильных блоков» . Биоинформатика . 17 (6): 573–4. DOI : 10.1093 / биоинформатики / 17.6.573 . PMID 11395440 . 
  45. ^ Пуаро О, О'Тул E, Notredame C (июль 2003 г.). «Tcoffee @ igs: веб-сервер для вычисления, оценки и объединения нескольких выравниваний последовательностей» . Nucleic Acids Res . 31 (13): 3503–6. DOI : 10.1093 / NAR / gkg522 . PMC 168929 . PMID 12824354 .  
  46. ^ Чанг, JM; Di Tommaso, P; Notredame, C (июнь 2014 г.). «TCS: новая мера надежности множественного выравнивания последовательностей для оценки точности выравнивания и улучшения реконструкции филогенетического дерева» . Молекулярная биология и эволюция . 31 (6): 1625–37. DOI : 10.1093 / molbev / msu117 . PMID 24694831 . 
  47. ^ Чанг JM, ди Томмазо Р, Лефорт В, Gascuel О, Notredame С (июль 2015). «TCS: веб-сервер для оценки множественного выравнивания последовательностей и филогенетической реконструкции» . Nucleic Acids Res . 43 (W1): W3–6. DOI : 10.1093 / NAR / gkv310 . PMC 4489230 . PMID 25855806 .  
  48. ^ Брэдли RK, Робертс A, M Смут, Juvekar S, Do J, Dewey C, Холмс I, Пэчтер L (май 2009). «Быстрое статистическое выравнивание» . PLOS Comput. Биол . 5 (5): e1000392. Bibcode : 2009PLSCB ... 5E0392B . DOI : 10.1371 / journal.pcbi.1000392 . PMC 2684580 . PMID 19478997 .  
  49. ^ Landan G, Граур D (2008). «Местные меры надежности из наборов кооптимальных множественных выравниваний последовательностей». Биокомпьютинг 2008 . Pac Symp Biocomput . С. 15–24. DOI : 10.1142 / 9789812776136_0003 . ISBN 978-981-277-608-2. PMID  18229673 .
  50. ^ Пенна О, Привман Е, Landan G, D Граур, Пупко Т (август 2010 г.). «Оценка достоверности выравнивания, отражающая надежность для определения неопределенности дерева» . Мол. Биол. Evol . 27 (8): 1759–67. DOI : 10.1093 / molbev / msq066 . PMC 2908709 . PMID 20207713 .  
  51. ^ Redelings BD, Suchard MA (июнь 2005). «Совместная байесовская оценка выравнивания и филогении» . Syst. Биол . 54 (3): 401–18. DOI : 10.1080 / 10635150590947041 . PMID 16012107 . 
  52. ^ a b Бадд, Эйдан (10 февраля 2009 г.). «Упражнения и демонстрации по согласованию нескольких последовательностей» . Европейская лаборатория молекулярной биологии. Архивировано из оригинала 5 марта 2012 года . Проверено 30 июня 2010 года .

Статьи обзора [ править ]

  • Duret, L .; С. Абдеддаим (2000). «Множественное выравнивание для структурно-функционального или филогенетического анализа гомологичных последовательностей». В Д. Хиггинсе и В. Тейлоре (ред.). Структура последовательностей биоинформатики и банки данных . Оксфорд: Издательство Оксфордского университета.
  • Notredame, C. (2002). «Последние достижения в выравнивании множественных последовательностей: обзор». Фармакогеномика . 3 (1): 131–144. DOI : 10.1517 / 14622416.3.1.131 . PMID  11966409 .
  • Томпсон, JD; Plewniak, F .; Поч, О. (1999). «Комплексное сравнение нескольких программ выравнивания последовательностей» . Исследования нуклеиновых кислот . 27 (13): 12682–2690. DOI : 10.1093 / NAR / 27.13.2682 . PMC  148477 . PMID  10373585 .
  • Уоллес, И. М.; Blackshields, G .; Хиггинс, Д.Г. (2005). «Множественные выравнивания последовательностей». Curr Opin Struct Biol . 15 (3): 261–266. DOI : 10.1016 / j.sbi.2005.04.002 . PMID  15963889 .
  • Notredame, C (2007). «Последние разработки алгоритмов выравнивания множественных последовательностей» . PLOS Вычислительная биология . 3 (8): e123. Bibcode : 2007PLSCB ... 3..123N . DOI : 10.1371 / journal.pcbi.0030123 . PMC  1963500 . PMID  17784778 .

Внешние ссылки [ править ]

  • Инструменты выравнивания последовательностей ExPASy
  • Архивная страница ресурсов множественного выравнивания  - из Виртуальной школы естественных наук
  • Инструменты для множественного совмещения  - от Pôle Bioinformatique Lyonnais
  • Точка входа к серверам Clustal и информации
  • Точка входа на основные серверы T-Coffee
  • Точка входа на главный сервер MergeAlign и информацию
  • Серверы Европейского института биоинформатики:
    • ClustalW2  - универсальная программа для выравнивания множественных последовательностей ДНК или белков.
    • Мышца  - сравнение нескольких последовательностей с помощью логарифмического ожидания
    • T-coffee  - множественное выравнивание последовательностей.
    • MAFFT  - множественное выравнивание с использованием быстрого преобразования Фурье
    • KALIGN  - быстрый и точный алгоритм множественного выравнивания последовательностей.

Конспекты лекций, учебные пособия и курсы [ править ]

  • Лекции по множественному выравниванию последовательностей  - от Института молекулярной генетики Макса Планка
  • Конспекты лекций и практические упражнения по множественному выравниванию последовательностей в EMBL
  • Конспект лекций по молекулярной биоинформатике
  • Конспект лекций по молекулярной эволюции и биоинформатике