stringtranslate.com

Выравнивание последовательности

В биоинформатике выравнивание последовательностей — это способ упорядочивания последовательностей ДНК , РНК или белка для выявления областей сходства, которые могут быть следствием функциональных, структурных или эволюционных связей между последовательностями. [1] Выровненные последовательности нуклеотидных или аминокислотных остатков обычно представляются в виде строк в матрице . Пробелы вставляются между остатками так, чтобы идентичные или похожие символы были выровнены в последовательных столбцах. Выравнивание последовательностей также используется для небиологических последовательностей, таких как расчет стоимости расстояния между строками на естественном языке или для отображения финансовых данных.

Выравнивание последовательностей, произведенное ClustalO , гистоновых белков млекопитающих .
Последовательности представляют собой аминокислоты для остатков 120-180 белков. Остатки, которые сохраняются во всех последовательностях, выделены серым цветом. Под последовательностями белков находится ключ, обозначающий консервативную последовательность (*), консервативные мутации (:), полуконсервативные мутации (.) и неконсервативные мутации ( ). [2]

Интерпретация

Если две последовательности в выравнивании имеют общего предка, несовпадения можно интерпретировать как точечные мутации , а пробелы как индели (то есть мутации вставки или делеции), введенные в одну или обе линии с тех пор, как они разошлись друг от друга. При выравнивании последовательностей белков степень сходства между аминокислотами , занимающими определенное положение в последовательности, можно интерпретировать как грубую меру того, насколько консервативен определенный регион или мотив последовательности среди линий. Отсутствие замен или наличие только очень консервативных замен (то есть замены аминокислот, боковые цепи которых имеют схожие биохимические свойства) в определенном регионе последовательности предполагает [3] , что этот регион имеет структурное или функциональное значение. Хотя нуклеотидные основания ДНК и РНК более похожи друг на друга, чем аминокислоты, сохранение пар оснований может указывать на схожую функциональную или структурную роль.

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

Очень короткие или очень похожие последовательности можно выровнять вручную. Однако для решения самых интересных задач требуется выравнивание длинных, сильно изменчивых или чрезвычайно многочисленных последовательностей, которые невозможно выровнять исключительно человеческими усилиями. Вместо этого человеческие знания применяются при построении алгоритмов для получения высококачественных выравниваний последовательностей, а иногда и при корректировке конечных результатов для отражения шаблонов, которые трудно представить алгоритмически (особенно в случае нуклеотидных последовательностей). Вычислительные подходы к выравниванию последовательностей обычно делятся на две категории: глобальные выравнивания и локальные выравнивания . Вычисление глобального выравнивания является формой глобальной оптимизации, которая «заставляет» выравнивание охватывать всю длину всех последовательностей запроса. Напротив, локальные выравнивания выявляют области сходства в длинных последовательностях, которые часто сильно расходятся в целом. Локальные выравнивания часто предпочтительнее, но их может быть сложнее вычислить из-за дополнительной проблемы определения областей сходства. [4] К проблеме выравнивания последовательностей применялись различные вычислительные алгоритмы. К ним относятся медленные, но формально правильные методы, такие как динамическое программирование . К ним также относятся эффективные эвристические алгоритмы или вероятностные методы, разработанные для крупномасштабного поиска в базах данных, которые не гарантируют нахождения наилучших совпадений.

Представления

Выравнивания обычно представляются как в графическом, так и в текстовом формате. Почти во всех представлениях выравнивания последовательностей последовательности записываются в строках, расположенных таким образом, что выровненные остатки появляются в последовательных столбцах. В текстовых форматах выровненные столбцы, содержащие идентичные или похожие символы, обозначаются системой символов консервации. Как на изображении выше, символ звездочки или вертикальной черты используется для обозначения идентичности между двумя столбцами; другие менее распространенные символы включают двоеточие для консервативных замен и точку для полуконсервативных замен. Многие программы визуализации последовательностей также используют цвет для отображения информации о свойствах отдельных элементов последовательности; в последовательностях ДНК и РНК это равнозначно назначению каждому нуклеотиду собственного цвета. В выравниваниях белков, таких как на изображении выше, цвет часто используется для обозначения свойств аминокислот, чтобы помочь в оценке консервативности данной замены аминокислоты. Для нескольких последовательностей последняя строка в каждом столбце часто является консенсусной последовательностью, определенной выравниванием; консенсусная последовательность также часто представлена ​​в графическом формате с логотипом последовательности , в котором размер каждой буквы нуклеотида или аминокислоты соответствует степени ее консервативности. [5]

