В биоинформатике выравнивание последовательностей — это способ упорядочения последовательностей ДНК , РНК или белка для выявления областей сходства, которые могут быть следствием функциональных, структурных или эволюционных связей между последовательностями. [1] Выровненные последовательности нуклеотидных или аминокислотных остатков обычно представляются в виде строк в матрице . Между остатками вставляются пробелы , чтобы одинаковые или похожие символы располагались в последовательных столбцах. Выравнивание последовательностей также используется для небиологических последовательностей, таких как расчет стоимости расстояния между строками на естественном языке или для отображения финансовых данных.
Если две последовательности в выравнивании имеют общего предка, несовпадения можно интерпретировать как точечные мутации , а пробелы — как инделы (то есть мутации вставки или делеции), появившиеся в одной или обеих линиях с момента их расхождения друг от друга. При выравнивании последовательностей белков степень сходства между аминокислотами, занимающими определенное положение в последовательности, можно интерпретировать как приблизительную меру того, насколько консервативен конкретный участок или мотив последовательности среди линий. Отсутствие замен или наличие только очень консервативных замен (то есть замены аминокислот, боковые цепи которых имеют сходные биохимические свойства) в определенном участке последовательности позволяют предположить [3] , что этот участок имеет структурное или функциональное значение. . Хотя нуклеотидные основания ДНК и РНК более похожи друг на друга, чем аминокислоты, консервативность пар оснований может указывать на сходную функциональную или структурную роль.
Очень короткие или очень похожие последовательности можно выровнять вручную. Однако наиболее интересные проблемы требуют выравнивания длинных, сильно вариабельных или чрезвычайно многочисленных последовательностей, которые не могут быть выровнены исключительно человеческими усилиями. Вместо этого человеческие знания применяются при построении алгоритмов для обеспечения высококачественного выравнивания последовательностей, а иногда и для корректировки окончательных результатов для отражения закономерностей, которые трудно представить алгоритмически (особенно в случае нуклеотидных последовательностей). Вычислительные подходы к выравниванию последовательностей обычно делятся на две категории: глобальное выравнивание и локальное выравнивание . Вычисление глобального выравнивания — это форма глобальной оптимизации , которая «заставляет» выравнивание охватывать всю длину всех последовательностей запросов. Напротив, локальное выравнивание идентифицирует области сходства внутри длинных последовательностей, которые в целом часто сильно расходятся. Локальное выравнивание часто предпочтительнее, но его сложнее вычислить из-за дополнительной проблемы определения областей сходства. [4] Для решения проблемы выравнивания последовательностей применялись различные вычислительные алгоритмы. К ним относятся медленные, но формально правильные методы, такие как динамическое программирование . К ним также относятся эффективные эвристические алгоритмы или вероятностные методы, предназначенные для поиска в крупномасштабных базах данных, которые не гарантируют нахождение наилучших совпадений.
Трассы обычно представляются как графически, так и в текстовом формате. Почти во всех представлениях выравнивания последовательностей последовательности записаны в строках, расположенных так, что выровненные остатки появляются в последовательных столбцах. В текстовых форматах выровненные столбцы, содержащие одинаковые или похожие символы, обозначаются системой символов сохранения. Как и на изображении выше, символ звездочки или вертикальной черты используется для обозначения идентичности двух столбцов; другие менее распространенные символы включают двоеточие для консервативных замен и точку для полуконсервативных замен. Многие программы визуализации последовательностей также используют цвет для отображения информации о свойствах отдельных элементов последовательности; в последовательностях ДНК и РНК это соответствует присвоению каждому нуклеотиду своего цвета. В выравниваниях белков, например, показанном на изображении выше, цвет часто используется для обозначения свойств аминокислот, что помогает судить о сохранении данной аминокислотной замены. Для нескольких последовательностей последняя строка в каждом столбце часто является консенсусной последовательностью, определяемой выравниванием; консенсусная последовательность также часто представляется в графическом формате с логотипом последовательности , в котором размер каждой буквы нуклеотида или аминокислоты соответствует степени ее консервативности. [5]
Выравнивания последовательностей могут храниться в самых разных форматах текстовых файлов, многие из которых изначально были разработаны в сочетании с конкретной программой или реализацией выравнивания. Большинство веб-инструментов допускают ограниченное количество входных и выходных форматов, таких как формат FASTA и формат GenBank , и выходные данные нелегко редактировать. Доступно несколько программ преобразования, которые предоставляют графический интерфейс и/или интерфейс командной строки [ мертвая ссылка ] , такие как READSEQ и EMBOSS . Существует также несколько программных пакетов, которые предоставляют эту функциональность преобразования, например BioPython , BioRuby и BioPerl . Файлы SAM /BAM используют строковый формат CIGAR (компактный отчет об идиосинкразическом выравнивании с пробелами) для представления выравнивания последовательности по ссылке путем кодирования последовательности событий (например, совпадения/несоответствия, вставок, удалений). [6]
Ссылка. : GTCGTAGAATA
Чтение : CACGTAG—TA
CIGAR: 2S5M2D2M где:
2S = 2 мягких отсечения (могут быть несовпадения или чтение длиннее, чем совпавшая последовательность)
5M = 5 совпадений или несовпадений
2D = 2 удаления
2M = 2 совпадения или несовпадения
Исходный формат CIGAR из программы выравнивания exonerate не различал несоответствия или совпадения с символом M.
Документ спецификации SAMv1 определяет новые коды CIGAR. В большинстве случаев для обозначения совпадений или несоответствий предпочтительнее использовать символы «=» и «X», а не старый символ «M», который является неоднозначным.
Глобальные выравнивания, которые пытаются выровнять каждый остаток в каждой последовательности, наиболее полезны, когда последовательности в наборе запроса похожи и имеют примерно одинаковый размер. (Это не означает, что глобальное выравнивание не может начинаться и/или заканчиваться пробелами.) Общим методом глобального выравнивания является алгоритм Нидлмана-Вунша , основанный на динамическом программировании. Локальное выравнивание более полезно для несходных последовательностей, которые, как предполагается, содержат области сходства или сходные мотивы последовательностей в пределах их более широкого контекста последовательности. Алгоритм Смита-Уотермана — это общий метод локального выравнивания, основанный на той же схеме динамического программирования, но с дополнительными вариантами начала и окончания в любом месте. [4]
Гибридные методы, известные как полуглобальные или «глокальные» (сокращенно от glob - local ) методы, ищут наилучшее возможное частичное выравнивание двух последовательностей (другими словами, комбинацию одного или обоих начал и одного или обоих). считается, что концы совмещены). Это может быть особенно полезно, когда нисходящая часть одной последовательности перекрывается с восходящей частью другой последовательности. В этом случае ни глобальное, ни локальное выравнивание не являются полностью подходящими: глобальное выравнивание будет пытаться заставить выравнивание выйти за пределы области перекрытия, в то время как локальное выравнивание может не полностью покрыть область перекрытия. [7] Другой случай, когда полуглобальное выравнивание полезно, — это когда одна последовательность короткая (например, последовательность гена), а другая очень длинная (например, последовательность хромосомы). В этом случае короткая последовательность должна быть глобально (полностью) выровнена, но для длинной последовательности желательно только локальное (частичное) выравнивание.
Быстрое расширение генетических данных бросает вызов скорости современных алгоритмов выравнивания последовательностей ДНК. Насущные потребности в эффективном и точном методе обнаружения вариантов ДНК требуют инновационных подходов к параллельной обработке в реальном времени. Оптические вычислительные подходы были предложены в качестве многообещающей альтернативы нынешним электрическим реализациям, однако их применимость еще предстоит проверить [1].
Методы попарного выравнивания последовательностей используются для поиска наиболее подходящих кусочных (локальных или глобальных) выравниваний двух последовательностей запроса. Парные выравнивания можно использовать только между двумя последовательностями одновременно, но они эффективны для вычислений и часто используются для методов, не требующих предельной точности (например, поиск в базе данных последовательностей с высоким сходством с запросом). Тремя основными методами создания парных выравниваний являются матричные методы, динамическое программирование и словесные методы; [1] однако методы множественного выравнивания последовательностей также могут выравнивать пары последовательностей. Хотя каждый метод имеет свои сильные и слабые стороны, все три парных метода испытывают трудности с высокоповторяющимися последовательностями с низким содержанием информации , особенно там, где количество повторений различается в двух последовательностях, которые необходимо выровнять.
Одним из способов количественной оценки полезности данного попарного выравнивания является « максимальное уникальное совпадение » (MUM) или самая длинная подпоследовательность, которая встречается в обеих последовательностях запроса. Более длинные последовательности MUM обычно отражают более близкое родство. [8] в области множественного выравнивания последовательностей геномов в вычислительной биологии . Идентификация MUM и других потенциальных якорей является первым шагом в создании более крупных систем согласования, таких как MUMmer . Якоря — это области между двумя геномами, где они очень похожи. Чтобы понять, что такое МАМА, мы можем разобрать каждое слово в аббревиатуре. Совпадение подразумевает, что подстрока встречается в обеих выравниваемых последовательностях. Уникальность означает, что подстрока встречается в каждой последовательности только один раз. Наконец, «максимум» утверждает, что подстрока не является частью другой более крупной строки, которая удовлетворяет обоим предыдущим требованиям. Идея, лежащая в основе этого, заключается в том, что длинные последовательности, которые точно совпадают и встречаются только один раз в каждом геноме, почти наверняка являются частью глобального выравнивания.
Точнее:
«Для двух геномов A и B подстрока максимального уникального совпадения (MUM) представляет собой общую подстроку A и B, длина которой превышает указанную минимальную длину d (по умолчанию d = 20), такую что
- он максимален, то есть его нельзя расширить с любого конца, не вызывая несоответствия; и
- оно уникально в обеих последовательностях» [9]
Матричный подход, который неявно создает семейство выравниваний для отдельных областей последовательности, является качественным и концептуально простым, хотя и требует много времени для анализа в больших масштабах. При отсутствии шума можно легко визуально идентифицировать определенные особенности последовательности, такие как вставки, делеции, повторы или инвертированные повторы , на точечно-матричном графике. Чтобы построить точечно-матричный график , две последовательности записываются вдоль верхней строки и крайнего левого столбца двумерной матрицы , а точка ставится в любой точке, где символы в соответствующих столбцах совпадают — это типичный рекуррентный график . В некоторых реализациях размер или интенсивность точки варьируются в зависимости от степени сходства двух символов, чтобы обеспечить консервативные замены. Точечные графики очень близких последовательностей будут отображаться в виде одной линии вдоль главной диагонали матрицы .
Проблемы с точечными диаграммами как методом отображения информации включают в себя: шум, отсутствие ясности, неинтуитивность, трудности с извлечением сводной статистики совпадений и позиций совпадений в двух последовательностях. Также имеется много бесполезного пространства, когда данные сопоставления по своей сути дублируются по диагонали, и большая часть фактической площади графика занята либо пустым пространством, либо шумом, и, наконец, точечные графики ограничены двумя последовательностями. Ни одно из этих ограничений не применимо к диаграммам выравнивания Miropeats, но у них есть свои недостатки.
Точечные графики также можно использовать для оценки повторяемости в одной последовательности. Последовательность можно построить против самой себя, и области, имеющие значительное сходство, будут отображаться в виде линий за пределами главной диагонали. Этот эффект возникает, когда белок состоит из множества сходных структурных доменов .
Технику динамического программирования можно применять для создания глобальных выравниваний с помощью алгоритма Нидлмана-Вунша и локальных выравниваний с помощью алгоритма Смита-Уотермана . При типичном использовании при выравнивании белков используется матрица замен для присвоения баллов совпадениям или несоответствиям аминокислот, а также штраф за пропуск за совпадение аминокислоты в одной последовательности с пробелом в другой. При выравнивании ДНК и РНК может использоваться оценочная матрица, но на практике часто просто присваивается положительная оценка совпадения, отрицательная оценка несовпадения и отрицательный штраф за пропуск. (В стандартном динамическом программировании оценка каждой позиции аминокислоты не зависит от идентичности ее соседей, и поэтому эффекты стекирования оснований не учитываются. Однако такие эффекты можно учесть, изменив алгоритм.) [ необходима ссылка ] Распространенным расширением стандартных затрат на линейный разрыв является использование двух разных штрафов за разрыв за открытие разрыва и за его расширение. Обычно первое значение намного больше, чем второе, например, -10 для открытия гэпа и -2 для расширения гэпа. Таким образом, количество пробелов в выравнивании обычно уменьшается, а остатки и пробелы сохраняются вместе, что обычно имеет больший биологический смысл. Алгоритм Гото реализует стоимость аффинного разрыва, используя три матрицы. [ нужна ссылка ]
Динамическое программирование может быть полезно при сопоставлении нуклеотидов с белковыми последовательностями — задача, осложняющаяся необходимостью учитывать мутации сдвига рамки считывания (обычно вставки или делеции). Метод фреймового поиска производит серию глобальных или локальных парных выравниваний между запрашиваемой нуклеотидной последовательностью и поисковым набором белковых последовательностей или наоборот. Его способность оценивать сдвиги рамки считывания, смещенные на произвольное количество нуклеотидов, делает этот метод полезным для последовательностей, содержащих большое количество инделей, которые может быть очень трудно согласовать с более эффективными эвристическими методами. На практике этот метод требует больших вычислительных мощностей или системы, архитектура которой специализирована для динамического программирования. Пакеты BLAST и EMBOSS предоставляют базовые инструменты для создания транслированных выравниваний (хотя некоторые из этих подходов используют побочные эффекты возможностей инструментов по поиску последовательностей). Более общие методы доступны в программном обеспечении с открытым исходным кодом, таком как GeneWise. [ нужна ссылка ]
Метод динамического программирования гарантированно находит оптимальное выравнивание с учетом конкретной оценочной функции; однако определение хорошей оценочной функции часто является эмпирическим, а не теоретическим вопросом. Хотя динамическое программирование можно расширить до более чем двух последовательностей, оно слишком медленное для большого количества последовательностей или чрезвычайно длинных последовательностей. [ нужна ссылка ]
Методы Word, также известные как методы k -кортежей, представляют собой эвристические методы, которые не гарантируют нахождение оптимального решения для выравнивания, но они значительно более эффективны, чем динамическое программирование. Эти методы особенно полезны при крупномасштабном поиске в базе данных, когда понятно, что большая часть последовательностей-кандидатов по существу не будет иметь существенного совпадения с последовательностью запроса. Методы Word наиболее известны благодаря своей реализации в инструментах поиска по базам данных FASTA и семействе BLAST . [1] Методы Word идентифицируют серию коротких непересекающихся подпоследовательностей («слов») в последовательности запроса, которые затем сопоставляются с последовательностями базы данных-кандидатами. Относительные позиции слова в двух сравниваемых последовательностях вычитаются для получения смещения; это будет указывать на область выравнивания, если несколько разных слов создают одинаковое смещение. Только если эта область обнаружена, эти методы применяют более чувствительные критерии выравнивания; таким образом, устраняются многие ненужные сравнения с последовательностями, не имеющими заметного сходства.
В методе FASTA пользователь определяет значение k , которое будет использовать в качестве длины слова для поиска в базе данных. Этот метод медленнее, но более чувствителен при более низких значениях k , которые также предпочтительны для поиска, включающего очень короткую последовательность запросов. Семейство методов поиска BLAST предоставляет ряд алгоритмов, оптимизированных для определенных типов запросов, таких как поиск совпадений отдаленно связанных последовательностей. BLAST был разработан как более быстрая альтернатива FASTA без особого ущерба для точности; Как и FASTA, BLAST использует поиск слов длиной k , но оценивает только наиболее значимые совпадения слов, а не каждое совпадение слов, как это делает FASTA. В большинстве реализаций BLAST используется фиксированная длина слова по умолчанию, которая оптимизирована для типа запроса и базы данных и изменяется только при особых обстоятельствах, например, при поиске с использованием повторяющихся или очень коротких последовательностей запросов. Реализации можно найти на ряде веб-порталов, таких как EMBL FASTA и NCBI BLAST.
Множественное выравнивание последовательностей представляет собой расширение парного выравнивания, позволяющее включать более двух последовательностей одновременно. Множественные методы выравнивания пытаются выровнять все последовательности в заданном наборе запросов. Множественные выравнивания часто используются для идентификации консервативных областей последовательностей в группе последовательностей, предположительно связанных эволюционно. Такие консервативные мотивы последовательностей могут использоваться в сочетании со структурной и механистической информацией для определения местоположения каталитических активных центров ферментов . Выравнивания также используются для помощи в установлении эволюционных связей путем построения филогенетических деревьев . Множественное выравнивание последовательностей сложно произвести с вычислительной точки зрения, и большинство формулировок проблемы приводят к NP-полным задачам комбинаторной оптимизации. [10] [11] Тем не менее, полезность этих выравниваний в биоинформатике привела к разработке множества методов, подходящих для выравнивания трех или более последовательностей.
Техника динамического программирования теоретически применима к любому количеству последовательностей; однако, поскольку он требует больших вычислительных затрат как по времени, так и по памяти , он редко используется для более чем трех или четырех последовательностей в своей самой простой форме. Этот метод требует построения n -мерного эквивалента матрицы последовательностей, сформированной из двух последовательностей, где n — количество последовательностей в запросе. Стандартное динамическое программирование сначала используется для всех пар последовательностей запросов, а затем «пространство выравнивания» заполняется путем рассмотрения возможных совпадений или пробелов в промежуточных позициях, в конечном итоге создавая выравнивание по существу между каждым выравниванием двух последовательностей. Хотя этот метод требует больших вычислительных затрат, его гарантия глобального оптимального решения полезна в тех случаях, когда необходимо точно выровнять лишь несколько последовательностей. Один из методов снижения вычислительных требований динамического программирования, основанный на целевой функции «суммы пар» , был реализован в пакете программного обеспечения MSA. [12]
Прогрессивные, иерархические или древовидные методы генерируют множественное выравнивание последовательностей, сначала выравнивая наиболее похожие последовательности, а затем последовательно добавляя к выравниванию менее связанные последовательности или группы, пока весь набор запросов не будет включен в решение. Исходное дерево, описывающее родство последовательностей, основано на парных сравнениях, которые могут включать в себя эвристические методы парного выравнивания, аналогичные FASTA . Результаты прогрессивного выравнивания зависят от выбора «наиболее связанных» последовательностей и, следовательно, могут быть чувствительны к неточностям начального парного выравнивания. Большинство прогрессивных методов множественного выравнивания последовательностей дополнительно взвешивают последовательности в наборе запросов в соответствии с их родством, что снижает вероятность неправильного выбора исходных последовательностей и, таким образом, повышает точность выравнивания.
Многие варианты прогрессивной реализации Clustal [13] [14] [15] используются для множественного выравнивания последовательностей, построения филогенетического дерева и в качестве входных данных для предсказания структуры белка . Более медленный, но более точный вариант прогрессивного метода известен как T-Coffee . [16]
Итеративные методы пытаются улучшить сильную зависимость от точности начального парного выравнивания, что является слабым местом прогрессивных методов. Итеративные методы оптимизируют целевую функцию на основе выбранного метода оценки выравнивания путем назначения начального глобального выравнивания, а затем перераспределения подмножеств последовательностей. Затем перевыровненные подмножества сами выравниваются, чтобы обеспечить выравнивание множественных последовательностей в следующей итерации. Различные способы выбора подгрупп последовательностей и целевой функции рассмотрены в [17] .
Поиск мотивов, также известный как анализ профиля, создает глобальное выравнивание множественных последовательностей, которое пытается выровнять мотивы коротких консервативных последовательностей среди последовательностей в наборе запросов. Обычно это делается путем сначала построения общего глобального множественного выравнивания последовательностей, после чего высококонсервативные области изолируются и используются для построения набора матриц профилей. Матрица профиля для каждой консервативной области устроена как оценочная матрица, но ее значения частоты для каждой аминокислоты или нуклеотида в каждом положении получены на основе распределения признаков консервативной области, а не на основе более общего эмпирического распределения. Матрицы профилей затем используются для поиска в других последовательностях появления мотива, который они характеризуют. В тех случаях, когда исходный набор данных содержал небольшое количество последовательностей или только сильно связанные последовательности, добавляются псевдосчетчики для нормализации распределений символов, представленных в мотиве.
Для решения задачи выравнивания множественных последовательностей также применялись различные алгоритмы общей оптимизации , обычно используемые в информатике. Скрытые модели Маркова использовались для получения оценок вероятности для семейства возможных множественных выравниваний последовательностей для данного набора запросов; хотя ранние методы, основанные на HMM, давали неудовлетворительную производительность, более поздние приложения обнаружили их особенно эффективными при обнаружении отдаленно связанных последовательностей, поскольку они менее восприимчивы к шуму, создаваемому консервативными или полуконсервативными заменами. [18] Генетические алгоритмы и имитация отжига также использовались для оптимизации показателей множественного выравнивания последовательностей, что оценивалось с помощью оценочной функции, такой как метод суммы пар. Более полную информацию и программные пакеты можно найти в основной статье множественного выравнивания последовательностей .
Преобразование Берроуза -Уиллера было успешно применено для быстрого выравнивания коротких чтений в таких популярных инструментах, как Bowtie и BWA. См. FM-индекс .
Структурное выравнивание, которое обычно специфично для последовательностей белка, а иногда и РНК, использует информацию о вторичной и третичной структуре молекулы белка или РНК, чтобы помочь в выравнивании последовательностей. Эти методы можно использовать для двух или более последовательностей и обычно обеспечивают локальное выравнивание; однако, поскольку они зависят от наличия структурной информации, их можно использовать только для последовательностей, соответствующие структуры которых известны (обычно с помощью рентгеновской кристаллографии или ЯМР-спектроскопии ). Поскольку структура как белка, так и РНК более консервативна в эволюционном отношении, чем последовательность, [19] структурное выравнивание может быть более надежным между последовательностями, которые очень отдаленно родственны и разошлись настолько сильно, что сравнение последовательностей не может надежно обнаружить их сходство.
Структурные выравнивания используются в качестве «золотого стандарта» при оценке выравниваний для предсказания структуры белка на основе гомологии [20], поскольку они явно выравнивают области белковой последовательности, которые структурно схожи, а не полагаются исключительно на информацию о последовательностях. Однако очевидно, что структурные выравнивания нельзя использовать при предсказании структуры, поскольку по крайней мере одна последовательность в наборе запросов является целью моделирования, для которой структура неизвестна. Было показано, что при структурном выравнивании между последовательностью мишени и матричной последовательностью можно создать высокоточные модели последовательности целевого белка; Основным камнем преткновения в предсказании структуры на основе гомологии является получение структурно точных выравниваний с учетом только информации о последовательностях. [20]
Метод DALI, или выравнивание матрицы расстояний , представляет собой метод на основе фрагментов для построения структурных выравниваний на основе шаблонов контактного сходства между последовательными гексапептидами в запрашиваемых последовательностях. [21] Он может генерировать парные или множественные выравнивания и идентифицировать структурных соседей запрашиваемой последовательности в Банке данных белков (PDB). Он использовался для создания базы данных структурного выравнивания FSSP (складчатая классификация, основанная на выравнивании структуры и структуры белков или семейств структурно подобных белков). Доступ к веб-серверу DALI можно получить через DALI, а FSSP находится в базе данных Dali.
SSAP (программа последовательного выравнивания структур) — это метод структурного выравнивания, основанный на динамическом программировании, который использует векторы между атомами в структурном пространстве в качестве точек сравнения. С момента своего первоначального описания он был расширен, включив в него как множественные, так и попарные выравнивания [22] и использовался при построении иерархической классификации белковых складок CATH (класс, архитектура, топология, гомология) базы данных. [23] Доступ к базе данных CATH можно получить на странице «Классификация структуры белков CATH».
Метод комбинаторного расширения структурного выравнивания генерирует парное структурное выравнивание, используя локальную геометрию для выравнивания коротких фрагментов двух анализируемых белков, а затем собирает эти фрагменты в более крупное выравнивание. [24] На основе таких показателей, как среднеквадратическое расстояние твердого тела , расстояния остатков, локальная вторичная структура и особенности окружающей среды, такие как гидрофобность соседей остатков , генерируются локальные выравнивания, называемые «парами выровненных фрагментов», которые используются для построения матрицы сходства. представление всех возможных структурных согласований в пределах заранее определенных критериев отсечения. Затем путь от одного состояния структуры белка к другому прослеживается через матрицу путем расширения растущего выравнивания по одному фрагменту за раз. Оптимальный такой путь определяет выравнивание комбинаторного расширения. Веб-сервер, реализующий метод и предоставляющий базу данных попарных выравниваний структур в Банке данных белков, расположен на веб-сайте Combinatorial Extension.
Филогенетика и выравнивание последовательностей являются тесно связанными областями из-за общей необходимости оценки родства последовательностей. [25] В области филогенетики выравнивание последовательностей широко используется при построении и интерпретации филогенетических деревьев , которые используются для классификации эволюционных отношений между гомологичными генами , представленными в геномах дивергентных видов. Степень различия последовательностей в наборе запросов качественно связана с эволюционным расстоянием последовательностей друг от друга. Грубо говоря, высокая идентичность последовательностей предполагает, что рассматриваемые последовательности имеют сравнительно молодого самого недавнего общего предка , тогда как низкая идентичность предполагает, что расхождение более древнее. Это приближение, которое отражает гипотезу « молекулярных часов », согласно которой примерно постоянная скорость эволюционных изменений может быть использована для экстраполяции времени, прошедшего с тех пор, как два гена впервые разошлись (то есть время слияния ), предполагает , что эффекты мутации и отбора константа во всех линиях последовательности. Следовательно, он не учитывает возможные различия между организмами или видами в скорости репарации ДНК или возможную функциональную консервативность определенных участков последовательности. (В случае нуклеотидных последовательностей гипотеза молекулярных часов в своей самой базовой форме также не учитывает разницу в скорости принятия между «молчащими» мутациями , которые не меняют значения данного кодона , и другими мутациями, которые приводят к включению в структуру другой аминокислоты). белок). Более статистически точные методы позволяют варьировать скорость эволюции на каждой ветви филогенетического дерева, что дает более точную оценку времени слияния генов.
Методы прогрессивного множественного выравнивания по необходимости создают филогенетическое дерево, поскольку они включают последовательности в растущее выравнивание в порядке родства. Другие методы, которые собирают множественные выравнивания последовательностей и филогенетические деревья, сначала оценивают и сортируют деревья, а затем вычисляют множественное выравнивание последовательностей на основе дерева с наивысшим баллом. Обычно используемые методы построения филогенетических деревьев в основном являются эвристическими, поскольку проблема выбора оптимального дерева, как и проблема выбора оптимального множественного выравнивания последовательностей, является NP-трудной . [26]
Выравнивание последовательностей полезно в биоинформатике для выявления сходства последовательностей, создания филогенетических деревьев и разработки моделей гомологии белковых структур. Однако биологическая значимость выравнивания последовательностей не всегда ясна. Часто предполагается, что выравнивание отражает степень эволюционных изменений между последовательностями, произошедшими от общего предка; однако формально возможно, что конвергентная эволюция может привести к очевидному сходству между белками, которые эволюционно неродственны, но выполняют сходные функции и имеют схожие структуры.
При поиске в базе данных, таком как BLAST, статистические методы могут определить вероятность того, что определенное выравнивание между последовательностями или областями последовательностей возникнет случайно, учитывая размер и состав базы данных, в которой осуществляется поиск. Эти значения могут существенно различаться в зависимости от пространства поиска. В частности, вероятность случайного обнаружения данного выравнивания увеличивается, если база данных состоит только из последовательностей из того же организма, что и запрашиваемая последовательность. Повторяющиеся последовательности в базе данных или запросе также могут исказить как результаты поиска, так и оценку статистической значимости; BLAST автоматически фильтрует такие повторяющиеся последовательности в запросе, чтобы избежать явных совпадений, которые являются статистическими артефактами.
Методы оценки статистической значимости выравниваний последовательностей с пробелами доступны в литературе. [25] [27] [28] [29] [30] [31] [32] [33]
Статистическая значимость указывает на вероятность того, что выравнивание данного качества могло возникнуть случайно, но не указывает, насколько данное выравнивание превосходит альтернативные выравнивания тех же последовательностей. Меры достоверности выравнивания указывают на степень, в которой наилучшие выравнивания для данной пары последовательностей по существу схожи. Методы оценки достоверности выравнивания для выравниваний последовательностей с пробелами доступны в литературе. [34]
Выбор оценочной функции, которая отражает биологические или статистические наблюдения над известными последовательностями, важен для получения хорошего выравнивания. Белковые последовательности часто выравниваются с использованием матриц замен , которые отражают вероятности данных замен между символами. Серия матриц, называемых матрицами PAM (матрицы точечных мутаций, первоначально определенные Маргарет Дэйхофф и иногда называемые «матрицами Дэйхоффа»), явно кодируют эволюционные приближения относительно скорости и вероятности определенных мутаций аминокислот. Другая распространенная серия оценочных матриц, известная как BLOSUM (матрица замены блоков), кодирует эмпирически полученные вероятности замены. Варианты матриц обоих типов используются для обнаружения последовательностей с разными уровнями расхождения, что позволяет пользователям BLAST или FASTA ограничивать поиск более близкими совпадениями или расширять поиск для обнаружения более расходящихся последовательностей. Штрафы за пробелы учитывают появление пробелов (согласно эволюционной модели, мутаций вставки или делеции) как в нуклеотидных, так и в белковых последовательностях, и поэтому значения штрафов должны быть пропорциональны ожидаемой частоте таких мутаций. Таким образом, качество полученных сопоставлений зависит от качества оценочной функции.
Может быть очень полезно и поучительно попробовать одно и то же выравнивание несколько раз с разными вариантами матрицы оценок и/или значений штрафа за пропуск и сравнить результаты. Области, в которых решение является слабым или неуникальным, часто можно определить, наблюдая, какие области выравнивания устойчивы к изменениям параметров выравнивания.
Секвенированные РНК, такие как экспрессированные метки последовательностей и полноразмерные мРНК, можно сопоставить с секвенированным геномом, чтобы определить, где находятся гены, и получить информацию об альтернативном сплайсинге [35] и редактировании РНК . [36] Выравнивание последовательностей также является частью сборки генома , при которой последовательности выравниваются для обнаружения перекрытия и формирования контигов (длинных участков последовательности). [37] Другим применением является анализ SNP , при котором последовательности от разных людей выравниваются, чтобы найти отдельные пары оснований, которые часто различаются в популяции. [38]
Методы, используемые для выравнивания биологических последовательностей, также нашли применение в других областях, особенно в обработке естественного языка и в социальных науках , где алгоритм Нидлмана-Вунша обычно называют оптимальным сопоставлением . [39] Методы, генерирующие набор элементов, из которых будут выбираться слова в алгоритмах генерации естественного языка, заимствовали множество методов выравнивания последовательностей из биоинформатики для создания лингвистических версий математических доказательств, сгенерированных компьютером . [40] В области исторической и сравнительной лингвистики выравнивание последовательностей использовалось для частичной автоматизации сравнительного метода , с помощью которого лингвисты традиционно реконструируют языки. [41] В бизнес- и маркетинговых исследованиях также применялись множественные методы выравнивания последовательностей при анализе серий покупок с течением времени. [42]
Более полный список доступного программного обеспечения, классифицированного по алгоритму и типу выравнивания, доступен на сайте «Программное обеспечение для выравнивания последовательностей» , но общие программные инструменты, используемые для общих задач выравнивания последовательностей, включают ClustalW2 [43] и T-coffee [44] для выравнивания, а также BLAST [45] и FASTA3x [46] для поиска в базе данных. Также доступны коммерческие инструменты, такие как DNASTAR Lasergene, Geneious и PatternHunter . Инструменты, помеченные как выполняющие выравнивание последовательностей, перечислены в реестре bio.tools.
Алгоритмы и программное обеспечение выравнивания можно напрямую сравнивать друг с другом с использованием стандартизированного набора эталонных эталонных выравниваний множественных последовательностей, известного как BAliBASE. [47] Набор данных состоит из структурных выравниваний, которые можно считать стандартом, с которым сравниваются методы, основанные исключительно на последовательностях. Относительная эффективность многих распространенных методов выравнивания при решении часто встречающихся проблем выравнивания сведена в таблицу, а отдельные результаты опубликованы на сайте BAliBASE. [48] [49] Полный список оценок BAliBASE для многих (на данный момент 12) различных инструментов выравнивания можно вычислить в инструментальном средстве STRAP для белков. [50]
{{cite book}}
: |journal=
игнорируется ( помощь ){{cite journal}}
: Требуется цитировать журнал |journal=
( помощь )