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

Первые 90 положений множественного выравнивания последовательностей белка для примеров кислого рибосомного белка P0 (L10E) из нескольких организмов. Создано с помощью ClustalX.

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

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

Алгоритм

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

Математическое определение

Данный ${displaystyle m}$ последовательности ${displaystyle S_{i}}$, ${displaystyle i=1,cdots ,m}$ аналогично форме ниже:

${displaystyle S:={egin{cases}S_{1}=(S_{11},S_{12},ldots ,S_{1n_{1}})S_{2}=(S_{21},S_{22},cdots ,S_{2n_{2}}),,,,,,,,,,vdots S_{m}=(S_{m1},S_{m2},ldots ,S_{mn_{m}})end{cases}}}$

Для этого набора последовательностей проводится множественное выравнивание последовательностей. ${displaystyle S}$ вставив необходимое количество зазоров в каждый из ${displaystyle S_{i}}$ последовательности ${displaystyle S}$ пока измененные последовательности, ${displaystyle S'_{i}}$, все соответствуют длине ${displaystyle Lgeq max{n_{i}mid i=1,ldots ,m}}$ и нет значений в последовательностях ${displaystyle S}$ одного столбца состоит только из пробелов. Математическая форма MSA указанного выше набора последовательностей показана ниже:

${displaystyle S':={egin{cases}S'_{1}=(S'_{11},S'_{12},ldots ,S'_{1L})S'_{2}=(S'_{21},S'_{22},ldots ,S'_{2L}),,,,,,,,,,vdots S'_{m}=(S'_{m1},S'_{m2},ldots ,S'_{mL})end{cases}}}$

Чтобы вернуться из каждой конкретной последовательности ${displaystyle S'_{i}}$ к ${displaystyle S_{i}}$, убираем все зазоры.

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

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

Отслеживание выравниваний

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

Приложение в коде

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

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

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

Методы совмещения

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

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

Наиболее широко используемый подход к множественному выравниванию последовательностей использует эвристический поиск, известный как прогрессивный метод (также известный как иерархический или древовидный метод), разработанный Да-Фей Фэном и Дулиттлом в 1987 году.^[11] Прогрессивное выравнивание создает окончательный MSA путем комбинирования попарных выравниваний, начиная с наиболее похожей пары и переходя к наиболее отдаленно связанным. Все методы прогрессивного выравнивания требуют двух стадий: первая стадия, на которой отношения между последовательностями представлены как дерево, называется направляющее деревои второй шаг, на котором MSA строится путем последовательного добавления последовательностей к растущему MSA в соответствии с направляющим деревом. Начальный направляющее дерево определяется эффективным кластеризация метод, такой как присоединение к соседу или же UPGMA, и может использовать расстояния на основе количества идентичных двухбуквенных подпоследовательностей (как в ФАСТА а не согласование динамического программирования).^[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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Филогенетические методы

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

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

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

Поиск мотива

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

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

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

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

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

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

Оптимизация

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

Стандартные методы оптимизации в информатике - оба из которых основаны на физических процессах, но не воспроизводят их напрямую - также использовались в попытке более эффективно производить качественные 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 объявила, что ее программное обеспечение для квантовых вычислений с открытым исходным кодом qbsolv было успешно использовано для поиска более быстрого решения проблемы MSA.^[41]

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

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

Обзорные статьи

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

внешняя ссылка

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

Конспекты лекций, учебные пособия и курсы

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