Выравнивания последовательностей могут храниться в самых разных текстовых форматах файлов, многие из которых изначально были разработаны совместно с определенной программой или реализацией выравнивания. Большинство веб-инструментов допускают ограниченное количество форматов ввода и вывода, таких как формат FASTA и формат GenBank , а вывод нелегко редактировать. Доступно несколько программ преобразования, которые предоставляют графический интерфейс и/или интерфейс командной строки [ нерабочая ссылка ] , таких как READSEQ и EMBOSS . Существует также несколько пакетов программирования, которые предоставляют эту функциональность преобразования, таких как BioPython , BioRuby и BioPerl . Файлы SAM/BAM используют формат строки CIGAR (Compact Idiosyncratic Gapped Alignment Report) для представления выравнивания последовательности с эталоном путем кодирования последовательности событий (например, совпадений/несовпадений, вставок, удалений). [6]

Формат СИГАРЫ

Ссылка: GTCGTAGAATA
Прочтите : CACGTAG—TA
CIGAR: 2S5M2D2M, где:
2S = 2 мягких отсечения (могут быть несовпадения или чтение длиннее, чем совпавшая последовательность)
5M = 5 совпадений или несовпадений
2D = 2 удаления
2M = 2 совпадения или несовпадения

Первоначальный формат CIGAR из программы выравнивания exonerate не различал несовпадения или совпадения с символом M.

Документ спецификации SAMv1 определяет новые коды CIGAR. В большинстве случаев для обозначения совпадений или несовпадений предпочтительнее использовать символы '=' и 'X', а не старый символ 'M', который неоднозначен.

Глобальные и локальные выравнивания

Глобальные выравнивания, которые пытаются выровнять каждый остаток в каждой последовательности, наиболее полезны, когда последовательности в наборе запроса похожи и примерно одинакового размера. (Это не означает, что глобальные выравнивания не могут начинаться и/или заканчиваться пробелами.) Общий метод глобального выравнивания — это алгоритм Нидлмана-Вунша , который основан на динамическом программировании. Локальные выравнивания более полезны для разнородных последовательностей, которые предположительно содержат области сходства или похожие мотивы последовательностей в их более широком контексте последовательности. Алгоритм Смита-Уотермана — это общий метод локального выравнивания, основанный на той же схеме динамического программирования, но с дополнительными вариантами начала и окончания в любом месте. [4]

Гибридные методы, известные как полуглобальные или «глокальные» (сокращенно от glob bal-local ) методы, ищут наилучшее возможное частичное выравнивание двух последовательностей (другими словами, комбинация одного или обоих начал и одного или обоих концов, как утверждается, выровнена). Это может быть особенно полезно, когда нисходящая часть одной последовательности перекрывается с восходящей частью другой последовательности. В этом случае ни глобальное, ни локальное выравнивание не являются полностью подходящими: глобальное выравнивание попытается заставить выравнивание выйти за пределы области перекрытия, в то время как локальное выравнивание может не полностью покрывать область перекрытия. [7] Другой случай, когда полуглобальное выравнивание полезно, — это когда одна последовательность короткая (например, последовательность гена), а другая очень длинная (например, последовательность хромосомы). В этом случае короткая последовательность должна быть глобально (полностью) выровнена, но для длинной последовательности желательно только локальное (частичное) выравнивание.

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

Парное выравнивание

Методы парного выравнивания последовательностей используются для поиска наиболее соответствующих кусочных (локальных или глобальных) выравниваний двух последовательностей запроса. Парные выравнивания могут использоваться только между двумя последовательностями одновременно, но они эффективны для вычисления и часто используются для методов, которые не требуют чрезвычайной точности (например, поиска в базе данных последовательностей с высоким сходством с запросом). Три основных метода создания парных выравниваний — это методы точечной матрицы, динамическое программирование и методы слов; [1] однако методы множественного выравнивания последовательностей также могут выравнивать пары последовательностей. Хотя каждый метод имеет свои индивидуальные сильные и слабые стороны, все три парных метода испытывают трудности с сильно повторяющимися последовательностями с низким информационным содержанием — особенно когда количество повторений различается в двух последовательностях, которые нужно выровнять.

Максимальное уникальное совпадение

Одним из способов количественной оценки полезности данного парного выравнивания является « максимальное уникальное совпадение » (MUM) или самая длинная подпоследовательность, которая встречается в обеих последовательностях запроса. Более длинные последовательности MUM обычно отражают более тесное родство. [8] в множественном выравнивании последовательностей геномов в вычислительной биологии . Идентификация MUM и других потенциальных якорей является первым шагом в более крупных системах выравнивания, таких как MUMmer . Якоря — это области между двумя геномами, где они очень похожи. Чтобы понять, что такое MUM, мы можем разбить каждое слово в аббревиатуре. Совпадение подразумевает, что подстрока встречается в обеих последовательностях, которые должны быть выровнены. Уникальный означает, что подстрока встречается только один раз в каждой последовательности. Наконец, максимальный утверждает, что подстрока не является частью другой более крупной строки, которая удовлетворяет обоим предыдущим требованиям. Идея этого заключается в том, что длинные последовательности, которые точно совпадают и встречаются только один раз в каждом геноме, почти наверняка являются частью глобального выравнивания.

Точнее:

«Для двух геномов A и B подстрока максимального уникального совпадения (MUM) — это общая подстрока A и B, длина которой больше указанной минимальной длины d (по умолчанию d = 20), такая, что

