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

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

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

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

СОДЕРЖАНИЕ

  • 1 Описание проблемы
  • 2 Графический подход
    • 2.1 Отслеживание выравнивания
  • 3 Методы центровки
    • 3.1 Динамическое программирование
    • 3.2 Построение прогрессивной центровки
    • 3.3 Итерационные методы
    • 3.4 Методы консенсуса
    • 3.5 Скрытые марковские модели
    • 3.6 Филогенетические методы
    • 3.7 Поиск мотивов
    • 3.8 Некодирующее выравнивание множественных последовательностей
  • 4 Оптимизация
    • 4.1 Генетические алгоритмы и имитация отжига
    • 4.2 Математическое программирование и алгоритмы точного решения
    • 4.3 Моделирование квантовых вычислений
  • 5 Визуализация юстировки и контроль качества
  • 6 Филогенетическое использование
  • 7 См. Также
  • 8 ссылки
    • 8.1 Обзорные статьи
  • 9 Внешние ссылки
    • 9.1 Конспекты лекций, учебные пособия и курсы

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

Заданные последовательности, похожие на форму ниже: м {\ displaystyle m} S я {\ displaystyle S_ {i}} я знак равно 1 , , м {\ Displaystyle я = 1, \ cdots, м}

S знак равно { S 1 знак равно ( S 11 , S 12 , , S 1 п 1 ) S 2 знак равно ( S 21 год , S 22 , , S 2 п 2 ) S м знак равно ( S м 1 , S м 2 , , S м п м ) {\ displaystyle 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 {case}}}

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

S знак равно { S 1 знак равно ( S 11 , S 12 , , S 1 L ) S 2 знак равно ( S 21 год , S 22 , , S 2 L ) S м знак равно ( S м 1 , S м 2 , , S м L ) {\ displaystyle S ': = {\ begin {case} 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 {case}}}

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы прогрессивного выравнивания достаточно эффективны для крупномасштабной реализации многих (от 100 до 1000) последовательностей. Услуги прогрессивного выравнивания обычно доступны на общедоступных веб-серверах, поэтому пользователям не нужно локально устанавливать интересующие их приложения. Самым популярным методом прогрессивного выравнивания было семейство Clustal, особенно взвешенный вариант ClustalW, доступ к которому предоставляется через большое количество веб-порталов, включая GenomeNet, EBI и EMBNet. Различные порталы или реализации могут различаться по пользовательскому интерфейсу и делать разные параметры доступными для пользователя. ClustalW широко используется для построения филогенетического дерева, несмотря на явные предупреждения автора о том, что неотредактированные сопоставления не должны использоваться в таких исследованиях и в качестве входных данных для предсказания структуры белка путем моделирования гомологии. Текущая версия семейства Clustal - ClustalW2. EMBL-EBI объявила, что CLustalW2 истечет в августе 2015 года. Они рекомендуют Clustal Omega, который работает на основе засеянных направляющих деревьев и методов профиля-профиля HMM для выравнивания белков. Они предлагают различные инструменты MSA для прогрессивного выравнивания ДНК. Один из них - 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. Это отличается от методов прогрессивного выравнивания, поскольку выравнивание предыдущих последовательностей обновляется при каждом добавлении новой последовательности. Однако, как и в случае прогрессивных методов, на этот метод может влиять порядок, в котором последовательности в наборе запроса интегрируются в выравнивание, особенно когда последовательности имеют отдаленное родство.

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

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

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

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

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

Поиск мотива

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

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

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

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

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

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

Оптимизация

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

Стандартные методы оптимизации в информатике - оба из которых были вдохновлены физическими процессами, но не воспроизводят их напрямую - также использовались в попытке более эффективно производить качественные 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. Программа T-Coffee использует библиотеку выравниваний при построении окончательного MSA, и ее выходной MSA окрашен в соответствии с оценками достоверности, которые отражают согласие между различными выравниваниями в библиотеке относительно каждого выровненного остатка. Его расширение, TCS  : ( ядро T ransitive C onsistency S), использует библиотеки попарного выравнивания T-Coffee для оценки любых сторонних MSA. Парные прогнозы могут быть произведены с использованием быстрых или медленных методов, что позволяет найти компромисс между скоростью и точностью. Другой программой выравнивания, которая может выводить MSA с оценками достоверности, является FSA, в которой используется статистическая модель, позволяющая рассчитать неопределенность при выравнивании. Оценка HoT («головы или хвосты») может использоваться в качестве меры неопределенности согласования для конкретного участка из-за наличия нескольких совместно оптимальных решений. Программа GUIDANCE вычисляет аналогичный показатель достоверности для конкретного участка на основе устойчивости выравнивания к неопределенности в дереве направляющих, которое используется в программах прогрессивного выравнивания. Альтернативный, более статистически обоснованный подход к оценке неопределенности выравнивания - это использование вероятностных эволюционных моделей для совместной оценки филогении и выравнивания. Байесовский подход позволяет рассчитать апостериорные вероятности предполагаемой филогении и выравнивания, что является мерой уверенности в этих оценках. В этом случае для каждого участка трассы можно рассчитать апостериорную вероятность. Такой подход реализован в программе BAli-Phy.

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

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

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

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

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

использованная литература

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

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

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

Последняя правка сделана 2023-03-20 02:05:18
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте