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

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

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

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

Постановка задачи

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

$S:={\begin{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}}$

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

$S':={\begin{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}}$

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

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

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

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

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

Методы выравнивания

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

Динамическое программирование

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

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

Прогрессивная конструкция выравнивания

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

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

Методы прогрессивного выравнивания достаточно эффективны, чтобы их можно было реализовать в больших масштабах для многих последовательностей (от 100 до 1000). Популярным методом прогрессивного выравнивания является семейство Clustal . ClustalW широко используется для построения филогенетических деревьев, несмотря на явные предупреждения автора о том, что неотредактированные выравнивания не следует использовать в таких исследованиях, а также в качестве входных данных для предсказания структуры белка путем моделирования гомологии. EMBL-EBI объявила, что срок действия CLustalW2 истекает в августе 2015 года. Они рекомендуют Clustal Omega, который работает на основе засеянных направляющих деревьев и методов профиля-профиля HMM для выравнивания белков. Альтернативным инструментом для прогрессивного выравнивания ДНК является MAFFT (множественное выравнивание с использованием быстрого преобразования Фурье).

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

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

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

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

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

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

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

Методы консенсуса

Методы консенсуса пытаются найти оптимальное множественное выравнивание последовательностей с учетом нескольких различных выравниваний одного и того же набора последовательностей. Существует два широко используемых метода консенсуса: M-COFFEE и MergeAlign. M-COFFEE использует множественные выравнивания последовательностей, созданные семью различными методами, для создания консенсусных выравниваний. MergeAlign способен генерировать консенсусные выравнивания из любого количества входных выравниваний, созданных с использованием различных моделей эволюции последовательностей или разных методов множественного выравнивания последовательностей. Опция по умолчанию для MergeAlign — сделать вывод о консенсусном выравнивании, используя выравнивания, созданные с использованием 91 различных моделей эволюции белковых последовательностей.

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

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

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

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

Доступно несколько программ, в которых реализованы варианты методов на основе СММ и которые отличаются своей масштабируемостью и эффективностью, хотя правильное использование метода СММ является более сложным, чем использование более распространенных прогрессивных методов. Самым простым является выравнивание частичного порядка (POA). и аналогичный более общий метод реализован в пакете программного обеспечения Sequence Alignment and Modeling System (SAM). и ХММЕР . SAM использовался в качестве источника выравниваний для предсказания структуры белков для участия в эксперименте по предсказанию структуры CASP и для разработки базы данных предсказанных белков в дрожжей видах S. cerevisiae . HHпоиск представляет собой пакет программного обеспечения для обнаружения отдаленно родственных белковых последовательностей на основе парного сравнения HMM. Сервер, на котором работал HHsearch ( HHpred ), был самым быстрым из 10 серверов автоматического предсказания структуры в соревнованиях по предсказанию структуры CASP7 и CASP8.

Методы, учитывающие филогению

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

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

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

Поиск мотива

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

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

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

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

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

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

Оптимизация

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

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

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

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

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

Моделирование квантовых вычислений

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

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

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

Однако по мере увеличения количества последовательностей, особенно в полногеномных исследованиях, в которых участвует множество MSA, невозможно вручную контролировать все выравнивания. Кроме того, ручное курирование является субъективным. И, наконец, даже самый лучший эксперт не может с уверенностью согласовать наиболее неоднозначные случаи сильно расходящихся последовательностей. В таких случаях общепринятой практикой является использование автоматических процедур для исключения ненадежно выровненных регионов из MSA. С целью реконструкции филогении (см. ниже) широко используется программа Gblocks для удаления блоков выравнивания, подозрительных на низкое качество, по различным ограничениям по количеству пропущенных последовательностей в столбцах выравнивания. Однако эти критерии могут чрезмерно отфильтровывать области с событиями вставки/удаления, которые все еще могут быть надежно выровнены, и эти области могут быть желательны для других целей, таких как обнаружение положительного отбора. Некоторые алгоритмы выравнивания выдают оценки для конкретного сайта, которые позволяют выбирать регионы с высокой степенью достоверности. Впервые такая услуга была предложена программой SOAP. который проверяет устойчивость каждого столбца к изменениям параметров популярной программы выравнивания CLUSTALW. Программа «Т-Кофе» использует библиотеку выравниваний при построении окончательного MSA, а его выходной MSA окрашивается в соответствии с показателями достоверности, которые отражают согласие между различными выравниваниями в библиотеке относительно каждого выровненного остатка. Его расширение, TCS ( Consistency S Transitive core ), использует библиотеки парного выравнивания T -Coffee для оценки любого стороннего MSA. Парные проекции можно создавать с использованием быстрых или медленных методов, что позволяет найти компромисс между скоростью и точностью. Другая программа выравнивания, которая может выводить MSA с оценками достоверности, — это FSA. который использует статистическую модель, позволяющую рассчитать неопределенность выравнивания. Показатель HoT (Орел-или-Решка) может использоваться как мера неопределенности выравнивания для конкретного участка из-за существования множества сооптимальных решений. Программа РУКОВОДСТВО вычисляет аналогичную меру достоверности для конкретного участка на основе устойчивости выравнивания к неопределенности в направляющем дереве, которое используется в программах постепенного выравнивания. Альтернативным, более статистически обоснованным подходом к оценке неопределенности выравнивания является использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. Байесовский подход позволяет рассчитать апостериорные вероятности предполагаемой филогении и выравнивания, что является мерой достоверности этих оценок. В этом случае апостериорную вероятность можно рассчитать для каждого участка выравнивания. Такой подход был реализован в программе BAli-Phy.

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

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

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

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

См. также

• Анализ последовательности без выравнивания
• кладистика
• Обобщенное выравнивание дерева
• Несколько программ просмотра выравнивания последовательностей
• PANDIT , биологическая база данных, охватывающая белковые домены.
• Филогенетика
• Программное обеспечение для выравнивания последовательностей
• Структурное выравнивание

Ссылки

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

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

Внешние ссылки

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

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

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