Методы точечной матрицы

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

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

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

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

Метод динамического программирования может быть применен для создания глобальных выравниваний с помощью алгоритма Нидлмана-Вунша и локальных выравниваний с помощью алгоритма Смита-Уотермана . В типичном использовании выравнивания белков используют матрицу замещения для назначения оценок совпадениям или несовпадениям аминокислот и штрафа за пропуск за сопоставление аминокислоты в одной последовательности с пропуском в другой. Выравнивания ДНК и РНК могут использовать матрицу подсчета, но на практике часто просто назначают положительную оценку соответствия, отрицательную оценку несовпадения и отрицательный штраф за пропуск. (В стандартном динамическом программировании оценка каждой позиции аминокислоты не зависит от идентичности ее соседей, и поэтому эффекты укладки оснований не учитываются. Однако можно учесть такие эффекты, изменив алгоритм.) [ необходима цитата ] Распространенным расширением стандартных линейных затрат на пропуски являются аффинные затраты на пропуски. Здесь применяются два различных штрафа за пропуски для открытия пропуска и для расширения пропуска. Обычно первый намного больше второго, например -10 для открытия разрыва и -2 для расширения разрыва. Это приводит к меньшему количеству разрывов в выравнивании, а остатки и разрывы сохраняются вместе, что является признаком, более характерным для биологических последовательностей. Алгоритм Gotoh реализует аффинные затраты разрыва, используя три матрицы. [10] [11]

Динамическое программирование может быть полезным при выравнивании нуклеотидов с белковыми последовательностями, задача осложняется необходимостью учитывать мутации сдвига рамки считывания (обычно вставки или делеции). Метод поиска рамки создает ряд глобальных или локальных парных выравниваний между последовательностью нуклеотидов запроса и набором поиска последовательностей белка, или наоборот. Его способность оценивать сдвиги рамки считывания, смещенные на произвольное число нуклеотидов, делает метод полезным для последовательностей, содержащих большое количество инделей, которые может быть очень трудно выровнять более эффективными эвристическими методами. На практике метод требует больших объемов вычислительной мощности или системы, архитектура которой специализирована для динамического программирования. Пакеты BLAST и EMBOSS предоставляют базовые инструменты для создания транслируемых выравниваний (хотя некоторые из этих подходов используют побочные эффекты возможностей поиска последовательностей инструментов). Более общие методы доступны в программном обеспечении с открытым исходным кодом, таком как GeneWise. [ необходима цитата ]

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

Методы слов

Методы слов, также известные как методы k -кортежей, являются эвристическими методами, которые не гарантируют нахождения оптимального решения для выравнивания, но значительно более эффективны, чем динамическое программирование. Эти методы особенно полезны при крупномасштабном поиске в базах данных, где понятно, что большая часть последовательностей-кандидатов не будет иметь существенного соответствия с последовательностью запроса. Методы слов наиболее известны по их реализации в инструментах поиска в базах данных FASTA и семействе BLAST . [1] Методы слов идентифицируют ряд коротких, неперекрывающихся подпоследовательностей («слов») в последовательности запроса, которые затем сопоставляются с последовательностями-кандидатами в базе данных. Относительные положения слова в двух сравниваемых последовательностях вычитаются для получения смещения; это укажет на область выравнивания, если несколько различных слов дают одинаковое смещение. Только если эта область обнаружена, эти методы применяют более чувствительные критерии выравнивания; таким образом, устраняются многие ненужные сравнения с последовательностями, не имеющими заметного сходства.

В методе FASTA пользователь определяет значение k для использования в качестве длины слова, с которой будет выполняться поиск в базе данных. Метод медленнее, но более чувствителен при более низких значениях k , которые также предпочтительны для поиска с использованием очень короткой последовательности запросов. Семейство методов поиска BLAST предоставляет ряд алгоритмов, оптимизированных для определенных типов запросов, таких как поиск отдаленно связанных совпадений последовательностей. BLAST был разработан для предоставления более быстрой альтернативы FASTA без особого ущерба для точности; как и FASTA, BLAST использует поиск слов длиной k , но оценивает только наиболее значимые совпадения слов, а не каждое совпадение слов, как это делает FASTA. Большинство реализаций BLAST используют фиксированную длину слова по умолчанию, которая оптимизирована для запроса и типа базы данных и изменяется только при особых обстоятельствах, например, при поиске с повторяющимися или очень короткими последовательностями запросов. Реализации можно найти на ряде веб-порталов, таких как EMBL FASTA и NCBI BLAST.

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

Выравнивание 27 последовательностей белка гемагглютинина вируса птичьего гриппа, окрашенных по консервации остатков (вверху) и свойствам остатков (внизу)

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

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

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

Прогрессивные методы

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

Многие вариации прогрессивной реализации Clustal [15] [16] [17] используются для множественного выравнивания последовательностей, построения филогенетического дерева и в качестве входных данных для предсказания структуры белка . Более медленный, но более точный вариант прогрессивного метода известен как T-Coffee . [18]

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

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

