stringtranslate.com

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

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

Множественное выравнивание последовательностей ( 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] [14] ClustalW широко используется для построения филогенетических деревьев, несмотря на явные предупреждения автора о том, что неотредактированные выравнивания не следует использовать в таких исследованиях, а также в качестве входных данных для прогнозирования структуры белка путем моделирования гомологии. EMBL-EBI объявила, что срок действия CLustalW2 истекает в августе 2015 года. Они рекомендуют Clustal Omega, который работает на основе засеянных направляющих деревьев и методов профиля-профиля HMM для выравнивания белков. Альтернативным инструментом для прогрессивного выравнивания ДНК является 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]

Доступно несколько программ, в которых реализованы варианты методов на основе СММ и которые отличаются своей масштабируемостью и эффективностью, хотя правильное использование метода СММ является более сложным, чем использование более распространенных прогрессивных методов. Самым простым является выравнивание частичного порядка (POA) [24] , аналогичный более общий метод реализован в пакете программного обеспечения Sequence Alignment and Modeling System (SAM). [25] и ХММЕР . [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.

Поиск мотива

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. ^ Томпсон Дж.Д., Линард Б., Лекомпт О., Поч О. (2011). «Комплексное сравнительное исследование нескольких методов выравнивания последовательностей: текущие проблемы и будущие перспективы». ПЛОС ОДИН . 6 (3): e18093. Бибкод : 2011PLoSO...618093T. дои : 10.1371/journal.pone.0018093 . ПМК  3069049 . ПМИД  21483869.
  2. ^ Аб Нуин П.А., Ван З., Тилье Э.Р. (2006). «Точность нескольких программ множественного выравнивания последовательностей белков». БМК Биоинформатика . 7 : 471. дои : 10.1186/1471-2105-7-471 . ПМЦ 1633746 . ПМИД  17062146. 
  3. ^ abc Hosseininasab A, van Hoeve WJ (2019). «Точное множественное выравнивание последовательностей с помощью синхронизированных диаграмм принятия решений». ИНФОРМС Журнал по вычислительной технике . дои : 10.1287/ijoc.2019.0937. S2CID  109937203.
  4. ^ «Помощь с матрицами, используемыми в инструментах сравнения последовательностей» . Европейский институт биоинформатики. Архивировано из оригинала 11 марта 2010 года . Проверено 3 марта 2010 г.
  5. ^ Ван Л, Цзян Т (1994). «О сложности множественного выравнивания последовательностей». J Компьютерная Биол . 1 (4): 337–348. CiteSeerX 10.1.1.408.894 . дои : 10.1089/cmb.1994.1.337. ПМИД  8790475. 
  6. ^ Просто W (2001). «Вычислительная сложность множественного выравнивания последовательностей с помощью SP-показателя». J Компьютерная Биол . 8 (6): 615–23. CiteSeerX 10.1.1.31.6382 . дои : 10.1089/106652701753307511. ПМИД  11747615. 
  7. ^ Элиас, Исаак (2006). «Урегулирование трудноразрешимости множественного выравнивания». J Компьютерная Биол . 13 (7): 1323–1339. CiteSeerX 10.1.1.6.256 . дои : 10.1089/cmb.2006.13.1323. ПМИД  17037961. 
  8. ^ Каррильо Х, ди-джей Липман (1988). «Проблема множественного выравнивания последовательностей в биологии». SIAM Journal по прикладной математике . 48 (5): 1073–1082. дои : 10.1137/0148063.
  9. ^ Липман DJ, Альтшул С.Ф., Кечечиоглу JD (1989). «Инструмент для множественного выравнивания последовательностей». Proc Natl Acad Sci США . 86 (12): 4412–4415. Бибкод : 1989PNAS...86.4412L. дои : 10.1073/pnas.86.12.4412 . ПМЦ 287279 . ПМИД  2734293. 
  10. ^ «Программное обеспечение для генетического анализа» . Национальный центр биотехнологической информации . Проверено 3 марта 2010 г.
  11. ^ Фэн Д.Ф., Дулитл РФ (1987). «Прогрессивное выравнивание последовательностей как необходимое условие исправления филогенетических деревьев». Джей Мол Эвол . 25 (4): 351–360. Бибкод : 1987JMolE..25..351F. дои : 10.1007/BF02603120. PMID  3118049. S2CID  6345432.
  12. ^ abcdefgh Гора DM. (2004). Биоинформатика: анализ последовательностей и генома 2-е изд. Лабораторное издательство Колд-Спринг-Харбор: Колд-Спринг-Харбор, Нью-Йорк.
  13. ^ Хиггинс Д.Г. , Sharp PM (1988). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–244. дои : 10.1016/0378-1119(88)90330-7. ПМИД  3243435.
  14. ^ Томпсон Дж.Д., Хиггинс Д.Г., Гибсон Т.Дж. (ноябрь 1994 г.). «CLUSTAL W: повышение чувствительности прогрессивного множественного выравнивания последовательностей за счет взвешивания последовательностей, штрафов за пробелы для конкретной позиции и выбора весовой матрицы». Нуклеиновые кислоты Рез . 22 (22): 4673–80. дои : 10.1093/нар/22.22.4673. ПМЦ 308517 . ПМИД  7984417. 
  15. ^ «EMBL-EBI-ClustalW2-Выравнивание нескольких последовательностей» . CLUSTALW2 .
  16. ^ Нотредам С., Хиггинс Д.Г., Херинга Дж. (сентябрь 2000 г.). «T-Coffee: новый метод быстрого и точного выравнивания множественных последовательностей». Дж. Мол. Биол . 302 (1): 205–17. дои : 10.1006/jmbi.2000.4042. PMID  10964570. S2CID  10189971.
  17. ^ Сзе Ш, Лу Ю, Ян Ц (2006). «Формулировка множественного выравнивания последовательностей, разрешимая за полиномиальное время». J Компьютерная Биол . 13 (2): 309–319. дои : 10.1089/cmb.2006.13.309. ПМИД  16597242.
  18. ^ Хиросава М, Тотоки Ю, Хосида М, Исикава М (1995). «Комплексное исследование итерационных алгоритмов множественного выравнивания последовательностей». Компьютерные приложения и биологические науки . 11 (1): 13–18. doi : 10.1093/биоинформатика/11.1.13. ПМИД  7796270.
  19. ^ Гото О (1996). «Значительное улучшение точности выравнивания нескольких белковых последовательностей за счет итеративного уточнения, оцениваемого со ссылкой на структурное выравнивание». Дж Мол Биол . 264 (4): 823–38. дои : 10.1006/jmbi.1996.0679. ПМИД  8980688.
  20. ^ аб Брудно М., Чепмен М., Геттгенс Б., Бацоглу С., Моргенштерн Б. (декабрь 2003 г.). «Быстрое и чувствительное множественное выравнивание больших геномных последовательностей». БМК Биоинформатика . 4:66 . дои : 10.1186/1471-2105-4-66 . ПМК 521198 . ПМИД  14693042. 
  21. ^ Эдгар RC (2004). «MUSCLE: множественное выравнивание последовательностей с высокой точностью и высокой пропускной способностью». Исследования нуклеиновых кислот . 32 (5): 1792–97. дои : 10.1093/nar/gkh340. ПМК 390337 . ПМИД  15034147. 
  22. ^ Коллингридж П.В., Келли С. (2012). «MergeAlign: улучшение производительности множественного выравнивания последовательностей за счет динамической реконструкции консенсусного множественного выравнивания последовательностей». БМК Биоинформатика . 13 (117): 117. дои : 10.1186/1471-2105-13-117 . ПМЦ 3413523 . ПМИД  22646090. 
  23. ^ Хьюи Р., Крог А. (1996). «Скрытые марковские модели для анализа последовательностей: расширение и анализ основного метода». КАБИОС . 12 (2): 95–107. CiteSeerX 10.1.1.44.3365 . doi : 10.1093/биоинформатика/12.2.95. ПМИД  8744772. 
  24. ^ Грассо С., Ли С. (2004). «Сочетание выравнивания частичного порядка и прогрессивного выравнивания множественных последовательностей увеличивает скорость выравнивания и масштабируемость для решения очень серьезных задач выравнивания». Биоинформатика . 20 (10): 1546–56. doi : 10.1093/биоинформатика/bth126 . ПМИД  14962922.
  25. ^ Хьюи Р., Крог А. СЭМ: Программная система выравнивания последовательностей и моделирования. Технический отчет 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 . doi : 10.1093/биоинформатика/bti125. ПМИД  15531603. 
  28. ^ Бэтти Дж. Н., Копп Дж., Бордоли Л., Рид Р. Дж., Кларк Н. Д., Шведе Т. (2007). «Автоматические прогнозы сервера в CASP7». Белки . 69 (Приложение 8): 68–82. дои : 10.1002/прот.21761 . PMID  17894354. S2CID  29879391.
  29. ^ Лойтыноя, А. (2005). «Алгоритм прогрессивного множественного выравнивания последовательностей со вставками». Труды Национальной академии наук . 102 (30): 10557–10562. Бибкод : 2005PNAS..10210557L. дои : 10.1073/pnas.0409137102 . ПМЦ 1180752 . ПМИД  16000407. 
  30. ^ Лойтыноя А, Гольдман Н (июнь 2008 г.). «Размещение пробелов с учетом филогении предотвращает ошибки в выравнивании последовательностей и эволюционном анализе». Наука . 320 (5883): 1632–5. Бибкод : 2008Sci...320.1632L. дои : 10.1126/science.1158395. PMID  18566285. S2CID  5211928.
  31. ^ Лойтыноя А, Вилелла А.Дж., Голдман Н. (июль 2012 г.). «Точное расширение множественных выравниваний последовательностей с использованием графового алгоритма, учитывающего филогению». Биоинформатика . 28 (13): 1684–91. doi : 10.1093/биоинформатика/bts198. ПМК 3381962 . ПМИД  22531217. 
  32. ^ Шалковский А.М. (июнь 2012 г.). «Быстрое и надежное выравнивание множественных последовательностей с размещением пробелов с учетом филогении». БМК Биоинформатика . 13 :129. дои : 10.1186/1471-2105-13-129 . ПМЦ 3495709 . ПМИД  22694311. 
  33. ^ Хеникофф С., Хеникофф Дж.Г. (декабрь 1991 г.). «Автоматическая сборка белковых блоков для поиска в базе данных». Нуклеиновые кислоты Рез . 19 (23): 6565–72. дои : 10.1093/нар/19.23.6565. ПМК 329220 . ПМИД  1754394. 
  34. ^ Бэйли Т.Л., Элкан С. (1994). «Подбор модели смеси путем максимизации ожидания для обнаружения мотивов в биополимерах» (PDF) . Материалы второй международной конференции по интеллектуальным системам молекулярной биологии . Менло-Парк, Калифорния: AAAI Press. стр. 28–36.
  35. ^ Бэйли Т.Л., Грибсков М. (1998). «Объединение доказательств с использованием p-значений: применение для поиска гомологии последовательностей». Биоинформатика . 14 (1): 48–54. дои : 10.1093/биоинформатика/14.1.48 . ПМИД  9520501.
  36. ^ Салама Р.А., Stekel DJ (ноябрь 2013 г.). «Независимое выравнивание множественных последовательностей на основе энергии улучшает предсказание сайтов связывания транскрипционных факторов». Биоинформатика . 29 (21): 2699–704. doi : 10.1093/биоинформатика/btt463 . ПМИД  23990411.
  37. ^ Нотредам С., Хиггинс Д.Г. (апрель 1996 г.). «SAGA: выравнивание последовательностей с помощью генетического алгоритма». Нуклеиновые кислоты Рез . 24 (8): 1515–24. дои : 10.1093/нар/24.8.1515. ПМЦ 145823 . ПМИД  8628686. 
  38. ^ Нотредам С., О'Брайен Э.А., Хиггинс Д.Г. (1997). «RAGA: выравнивание последовательности РНК с помощью генетического алгоритма». Нуклеиновые кислоты Рез . 25 (22): 4570–80. дои : 10.1093/нар/25.22.4570. ПМК 147093 . ПМИД  9358168. 
  39. ^ Ким Дж., Праманик С., Чунг М.Дж. (1994). «Множественное выравнивание последовательностей с использованием имитации отжига». Компьютерные приложения и биологические науки . 10 (4): 419–26. doi : 10.1093/биоинформатика/10.4.419. ПМИД  7804875.
  40. ^ Альтхаус Э., Капрара А., Ленхоф Х.П., Райнерт К. (2006). «Алгоритм ветвей и разрезов для множественного выравнивания последовательностей». Математическое программирование . 105 (2–3): 387–425. дои : 10.1007/s10107-005-0659-3. S2CID  17715172.
  41. ^ D-Wave запускает открытую квантовую программную среду, 11 января 2017 г.
  42. ^ «Ручное редактирование и настройка MSA». Европейская лаборатория молекулярной биологии. 2007. Архивировано из оригинала 24 сентября 2015 года . Проверено 7 марта 2010 г.
  43. ^ Кастресана Дж (апрель 2000 г.). «Отбор консервативных блоков из нескольких выравниваний для их использования в филогенетическом анализе». Мол. Биол. Эвол . 17 (4): 540–52. doi : 10.1093/oxfordjournals.molbev.a026334 . ПМИД  10742046.
  44. ^ Лойтыноя А, Милинкович MC (июнь 2001 г.). «SOAP, очистка множественных выравниваний от нестабильных блоков». Биоинформатика . 17 (6): 573–4. дои : 10.1093/биоинформатика/17.6.573 . ПМИД  11395440.
  45. ^ Пуаро О, О'Тул Э, Нотредам С (июль 2003 г.). «Tcoffee@igs: веб-сервер для вычислений, оценки и объединения нескольких выравниваний последовательностей». Нуклеиновые кислоты Рез . 31 (13): 3503–6. дои : 10.1093/nar/gkg522. ПМК 168929 . ПМИД  12824354. 
  46. ^ Чанг, Дж. М.; Ди Томмазо, П; Нотредам, К. (июнь 2014 г.). «TCS: новый показатель надежности множественного выравнивания последовательностей для оценки точности выравнивания и улучшения реконструкции филогенетического дерева». Молекулярная биология и эволюция . 31 (6): 1625–37. дои : 10.1093/molbev/msu117 . ПМИД  24694831.
  47. ^ Чанг Дж. М., Ди Томмазо П., Лефорт В., Гаскуэль О., Нотредам С. (июль 2015 г.). «TCS: веб-сервер для оценки множественного выравнивания последовательностей и филогенетической реконструкции». Нуклеиновые кислоты Рез . 43 (П1): П3–6. дои : 10.1093/nar/gkv310. ПМЦ 4489230 . ПМИД  25855806. 
  48. ^ Брэдли РК, Робертс А, Смут М, Ювекар С, До Дж, Дьюи С, Холмс I, Пахтер Л (май 2009 г.). «Быстрое статистическое выравнивание». ПЛОС Компьютер. Биол . 5 (5): e1000392. Бибкод : 2009PLSCB...5E0392B. дои : 10.1371/journal.pcbi.1000392 . ПМЦ 2684580 . ПМИД  19478997. 
  49. ^ Ландан Г., Граур Д. (2008). «Меры локальной надежности на основе наборов кооптимальных множественных выравниваний последовательностей». Биокомпьютинг 2008 . стр. 15–24. дои : 10.1142/9789812776136_0003. ISBN 978-981-277-608-2. ПМИД  18229673. {{cite book}}: |journal=игнорируется ( помощь )
  50. ^ Пенн О, Привман Э, Ландан Г, Граур Д, Пупко Т (август 2010 г.). «Оценка достоверности выравнивания, отражающая надежность для определения неопределенности дерева». Мол. Биол. Эвол . 27 (8): 1759–67. doi : 10.1093/molbev/msq066. ПМЦ 2908709 . ПМИД  20207713. 
  51. ^ Ределингс Б.Д., Сушард М.А. (июнь 2005 г.). «Совместная байесовская оценка выравнивания и филогении». Сист. Биол . 54 (3): 401–18. дои : 10.1080/10635150590947041 . ПМИД  16012107.
  52. ^ Аб Бадд, Эйдан (10 февраля 2009 г.). «Множественные упражнения и демонстрации по выравниванию последовательностей». Европейская лаборатория молекулярной биологии. Архивировано из оригинала 5 марта 2012 года . Проверено 30 июня 2010 г.

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

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

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