stringtranslate.com

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

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

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

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

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

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

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

Представительства

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

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

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

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

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

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

Глобальные и местные согласования

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

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

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

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

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

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

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

Точнее:

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

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

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

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

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

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

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

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

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

Методы Word

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

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

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

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

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

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

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

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

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

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

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

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

Поиск мотива

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

Методы, вдохновленные информатикой

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

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

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

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

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

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

ДАЛИ

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

ССАП

SSAP (программа последовательного выравнивания структур) — это метод структурного выравнивания, основанный на динамическом программировании, который использует векторы между атомами в структурном пространстве в качестве точек сравнения. С момента своего первоначального описания он был расширен, включив в него как множественные, так и попарные выравнивания [23] и использовался при построении иерархической базы данных CATH (класс, архитектура, топология, гомология) для классификации белковых складок. [24] Доступ к базе данных CATH можно получить по адресу «Классификация структуры белков CATH».

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

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

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

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

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

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

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

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

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

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

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

Функции оценки

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

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

Другое биологическое использование

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

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

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

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

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

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

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

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

  1. ^ abc Гора DM. (2004). Биоинформатика: анализ последовательностей и генома (2-е изд.). Лабораторное издательство Колд-Спринг-Харбор: Колд-Спринг-Харбор, Нью-Йорк. ISBN 978-0-87969-608-5.
  2. ^ Ганюк, Пол А. (2021). Алгоритмы в биоинформатике: теория и реализация (1-е изд.). Хобокен, Нью-Джерси: John Wiley & Sons. стр. 1–528. ISBN 978-1-119-69800-5. OCLC  1240827446.{{cite book}}: CS1 maint: дата и год ( ссылка )
  3. ^ "Часто задаваемые вопросы по кластерам #Symbols" . Кластал . Архивировано из оригинала 24 октября 2016 года . Проверено 8 декабря 2014 г.
  4. ^ Нг ПК; Хеникофф С. (май 2001 г.). «Прогнозирование вредных аминокислотных замен». Геном Рез . 11 (5): 863–74. дои : 10.1101/гр.176601. ПМК 311071 . ПМИД  11337480. 
  5. ^ аб Поляновский, В.О.; Ройтберг, Массачусетс; Туманян, В.Г. (2011). «Сравнительный анализ качества глобального алгоритма и локального алгоритма выравнивания двух последовательностей». Алгоритмы молекулярной биологии . 6 (1): 25. дои : 10.1186/1748-7188-6-25 . ПМЦ 3223492 . PMID  22032267. S2CID  2658261. 
  6. ^ Шнайдер ТД; Стивенс Р.М. (1990). «Логотипы последовательностей: новый способ отображения согласованных последовательностей». Нуклеиновые кислоты Рез . 18 (20): 6097–6100. дои : 10.1093/нар/18.20.6097. ПМК 332411 . ПМИД  2172928. 
  7. ^ «Выравнивание последовательностей/Спецификация формата карты» (PDF) .
  8. ^ Брудно М; Мальде С; Поляков А; Сделайте CB; Куронн О; Дубчак I; Бацоглу С (2003). «Глокальное выравнивание: обнаружение перестановок во время выравнивания». Биоинформатика . 19. Приложение 1 (90001): i54–62. doi : 10.1093/биоинформатика/btg1005 . ПМИД  12855437.
  9. ^ Делчер, Алабама; Касиф, С.; Флейшманн, РД; Петерсон, Дж.; Уайт, О.; Зальцберг, СЛ (1999). «Выравнивание целых геномов». Исследования нуклеиновых кислот . 27 (11): 2369–2376. дои : 10.1093/нар/30.11.2478 . ПМК 148804 . ПМИД  10325427. 
  10. ^ Wing-Kin, Сун (2010). Алгоритмы в биоинформатике: практическое введение (первое изд.). Бока-Ратон: Chapman & Hall/CRC Press. ISBN 978-1420070330.
  11. ^ Ван Л; Цзян Т. (1994). «О сложности множественного выравнивания последовательностей». J Компьютерная Биол . 1 (4): 337–48. CiteSeerX 10.1.1.408.894 . дои : 10.1089/cmb.1994.1.337. ПМИД  8790475. 
  12. ^ Элиас, Исаак (2006). «Урегулирование трудноразрешимости множественного выравнивания». J Компьютерная Биол . 13 (7): 1323–1339. CiteSeerX 10.1.1.6.256 . дои : 10.1089/cmb.2006.13.1323. ПМИД  17037961. 
  13. ^ Липман DJ; Альтшул С.Ф.; Кечечиоглу Дж.Д. (1989). «Инструмент для множественного выравнивания последовательностей». Proc Natl Acad Sci США . 86 (12): 4412–5. Бибкод : 1989PNAS...86.4412L. дои : 10.1073/pnas.86.12.4412 . ПМЦ 287279 . ПМИД  2734293. 
  14. ^ Хиггинс Д.Г. , Sharp PM (1988). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–44. дои : 10.1016/0378-1119(88)90330-7. ПМИД  3243435.
  15. ^ Томпсон Дж.Д.; Хиггинс Д.Г .; Гибсон Т.Дж. (1994). «CLUSTAL W: повышение чувствительности прогрессивного выравнивания множественных последовательностей за счет взвешивания последовательностей, штрафов за пробелы для конкретной позиции и выбора весовой матрицы». Нуклеиновые кислоты Рез . 22 (22): 4673–80. дои : 10.1093/нар/22.22.4673. ПМЦ 308517 . ПМИД  7984417. 
  16. ^ Ченна Р; Сугавара Х; Койке Т; Лопес Р; Гибсон Т.Дж.; Хиггинс Д.Г.; Томпсон Дж.Д. (2003). «Множественное выравнивание последовательностей с помощью программ серии Clustal». Нуклеиновые кислоты Рез . 31 (13): 3497–500. дои : 10.1093/nar/gkg500. ПМК 168907 . ПМИД  12824352. 
  17. ^ Нотредам С; Хиггинс Д.Г .; Херинга Дж. (2000). «T-Coffee: новый метод быстрого и точного выравнивания множественных последовательностей». Дж Мол Биол . 302 (1): 205–17. дои : 10.1006/jmbi.2000.4042. PMID  10964570. S2CID  10189971.
  18. ^ Хиросава М; Тотоки Ю; Хошида М; Исикава М. (1995). «Комплексное исследование итерационных алгоритмов множественного выравнивания последовательностей». Компьютерные приложения и биологические науки . 11 (1): 13–8. doi : 10.1093/биоинформатика/11.1.13. ПМИД  7796270.
  19. ^ Карплюс К; Барретт С; Хьюи Р. (1998). «Скрытые марковские модели для обнаружения отдаленных гомологий белков». Биоинформатика . 14 (10): 846–856. дои : 10.1093/биоинформатика/14.10.846 . ПМИД  9927713.
  20. ^ Чотия С; Леск АМ. (апрель 1986 г.). «Связь между расхождением последовательности и структуры белков». ЭМБО Дж . 5 (4): 823–6. doi :10.1002/j.1460-2075.1986.tb04288.x. ПМК 1166865 . ПМИД  3709526. 
  21. ^ Аб Чжан Ю; Сколник Дж. (2005). «Проблема предсказания структуры белка может быть решена с использованием текущей библиотеки PDB». Proc Natl Acad Sci США . 102 (4): 1029–34. Бибкод : 2005PNAS..102.1029Z. дои : 10.1073/pnas.0407152101 . ПМЦ 545829 . ПМИД  15653774. 
  22. ^ Холм Л; Сандер С (1996). «Картирование белковой вселенной». Наука . 273 (5275): 595–603. Бибкод : 1996Sci...273..595H. дои : 10.1126/science.273.5275.595. PMID  8662544. S2CID  7509134.
  23. ^ Тейлор WR; Флорес ТП; Оренго, Калифорния. (1994). «Множественное выравнивание белковых структур». Белковая наука . 3 (10): 1858–70. дои : 10.1002/pro.5560031025. ПМК 2142613 . ПМИД  7849601. 
  24. ^ Оренго, Калифорния; Мичи А.Д.; Джонс С; Джонс Д.Т.; Суинделлс МБ; Торнтон Дж. М. (1997). «CATH - иерархическая классификация структур белковых доменов». Состав . 5 (8): 1093–108. дои : 10.1016/S0969-2126(97)00260-8 . ПМИД  9309224.
  25. ^ Шиндялов И.Н.; Борн ЧП. (1998). «Выравнивание структуры белка путем постепенного комбинаторного расширения (CE) оптимального пути». Белок англ . 11 (9): 739–47. дои : 10.1093/протеин/11.9.739 . ПМИД  9796821.
  26. ^ аб Ортет П; Бастьен О (2010). «Откуда берется форма распределения баллов выравнивания?». Эволюционная биоинформатика . 6 : 159–187. дои : 10.4137/EBO.S5875. ПМК 3023300 . ПМИД  21258650. 
  27. ^ Фельзенштейн Дж. (2004). Выводы о филогениях . Sinauer Associates: Сандерленд, Массачусетс. ISBN 978-0-87893-177-4.
  28. ^ Альтшул С.Ф.; Гиш В. (1996). «Статистика местного выравнивания». Компьютерные методы анализа макромолекулярных последовательностей . Методы энзимологии. Том. 266. С. 460–480. дои : 10.1016/S0076-6879(96)66029-7. ISBN 9780121821678. ПМИД  8743700. {{cite book}}: |journal=игнорируется ( помощь )
  29. ^ Хартманн АК (2002). «Отбор редких событий: статистика локальных выравниваний последовательностей». Физ. Преподобный Е. 65 (5): 056102. arXiv : cond-mat/0108201 . Бибкод : 2002PhRvE..65e6102H. doi : 10.1103/PhysRevE.65.056102. PMID  12059642. S2CID  193085.
  30. ^ Ньюберг, Лос-Анджелес (2008). «Значение разрывов в выравнивании последовательностей». J Компьютерная Биол . 15 (9): 1187–1194. дои : 10.1089/cmb.2008.0125. ПМЦ 2737730 . ПМИД  18973434. 
  31. ^ Эдди С.Р.; Рост, Буркхард (2008). Рост, Буркхард (ред.). «Вероятностная модель выравнивания локальных последовательностей, упрощающая оценку статистической значимости». ПЛОС Компьютерная Биол . 4 (5): e1000069. Бибкод : 2008PLSCB...4E0069E. дои : 10.1371/journal.pcbi.1000069 . ПМК 2396288 . PMID  18516236. S2CID  15640896. 
  32. ^ Бастьен О; Од Дж. К.; Рой С; Марешаль Э (2004). «Основы массового автоматического попарного выравнивания белковых последовательностей: теоретическое значение статистики Z-значений». Биоинформатика . 20 (4): 534–537. doi : 10.1093/биоинформатика/btg440 . ПМИД  14990449.
  33. ^ Агравал А; Хуан Икс (2011). «Попарная статистическая значимость локального выравнивания последовательностей с использованием матриц замены, специфичных для последовательности и позиции». Транзакции IEEE/ACM по вычислительной биологии и биоинформатике . 8 (1): 194–205. дои : 10.1109/TCBB.2009.69. PMID  21071807. S2CID  6559731.
  34. ^ Агравал А; Брендель, вице-президент; Хуан Икс (2008). «Парная статистическая значимость и эмпирическое определение эффективных штрафов за открытие пробелов для выравнивания локальных последовательностей белка». Международный журнал вычислительной биологии и разработки лекарств . 1 (4): 347–367. doi : 10.1504/IJCBDD.2008.022207. PMID  20063463. Архивировано из оригинала 28 января 2013 года.
  35. ^ Ньюберг, Лос-Анджелес; Лоуренс CE (2009). «Точный расчет распределений целых чисел с применением к выравниванию последовательностей». J Компьютерная Биол . 16 (1): 1–18. дои : 10.1089/cmb.2008.0137. ПМЦ 2858568 . ПМИД  19119992. 
  36. ^ Ким Н; Ли С. (2008). «Биоинформатическое обнаружение альтернативного сплайсинга». Биоинформатика . Методы молекулярной биологии. Том. 452. стр. 179–97. дои : 10.1007/978-1-60327-159-2_9. ISBN 978-1-58829-707-5. ПМИД  18566765.
  37. ^ Ли Дж.Б., Леванон Э.Ю., Юн Дж.К. и др. (май 2009 г.). «Полногеномная идентификация сайтов редактирования РНК человека путем параллельного захвата и секвенирования ДНК». Наука . 324 (5931): 1210–3. Бибкод : 2009Sci...324.1210L. дои : 10.1126/science.1170995. PMID  19478186. S2CID  31148824.
  38. ^ Блажевич Дж., Брия М., Фиглерович М. и др. (июнь 2009 г.). «Сборка всего генома на основе результатов секвенирования 454 с использованием концепции модифицированного графа ДНК». Вычислительная биол. хим . 33 (3): 224–30. doi :10.1016/j.compbiolchem.2009.04.005. ПМИД  19477687.
  39. ^ Дюран С; Эпплби Н; Варди М; Имельфорт М; Эдвардс Д; Бэтли Дж. (май 2009 г.). «Обнаружение однонуклеотидного полиморфизма в ячмене с использованием autoSNPdb». Растительная биотехнология. Дж . 7 (4): 326–33. дои : 10.1111/j.1467-7652.2009.00407.x . ПМИД  19386041.
  40. ^ Эбботт А.; Цай А. (2000). «Анализ последовательностей и методы оптимального сопоставления в социологии, обзор и перспективы». Социологические методы и исследования . 29 (1): 3–33. дои : 10.1177/0049124100029001001. S2CID  121097811.
  41. ^ Барзилай Р; Ли Л. (2002). «Стартовый лексический выбор посредством выравнивания нескольких последовательностей» (PDF) . Материалы конференции ACL-02 по эмпирическим методам обработки естественного языка - EMNLP '02 . Том. 10. С. 164–171. arXiv : cs/0205065 . Бибкод : 2002cs........5065B. дои : 10.3115/1118693.1118715. S2CID  7521453. {{cite book}}: |journal=игнорируется ( помощь )
  42. ^ Кондрак, Гжегож (2002). «Алгоритмы реконструкции языка» (PDF) . Университет Торонто, Онтарио. Архивировано из оригинала (PDF) 17 декабря 2008 года . Проверено 21 января 2007 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
  43. ^ Принци А.; Д. Ван ден Поэль (2006). «Включение последовательной информации в традиционные модели классификации с использованием SAM, чувствительного к элементу / положению» . Системы поддержки принятия решений . 42 (2): 508–526. дои : 10.1016/j.dss.2005.02.004.См. также статью Принци и Ван ден Поэла Prinzie, A; Ванденпол, Д. (2007). «Прогнозирование последовательностей приобретения бытовой техники: Марков/Марков для анализа дискриминации и выживания для моделирования последовательной информации в моделях NPTB» . Системы поддержки принятия решений . 44 (1): 28–45. дои : 10.1016/j.dss.2007.02.008.
  44. ^ EMBL-EBI. «ClustalW2 <Выравнивание множественных последовательностей <EMBL-EBI». www.EBI.ac.uk. _ Проверено 12 июня 2017 г.
  45. ^ Т-кофе
  46. ^ «BLAST: Базовый инструмент поиска локального выравнивания» . blast.ncbi.nlm.NIH.gov . Проверено 12 июня 2017 г.
  47. ^ "Сервер UVA FASTA" . fasta.bioch.Virginia.edu . Проверено 12 июня 2017 г.
  48. ^ Томпсон Дж.Д.; Плевняк Ф; Поч О (1999). «BAliBASE: эталонная база данных выравнивания для оценки нескольких программ выравнивания». Биоинформатика . 15 (1): 87–8. дои : 10.1093/биоинформатика/15.1.87 . ПМИД  10068696.
  49. ^ БАЛИБАЗЕ
  50. ^ Томпсон Дж.Д.; Плевняк Ф; Поч О. (1999). «Всестороннее сравнение нескольких программ выравнивания последовательностей». Нуклеиновые кислоты Рез . 27 (13): 2682–90. дои : 10.1093/нар/27.13.2682. ПМК 148477 . ПМИД  10373585. 
  51. ^ «Множественное выравнивание последовательностей: Ремешок» . 3d-alignment.eu . Проверено 12 июня 2017 г.

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

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