Поиск мотива

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

Методы, вдохновленные компьютерной наукой

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

Различные общие алгоритмы оптимизации, обычно используемые в информатике, также применялись к проблеме множественного выравнивания последовательностей. Скрытые марковские модели использовались для получения оценок вероятности для семейства возможных множественных выравниваний последовательностей для заданного набора запросов; хотя ранние методы на основе HMM давали неудовлетворительную производительность, более поздние приложения обнаружили, что они особенно эффективны при обнаружении отдаленно связанных последовательностей, поскольку они менее восприимчивы к шуму, создаваемому консервативными или полуконсервативными заменами. [20] Генетические алгоритмы и имитация отжига также использовались для оптимизации оценок множественного выравнивания последовательностей, оцениваемых с помощью функции подсчета, такой как метод суммы пар. Более полную информацию и пакеты программного обеспечения можно найти в основной статье множественное выравнивание последовательностей .

Преобразование Барроуза –Уиллера успешно применялось для быстрого выравнивания коротких прочтений в популярных инструментах, таких как Bowtie и BWA. См. FM-index .

Структурное выравнивание

Структурные выравнивания, которые обычно специфичны для последовательностей белков и иногда РНК, используют информацию о вторичной и третичной структуре молекулы белка или РНК для помощи в выравнивании последовательностей. Эти методы могут использоваться для двух или более последовательностей и обычно производят локальные выравнивания; однако, поскольку они зависят от доступности структурной информации, их можно использовать только для последовательностей, соответствующие структуры которых известны (обычно с помощью рентгеновской кристаллографии или ЯМР-спектроскопии ). Поскольку структура как белка, так и РНК более эволюционно консервативны, чем последовательность, [21] структурные выравнивания могут быть более надежными между последовательностями, которые очень отдаленно связаны и которые разошлись настолько сильно, что сравнение последовательностей не может надежно обнаружить их сходство.

Структурные выравнивания используются в качестве «золотого стандарта» при оценке выравниваний для предсказания структуры белка на основе гомологии [22], поскольку они явно выравнивают области последовательности белка, которые структурно схожи, а не полагаются исключительно на информацию о последовательности. Однако, очевидно, структурные выравнивания не могут использоваться при предсказании структуры, поскольку по крайней мере одна последовательность в наборе запросов является целью для моделирования, для которой структура неизвестна. Было показано, что, учитывая структурное выравнивание между целевой и шаблонной последовательностью, можно получить высокоточные модели целевой последовательности белка; основным камнем преткновения в предсказании структуры на основе гомологии является получение структурно точных выравниваний, учитывая только информацию о последовательности. [22]

ДАЛИ

Метод DALI, или выравнивание матрицы расстояний , представляет собой метод на основе фрагментов для построения структурных выравниваний на основе шаблонов сходства контактов между последовательными гексапептидами в последовательностях запроса. [23] Он может генерировать парные или множественные выравнивания и идентифицировать структурных соседей последовательности запроса в Банке данных белков (PDB). Он использовался для построения базы данных структурных выравниваний FSSP (классификация сгибов на основе выравнивания структуры-структуры белков или семейств структурно подобных белков). Веб-сервер DALI доступен на сайте DALI, а FSSP находится в базе данных Dali.

ССАП

SSAP (программа последовательного выравнивания структур) — это метод структурного выравнивания на основе динамического программирования, который использует атом-атомные векторы в пространстве структур в качестве точек сравнения. Он был расширен с момента своего первоначального описания, чтобы включить множественные, а также попарные выравнивания, [24] и использовался при построении иерархической базы данных классификации складок белков CATH (класс, архитектура, топология, гомология). [25] База данных CATH доступна на сайте CATH Protein Structure Classification.

Комбинаторное расширение

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

Филогенетический анализ

Филогенетика и выравнивание последовательностей являются тесно связанными областями из-за общей необходимости оценки родства последовательностей. [27] Область филогенетики широко использует выравнивания последовательностей при построении и интерпретации филогенетических деревьев , которые используются для классификации эволюционных отношений между гомологичными генами, представленными в геномах расходящихся видов. Степень, в которой последовательности в наборе запроса различаются, качественно связана с эволюционным расстоянием последовательностей друг от друга. Грубо говоря, высокая идентичность последовательностей предполагает, что рассматриваемые последовательности имеют сравнительно молодого последнего общего предка , в то время как низкая идентичность предполагает, что расхождение более древнее. Это приближение, которое отражает гипотезу « молекулярных часов », согласно которой примерно постоянную скорость эволюционных изменений можно использовать для экстраполяции прошедшего времени с момента первого расхождения двух генов (то есть времени слияния ), предполагает, что эффекты мутации и отбора постоянны во всех линиях последовательностей. Следовательно, она не учитывает возможные различия между организмами или видами в скорости восстановления ДНК или возможной функциональной консервации определенных областей в последовательности. (В случае нуклеотидных последовательностей гипотеза молекулярных часов в своей самой базовой форме также не учитывает разницу в скоростях принятия между молчащими мутациями , которые не изменяют значение данного кодона , и другими мутациями, которые приводят к включению другой аминокислоты в белок). Более статистически точные методы позволяют варьировать скорость эволюции на каждой ветви филогенетического дерева, тем самым получая более точные оценки времени слияния генов.

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

Оценка значимости

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

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

Методы оценки статистической значимости для выравниваний последовательностей с пробелами доступны в литературе. [27] [29] [30] [31] [32] [33] [34] [35]

Оценка достоверности

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

Функции подсчета очков

Выбор функции оценки, которая отражает биологические или статистические наблюдения об известных последовательностях, важен для получения хороших выравниваний. Последовательности белков часто выравниваются с использованием матриц замен , которые отражают вероятности заданных замен символа на символ. Серия матриц, называемых матрицами PAM (матрицы точечных принятых мутаций, первоначально определенные Маргарет Дейхофф и иногда называемые «матрицами Дейхофф»), явно кодирует эволюционные приближения относительно скоростей и вероятностей определенных мутаций аминокислот. Другая распространенная серия матриц оценки, известная как BLOSUM (матрица блочной замены), кодирует эмпирически полученные вероятности замен. Варианты обоих типов матриц используются для обнаружения последовательностей с различными уровнями расхождения, что позволяет пользователям BLAST или FASTA ограничивать поиск более тесно связанными совпадениями или расширять для обнаружения более расходящихся последовательностей. Штрафы за пробелы учитывают введение пробела - в эволюционной модели, мутацию вставки или делеции - как в нуклеотидных, так и в белковых последовательностях, и поэтому штрафные значения должны быть пропорциональны ожидаемой скорости таких мутаций. Качество полученных выравниваний, таким образом, зависит от качества функции подсчета.

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

Другие биологические применения

Секвенированные РНК, такие как экспрессированные метки последовательности и полноразмерные мРНК, могут быть выровнены с секвенированным геномом, чтобы найти, где находятся гены, и получить информацию об альтернативном сплайсинге [37] и редактировании РНК . [38] Выравнивание последовательностей также является частью сборки генома , где последовательности выравниваются для нахождения перекрытия, чтобы можно было сформировать контиги (длинные участки последовательности). [39] Другим применением является анализ однонуклеотидных полиморфизмов , где последовательности от разных людей выравниваются для нахождения отдельных пар оснований, которые часто различаются в популяции. [40]

Небиологическое использование

Методы, используемые для биологического выравнивания последовательностей, также нашли применение в других областях, в частности, в обработке естественного языка и в социальных науках , где алгоритм Нидлмана-Вунша обычно называют оптимальным соответствием . [41] Методы, которые генерируют набор элементов, из которых будут выбираться слова в алгоритмах генерации естественного языка , заимствовали методы множественного выравнивания последовательностей из биоинформатики для создания лингвистических версий математических доказательств, сгенерированных компьютером . [42] В области исторической и сравнительной лингвистики выравнивание последовательностей использовалось для частичной автоматизации сравнительного метода, с помощью которого лингвисты традиционно реконструируют языки. [43] Бизнес- и маркетинговые исследования также применяли методы множественного выравнивания последовательностей при анализе серий покупок с течением времени. [44]

Программное обеспечение

Более полный список доступного программного обеспечения, классифицированного по алгоритму и типу выравнивания, доступен на сайте sequence alignment software , но распространенные программные инструменты, используемые для общих задач выравнивания последовательностей, включают ClustalW2 [45] и T-coffee [46] для выравнивания, а также BLAST [47] и FASTA3x [48] для поиска в базе данных. Также доступны коммерческие инструменты, такие как DNASTAR Lasergene, Geneious и PatternHunter . Инструменты, аннотированные как выполняющие выравнивание последовательностей, перечислены в реестре bio.tools.

Алгоритмы и программное обеспечение для выравнивания можно напрямую сравнивать друг с другом, используя стандартизированный набор эталонных множественных выравниваний последовательностей, известный как BAliBASE. [49] Набор данных состоит из структурных выравниваний, которые можно считать стандартом, с которым сравниваются чисто основанные на последовательностях методы. Относительная производительность многих распространенных методов выравнивания при часто встречающихся проблемах выравнивания была сведена в таблицу, а выбранные результаты опубликованы онлайн на BAliBASE. [50] [51] Полный список оценок BAliBASE для многих (в настоящее время 12) различных инструментов выравнивания можно вычислить в рабочей среде STRAP для белков. [52]

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

Ссылки

  1. ^ abc Mount DM. (2004). Биоинформатика: Анализ последовательностей и генома (2-е изд.). Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY. ISBN 978-0-87969-608-5.
  2. ^ "Clustal FAQ #Symbols". Clustal . Архивировано из оригинала 24 октября 2016 года . Получено 8 декабря 2014 года .
  3. ^ Ng PC; Henikoff S (май 2001). «Предсказание вредных замен аминокислот». Genome Res . 11 (5): 863–74. doi : 10.1101/gr.176601. PMC 311071. PMID  11337480. 
  4. ^ ab Поляновский, ВО; Ройтберг, МА; Туманян, ВГ (2011). "Сравнительный анализ качества глобального алгоритма и локального алгоритма выравнивания двух последовательностей". Алгоритмы для молекулярной биологии . 6 (1): 25. doi : 10.1186/1748-7188-6-25 . PMC 3223492. PMID  22032267. S2CID  2658261. 
  5. ^ Schneider TD; Stephens RM (1990). «Логотипы последовательностей: новый способ отображения консенсусных последовательностей». Nucleic Acids Res . 18 (20): 6097–6100. doi :10.1093/nar/18.20.6097. PMC 332411. PMID  2172928 . 
  6. ^ «Спецификация формата выравнивания последовательностей/карты» (PDF) .
  7. ^ Брудно М.; Малде С.; Поляков А.; До К. Б.; Куронн О.; Дубчак И.; Батцоглу С. (2003). «Глокальное выравнивание: поиск перестроек во время выравнивания». Биоинформатика . 19. Приложение 1 (90001): i54–62. doi : 10.1093/bioinformatics/btg1005 . PMID  12855437.
  8. ^ Delcher, AL; Kasif, S.; Fleishmann, RD; Peterson, J.; White, O.; Salzberg, SL (1999). «Выравнивание целых геномов». Nucleic Acids Research . 27 (11): 2369–2376. doi : 10.1093 /nar/30.11.2478 . PMC 148804. PMID  10325427. 
  9. ^ Винг-Кин, Сунг (2010). Алгоритмы в биоинформатике: практическое введение (первое издание). Бока-Ратон: Chapman & Hall/CRC Press. ISBN 978-1420070330.
  10. ^ Гото, Осаму (15 декабря 1982 г.). «Улучшенный алгоритм сопоставления биологических последовательностей». Журнал молекулярной биологии . 162 (3): 705–708. doi :10.1016/0022-2836(82)90398-9. ISSN  0022-2836.
  11. ^ Гото, Осаму (1 января 1999 г.). «Множественное выравнивание последовательностей: алгоритмы и приложения». Advances in Biophysics . 36 : 159–206. doi :10.1016/S0065-227X(99)80007-0. ISSN  0065-227X.
  12. ^ Ван Л.; Цзян Т. (1994). «О сложности множественного выравнивания последовательностей». J Comput Biol . 1 (4): 337–48. CiteSeerX 10.1.1.408.894 . doi :10.1089/cmb.1994.1.337. PMID  8790475. 
  13. ^ Элиас, Айзек (2006). «Урегулирование неподатливости множественного выравнивания». J Comput Biol . 13 (7): 1323–1339. CiteSeerX 10.1.1.6.256 . doi :10.1089/cmb.2006.13.1323. PMID  17037961. 
  14. ^ Lipman DJ; Altschul SF; Kececioglu JD (1989). "Инструмент для множественного выравнивания последовательностей". Proc Natl Acad Sci USA . 86 (12): 4412–5. Bibcode : 1989PNAS...86.4412L. doi : 10.1073/pnas.86.12.4412 . PMC 287279. PMID  2734293. 
  15. ^ Хиггинс Д.Г. , Шарп П.М. (1988). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Gene . 73 (1): 237–44. doi :10.1016/0378-1119(88)90330-7. PMID  3243435.
  16. ^ Томпсон Дж. Д.; Хиггинс Д. Г .; Гибсон Т. Дж. (1994). «CLUSTAL W: улучшение чувствительности прогрессивного множественного выравнивания последовательностей с помощью взвешивания последовательностей, штрафов за пробелы, зависящие от позиции, и выбора матрицы весов». Nucleic Acids Res . 22 (22): 4673–80. doi :10.1093/nar/22.22.4673. PMC 308517. PMID  7984417 . 
  17. ^ Ченна Р.; Сугавара Х.; Коике Т.; Лопес Р.; Гибсон Т.Дж.; Хиггинс Д.Г.; Томпсон Дж.Д. (2003). «Множественное выравнивание последовательностей с помощью серии программ Clustal». Nucleic Acids Res . 31 (13): 3497–500. doi :10.1093/nar/gkg500. PMC 168907. PMID  12824352. 
  18. ^ Notredame C; Higgins DG ; Heringa J. (2000). «T-Coffee: новый метод быстрого и точного выравнивания множественных последовательностей». J Mol Biol . 302 (1): 205–17. doi :10.1006/jmbi.2000.4042. PMID  10964570. S2CID  10189971.
  19. ^ Хиросава М.; Тотоки И.; Хосида М.; Ишикава М. (1995). «Комплексное исследование итеративных алгоритмов множественного выравнивания последовательностей». Comput Appl Biosci . 11 (1): 13–8. doi :10.1093/bioinformatics/11.1.13. PMID  7796270.
  20. ^ Karplus K; Barrett C; Hughey R. (1998). «Скрытые марковские модели для обнаружения удаленных белковых гомологий». Биоинформатика . 14 (10): 846–856. CiteSeerX 10.1.1.57.2762 . doi : 10.1093/bioinformatics/14.10.846 . PMID  9927713. 
  21. ^ Chothia C; Lesk AM. (Апрель 1986). «Связь между расхождением последовательности и структуры в белках». EMBO J . 5 (4): 823–6. doi :10.1002/j.1460-2075.1986.tb04288.x. PMC 1166865 . PMID  3709526. 
  22. ^ ab Zhang Y; Skolnick J. (2005). «Проблема предсказания структуры белка может быть решена с использованием текущей библиотеки PDB». Proc Natl Acad Sci USA . 102 (4): 1029–34. Bibcode :2005PNAS..102.1029Z. doi : 10.1073/pnas.0407152101 . PMC 545829 . PMID  15653774. 
  23. ^ Холм Л.; Сандер К. (1996). «Картографирование вселенной белков». Science . 273 (5275): 595–603. Bibcode :1996Sci...273..595H. doi :10.1126/science.273.5275.595. PMID  8662544. S2CID  7509134.
  24. ^ Taylor WR; Flores TP; Orengo CA. (1994). «Множественное выравнивание структуры белка». Protein Sci . 3 (10): 1858–70. doi :10.1002/pro.5560031025. PMC 2142613. PMID  7849601 . 
  25. ^ Orengo CA; Michie AD; Jones S; Jones DT; Swindells MB; Thornton JM (1997). "CATH — иерархическая классификация структур доменов белков". Structure . 5 (8): 1093–108. doi : 10.1016/S0969-2126(97)00260-8 . PMID  9309224.
  26. ^ Шиндялов ИН; Борн ПЭ. (1998). "Выравнивание структуры белка путем инкрементального комбинаторного расширения (CE) оптимального пути". Protein Eng . 11 (9): 739–47. doi : 10.1093/protein/11.9.739 . PMID  9796821.
  27. ^ ab Ortet P; Bastien O (2010). «Откуда берется форма распределения оценок выравнивания?». Эволюционная биоинформатика . 6 : 159–187. doi :10.4137/EBO.S5875. PMC 3023300. PMID  21258650 . 
  28. ^ Фельзенштейн Дж. (2004). Выводы о филогениях . Sinauer Associates: Сандерленд, Массачусетс. ISBN 978-0-87893-177-4.
  29. ^ Altschul SF; Gish W (1996). "Статистика локального выравнивания". Компьютерные методы анализа макромолекулярной последовательности . Методы в энзимологии. Т. 266. С. 460–480. doi :10.1016/S0076-6879(96)66029-7. ISBN 9780121821678. PMID  8743700. {{cite book}}: |journal=проигнорировано ( помощь )
  30. ^ Hartmann AK (2002). "Выборка редких событий: статистика локальных выравниваний последовательностей". Phys. Rev. E. 65 ( 5): 056102. arXiv : cond-mat/0108201 . Bibcode : 2002PhRvE..65e6102H. doi : 10.1103/PhysRevE.65.056102. PMID  12059642. S2CID  193085.
  31. ^ Newberg LA (2008). «Значимость выравниваний последовательностей с пробелами». J Comput Biol . 15 (9): 1187–1194. doi :10.1089/cmb.2008.0125. PMC 2737730. PMID  18973434 . 
  32. ^ Eddy SR; Rost, Burkhard (2008). Rost, Burkhard (ред.). "Вероятностная модель локального выравнивания последовательностей, которая упрощает оценку статистической значимости". PLOS Comput Biol . 4 (5): e1000069. Bibcode : 2008PLSCB...4E0069E. doi : 10.1371/journal.pcbi.1000069 . PMC 2396288. PMID  18516236. S2CID  15640896 . 
  33. ^ Bastien O; Aude JC; Roy S; Marechal E (2004). «Основы массового автоматического парного выравнивания последовательностей белков: теоретическое значение статистики Z-значений». Биоинформатика . 20 (4): 534–537. CiteSeerX 10.1.1.602.6979 . doi : 10.1093/bioinformatics/btg440 . PMID  14990449. 
  34. ^ Агравал А; Хуан X (2011). «Парная статистическая значимость локального выравнивания последовательностей с использованием матриц замен, специфичных для последовательности и позиции». Труды IEEE/ACM по вычислительной биологии и биоинформатике . 8 (1): 194–205. doi :10.1109/TCBB.2009.69. PMID  21071807. S2CID  6559731.
  35. ^ Агравал А; Брендель В.П.; Хуан Х. (2008). «Парная статистическая значимость и эмпирическое определение эффективных штрафов за открытие пробелов для локального выравнивания последовательностей белков». Международный журнал вычислительной биологии и разработки лекарств . 1 (4): 347–367. doi :10.1504/IJCBDD.2008.022207. PMID  20063463. Архивировано из оригинала 28 января 2013 г.
  36. ^ Newberg LA; Lawrence CE (2009). «Точное вычисление распределений целых чисел с применением к выравниванию последовательностей». J Comput Biol . 16 (1): 1–18. doi :10.1089/cmb.2008.0137. PMC 2858568. PMID 19119992  . 
  37. ^ Ким Н.; Ли С. (2008). «Биоинформатическое обнаружение альтернативного сплайсинга». Биоинформатика . Методы в молекулярной биологии. Т. 452. С. 179–97. doi :10.1007/978-1-60327-159-2_9. ISBN 978-1-58829-707-5. PMID  18566765.
  38. ^ Li JB, Levanon EY, Yoon JK и др. (май 2009 г.). «Идентификация участков редактирования РНК человека в масштабе всего генома с помощью параллельного захвата и секвенирования ДНК». Science . 324 (5931): 1210–3. Bibcode :2009Sci...324.1210L. doi :10.1126/science.1170995. PMID  19478186. S2CID  31148824.
  39. ^ Blazewicz J, Bryja M, Figlerowicz M и др. (июнь 2009 г.). «Сборка всего генома из 454 секвенирования с помощью модифицированной концепции ДНК-графа». Comput Biol Chem . 33 (3): 224–30. doi :10.1016/j.compbiolchem.2009.04.005. PMID  19477687.
  40. ^ Duran C; Appleby N; Vardy M; Imelfort M; Edwards D; Batley J (май 2009). «Открытие полиморфизма отдельных нуклеотидов в ячмене с использованием autoSNPdb». Plant Biotechnol. J . 7 (4): 326–33. doi : 10.1111/j.1467-7652.2009.00407.x . PMID  19386041.
  41. ^ Эбботт А.; Цай А. (2000). «Анализ последовательностей и методы оптимального соответствия в социологии, обзор и перспектива». Социологические методы и исследования . 29 (1): 3–33. doi :10.1177/0049124100029001001. S2CID  121097811.
  42. ^ Barzilay R; Lee L. (2002). "Bootstrapping lexical choice via multiple-sequence alignment" (PDF) . Труды конференции ACL-02 по эмпирическим методам в обработке естественного языка - EMNLP '02 . Том 10. стр. 164–171. arXiv : cs/0205065 . Bibcode :2002cs........5065B. doi :10.3115/1118693.1118715. S2CID  7521453.
  43. ^ Kondrak, Grzegorz (2002). "Алгоритмы для реконструкции языка" (PDF) . Университет Торонто, Онтарио. Архивировано из оригинала (PDF) 17 декабря 2008 года . Получено 21 января 2007 года . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  44. ^ Prinzie A.; D. Van den Poel (2006). «Включение последовательной информации в традиционные модели классификации с использованием чувствительного к элементу/позиции SAM» . Системы поддержки принятия решений . 42 (2): 508–526. doi :10.1016/j.dss.2005.02.004.См. также статью Принзи и Ван ден Поэля Принзи, А.; Ванденпоэл, Д. (2007). «Прогнозирование последовательностей приобретения бытовой техники: Марков/Марков для анализа дискриминации и выживания для моделирования последовательной информации в моделях NPTB» . Системы поддержки принятия решений . 44 (1): 28–45. doi :10.1016/j.dss.2007.02.008.
  45. ^ EMBL-EBI. "ClustalW2 < Multiple Sequence Alignment < EMBL-EBI". www.EBI.ac.uk . Получено 12 июня 2017 г. .
  46. ^ T-кофе
  47. ^ "BLAST: Базовый инструмент поиска локального выравнивания". blast.ncbi.nlm.NIH.gov . Получено 12 июня 2017 г. .
  48. ^ "UVA FASTA Server". fasta.bioch.Virginia.edu . Получено 12 июня 2017 г. .
  49. ^ Томпсон Дж. Д.; Плевняк Ф.; Поч О. (1999). «BAliBASE: эталонная база данных выравнивания для оценки программ множественного выравнивания». Биоинформатика . 15 (1): 87–8. doi : 10.1093/bioinformatics/15.1.87 . PMID  10068696.
  50. ^ БАЛИБЕЙС
  51. ^ Томпсон Дж. Д.; Плевняк Ф.; Поч О. (1999). «Комплексное сравнение программ выравнивания множественных последовательностей». Nucleic Acids Res . 27 (13): 2682–90. doi :10.1093/nar/27.13.2682. PMC 148477. PMID  10373585. 
  52. ^ "Множественное выравнивание последовательностей: ремень". 3d-alignment.eu . Получено 12 июня 2017 г. .

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

Викиверситет содержит обучающие ресурсы по методам Dot-matrix
Послушайте эту статью ( 39 минут )
Разговорный значок Википедии
Этот аудиофайл был создан на основе редакции этой статьи от 5 июня 2012 года и не отражает последующие правки. ( 2012-06-05 )
( Аудиопомощь  · Больше устных статей )