Послушайте эту статью
Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Интерпретация [ править ]

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

Методы выравнивания [ править ]

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

Представления [ править ]

Ref. : GTCGTAGAATA
Чтение : CACGTAG - TA
CIGAR: 2S5M2D2M

где:
2S = 2 несоответствия
5M = 5 совпадений
2D = 2 удаления
2M = 2 совпадения


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

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

Глобальные и локальные выравнивания [ править ]

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

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

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

Попарное выравнивание [ править ]

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

Точечно-матричные методы [ править ]

Основная статья: Точечный график (биоинформатика)
Самостоятельное сравнение части генома линии мыши. Точечный график показывает мозаику линий, демонстрирующих дублированные сегменты ДНК.
ДНК точка участка в виде человеческого цинковых пальцев фактора транскрипции (GenBank ID NM_002383), показывающую региональное самоподобие . Основная диагональ представляет собой выравнивание последовательности с самой собой; линии от главной диагонали представляют собой похожие или повторяющиеся узоры в последовательности. Это типичный пример повторяющегося графика .

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

Проблемы с точечными графиками как методом отображения информации включают: шум, нечеткость, неинтуитивность, сложность извлечения сводной статистики совпадений и положения совпадений на двух последовательностях. Также существует много бесполезного места, где данные соответствия по своей природе дублируются по диагонали, и большая часть фактической области графика занята либо пустым пространством, либо шумом, и, наконец, точечные графики ограничены двумя последовательностями. Ни одно из этих ограничений не применяется к диаграммам выравнивания 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-полным задачам комбинаторной оптимизации. [8] [9] Тем не менее, использование этих выравниваний в биоинформатике привело к развитию множества методов, подходящих для выравнивания трех или более последовательностей.

Динамическое программирование [ править ]

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

Прогрессивные методы [ править ]

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

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

Итерационные методы [ править ]

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

Поиск мотивов [ править ]

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

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

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

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

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

Структурное выравнивание [ править ]

Основная статья: Структурное выравнивание

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

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

ДАЛИ [ править ]

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

SSAP [ править ]

SSAP (программа последовательного выравнивания структуры) - это метод структурного выравнивания, основанный на динамическом программировании, который использует в качестве точек сравнения векторы атом-атом в пространстве структуры. Он был расширен с момента своего первоначального описания, чтобы включить как множественные, так и попарные выравнивания [20], и был использован при построении иерархической классификации складок белков CATH (Класс, Архитектура, Топология, Гомология). [21] Доступ к базе данных CATH можно получить в классификации структуры белков CATH .

Комбинаторное расширение [ править ]

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

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

Основная статья: Вычислительная филогенетика

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

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

Оценка значимости [ править ]

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

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

В литературе доступны методы оценки статистической значимости выравнивания последовательностей с разрывом. [23] [25] [26] [27] [28] [29] [30] [31]

Оценка достоверности [ править ]

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

Функции подсчета очков [ править ]

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

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

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

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

Небиологические виды использования [ править ]

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

Программное обеспечение [ править ]

Основная статья: Программное обеспечение для выравнивания последовательностей

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

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

См. Также [ править ]

  • Гомология последовательностей
  • Последовательный майнинг
  • ВЗРЫВ
  • Алгоритм поиска строки
  • Анализ последовательности без выравнивания
  • UGENE
  • Алгоритм Нидлмана – Вунша

Ссылки [ править ]

  1. ^ a b c Установите DM. (2004). Биоинформатика: анализ последовательности и генома (2-е изд.). Пресса лаборатории Колд-Спринг-Харбор: Колд-Спринг-Харбор, Нью-Йорк. ISBN 978-0-87969-608-5.
  2. ^ "Clustal FAQ # Символы" . Clustal . Архивировано из оригинального 24 -го октября 2016 года . Проверено 8 декабря 2014 .
  3. ^ Ng PC; Хеникофф С (май 2001 г.). «Прогнозирование вредных аминокислотных замен» . Genome Res . 11 (5): 863–74. DOI : 10.1101 / gr.176601 . PMC 311071 . PMID 11337480 .  
  4. ^ а б Поляновский В.О. Ройтберг, Массачусетс; Туманян, В.Г. (2011). «Сравнительный анализ качества глобального алгоритма и локального алгоритма выравнивания двух последовательностей» . Алгоритмы молекулярной биологии . 6 (1): 25. DOI : 10,1186 / 1748-7188-6-25 . PMC 3223492 . PMID 22032267 . S2CID 2658261 .   
  5. ^ Шнайдер TD; Стивенс Р.М. (1990). «Логотипы последовательностей: новый способ отображения согласованных последовательностей» . Nucleic Acids Res . 18 (20): 6097–6100. DOI : 10.1093 / NAR / 18.20.6097 . PMC 332411 . PMID 2172928 .  
  6. ^ «Выравнивание последовательности / спецификация формата карты» (PDF) .
  7. ^ Брудно М; Malde S; Поляков А; Сделайте CB; Couronne O; Дубчак I; Бацоглу С (2003). «Глокальное выравнивание: поиск перестановок во время выравнивания» . Биоинформатика . 19. Дополнение 1 (90001): i54–62. DOI : 10.1093 / биоинформатики / btg1005 . PMID 12855437 . 
  8. ^ Ван Л; Цзян Т. (1994). «О сложности множественного выравнивания последовательностей». J Comput Biol . 1 (4): 337–48. CiteSeerX 10.1.1.408.894 . DOI : 10,1089 / cmb.1994.1.337 . PMID 8790475 .  
  9. ^ Элиас, Исаак (2006). «Урегулирование неразрешимости множественного выравнивания». J Comput Biol . 13 (7): 1323–1339. CiteSeerX 10.1.1.6.256 . DOI : 10,1089 / cmb.2006.13.1323 . PMID 17037961 .  
  10. ^ Lipman DJ; Альтшул С.Ф .; Kececioglu JD (1989). «Инструмент для множественного выравнивания последовательностей» . Proc Natl Acad Sci USA . 86 (12): 4412–5. Полномочный код : 1989PNAS ... 86.4412L . DOI : 10.1073 / pnas.86.12.4412 . PMC 287279 . PMID 2734293 .  
  11. Перейти ↑ Higgins DG , Sharp PM (1988). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–44. DOI : 10.1016 / 0378-1119 (88) 90330-7 . PMID 3243435 . 
  12. ^ Томпсон JD; Хиггинс Д.Г .; Гибсон Т.Дж. (1994). «CLUSTAL W: повышение чувствительности прогрессивного множественного выравнивания последовательностей за счет взвешивания последовательностей, штрафов за пропуски в зависимости от позиции и выбора матрицы весов» . Nucleic Acids Res . 22 (22): 4673–80. DOI : 10.1093 / NAR / 22.22.4673 . PMC 308517 . PMID 7984417 .  
  13. ^ Ченна R; Sugawara H; Koike T; Lopez R; Гибсон Т.Дж.; Хиггинс Д.Г.; Томпсон JD. (2003). «Множественное выравнивание последовательностей с помощью программ серии Clustal» . Nucleic Acids Res . 31 (13): 3497–500. DOI : 10.1093 / NAR / gkg500 . PMC 168907 . PMID 12824352 .  
  14. ^ Notredame C; Хиггинс Д.Г .; Херинга Дж. (2000). «T-Coffee: новый метод быстрого и точного выравнивания множественных последовательностей» . J Mol Biol . 302 (1): 205–17. DOI : 10.1006 / jmbi.2000.4042 . PMID 10964570 . S2CID 10189971 .  
  15. ^ Хиросава М; Totoki Y; Hoshida M; Исикава М. (1995). «Комплексное исследование итерационных алгоритмов множественного выравнивания последовательностей» . Comput Appl Biosci . 11 (1): 13–8. DOI : 10.1093 / биоинформатики / 11.1.13 . PMID 7796270 . 
  16. ^ Karplus K; Barrett C; Хьюи Р. (1998). «Скрытые марковские модели для обнаружения удаленных гомологий белков» . Биоинформатика . 14 (10): 846–856. DOI : 10.1093 / биоинформатики / 14.10.846 . PMID 9927713 . 
  17. ^ Chothia C; Леск AM. (Апрель 1986 г.). «Связь между расхождением последовательности и структуры в белках» . EMBO J . 5 (4): 823–6. DOI : 10.1002 / j.1460-2075.1986.tb04288.x . PMC 1166865 . PMID 3709526 .  
  18. ^ а б Чжан И; Сколник Дж. (2005). «Проблема предсказания структуры белка может быть решена с использованием текущей библиотеки PDB» . Proc Natl Acad Sci USA . 102 (4): 1029–34. Bibcode : 2005PNAS..102.1029Z . DOI : 10.1073 / pnas.0407152101 . PMC 545829 . PMID 15653774 .  
  19. ^ Holm L; Сандер С. (1996). «Картирование белковой вселенной» . Наука . 273 (5275): 595–603. Bibcode : 1996Sci ... 273..595H . DOI : 10.1126 / science.273.5275.595 . PMID 8662544 . S2CID 7509134 .  
  20. ^ Тейлор WR; Флорес ТП; Оренго CA. (1994). «Множественное выравнивание структуры белка» . Protein Sci . 3 (10): 1858–70. DOI : 10.1002 / pro.5560031025 . PMC 2142613 . PMID 7849601 .  [ постоянная мертвая ссылка ]
  21. ^ Оренго CA; Michie AD; Джонс С; Jones DT; Swindells MB; Торнтон Дж. М. (1997). «CATH - иерархическая классификация доменных структур белков». Структура . 5 (8): 1093–108. DOI : 10.1016 / S0969-2126 (97) 00260-8 . PMID 9309224 . 
  22. ^ Шиндялов И.Н.; Bourne PE. (1998). «Выравнивание структуры белка путем инкрементального комбинаторного удлинения (CE) оптимального пути» . Protein Eng . 11 (9): 739–47. DOI : 10,1093 / белок / 11.9.739 . PMID 9796821 . 
  23. ^ a b Ortet P; Бастьен О. (2010). "Откуда взялась форма распределения оценок выравнивания?" . Эволюционная биоинформатика . 6 : 159–187. DOI : 10.4137 / EBO.S5875 . PMC 3023300 . PMID 21258650 .  
  24. ^ Фельзенштейн J. (2004). Вывод филогении . Sinauer Associates: Сандерленд, Массачусетс. ISBN 978-0-87893-177-4.
  25. ^ Altschul SF; Гиш В. (1996). Статистика местного выравнивания . Meth.Enz . Методы в энзимологии. 266 . С. 460–480. DOI : 10.1016 / S0076-6879 (96) 66029-7 . ISBN 9780121821678. PMID  8743700 .
  26. Перейти ↑ 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 .  
  27. ^ Нюберг LA (2008). «Значение выравнивания последовательностей с разрывом» . J Comput Biol . 15 (9): 1187–1194. DOI : 10,1089 / cmb.2008.0125 . PMC 2737730 . PMID 18973434 .  
  28. ^ Эдди SR; Рост, Буркхард (2008). Рост, Буркхард (ред.). «Вероятностная модель локального выравнивания последовательностей, упрощающая оценку статистической значимости» . PLOS Comput Biol . 4 (5): e1000069. Bibcode : 2008PLSCB ... 4E0069E . DOI : 10.1371 / journal.pcbi.1000069 . PMC 2396288 . PMID 18516236 . S2CID 15640896 .   
  29. ^ Бастьен О; Aude JC; Рой С; Marechal E (2004). «Основы массового автоматического попарного выравнивания последовательностей белков: теоретическое значение статистики Z-значения» . Биоинформатика . 20 (4): 534–537. DOI : 10.1093 / биоинформатики / btg440 . PMID 14990449 . 
  30. ^ Agrawal A; Хуан X (2011). «Парная статистическая значимость локального выравнивания последовательностей с использованием матриц замещения, специфичных для последовательностей и позиций» . Протоколы IEEE / ACM по вычислительной биологии и биоинформатике . 8 (1): 194–205. DOI : 10.1109 / TCBB.2009.69 . PMID 21071807 . S2CID 6559731 .  
  31. ^ Agrawal A; Брендель В.П .; Хуан X (2008). «Попарная статистическая значимость и эмпирическое определение эффективных штрафов за открытие разрыва для локального выравнивания последовательности белка» . Международный журнал вычислительной биологии и дизайна лекарств . 1 (4): 347–367. DOI : 10.1504 / IJCBDD.2008.022207 . PMID 20063463 . Архивировано из оригинального 28 января 2013 года . 
  32. ^ Ньюберг Л.А.; Лоуренс CE (2009). «Точный расчет распределений по целым числам с применением для выравнивания последовательности» . J Comput Biol . 16 (1): 1–18. DOI : 10,1089 / cmb.2008.0137 . PMC 2858568 . PMID 19119992 .  
  33. ^ Ким Н; Ли С. (2008). Биоинформатика обнаружения альтернативного сплайсинга . Методы Мол. Биол . Методы молекулярной биологии ™. 452 . С. 179–97. DOI : 10.1007 / 978-1-60327-159-2_9 . ISBN 978-1-58829-707-5. PMID  18566765 .
  34. ^ Li JB, Levanon EY, Yoon JK и др. (Май 2009 г.). «Полногеномная идентификация сайтов редактирования РНК человека путем параллельного захвата ДНК и секвенирования» . Наука . 324 (5931): 1210–3. Bibcode : 2009Sci ... 324.1210L . DOI : 10.1126 / science.1170995 . PMID 19478186 . S2CID 31148824 .  
  35. ^ Blazewicz J, Bryja M, Figlerowicz M, et al. (Июнь 2009 г.). «Сборка всего генома из результатов секвенирования 454 с использованием модифицированной концепции графа ДНК». Comput Biol Chem . 33 (3): 224–30. DOI : 10.1016 / j.compbiolchem.2009.04.005 . PMID 19477687 . 
  36. ^ Duran C; Appleby N; Варды М; Имелфорт М; Эдвардс Д; Бэтли Дж. (Май 2009 г.). «Открытие однонуклеотидного полиморфизма ячменя с помощью autoSNPdb» . Plant Biotechnol. Дж . 7 (4): 326–33. DOI : 10.1111 / j.1467-7652.2009.00407.x . PMID 19386041 . 
  37. ^ Abbott A .; Цай А. (2000). «Последовательный анализ и методы оптимального сопоставления в социологии, обзоре и перспективах». Социологические методы и исследования . 29 (1): 3–33. DOI : 10.1177 / 0049124100029001001 . S2CID 121097811 . 
  38. ^ Barzilay R; Ли Л. (2002). «Лексический выбор начальной загрузки с помощью многопоследовательного выравнивания» (PDF) . Труды конференции по эмпирическим методам обработки естественного языка (EMNLP) . 10 : 164–171. arXiv : cs / 0205065 . Bibcode : 2002cs ........ 5065B . DOI : 10.3115 / 1118693.1118715 . S2CID 7521453 .  
  39. ^ Kondrak, Гжегож (2002). «Алгоритмы реконструкции языка» (PDF) . Университет Торонто, Онтарио. Архивировано из оригинального (PDF) 17 декабря 2008 года . Проверено 21 января 2007 года . Цитировать журнал требует |journal=( помощь )
  40. ^ Prinzie A .; Д. Ван ден Поэль (2006). «Включение последовательной информации в традиционные модели классификации с помощью чувствительного к элементу / позиции SAM» . Системы поддержки принятия решений . 42 (2): 508–526. DOI : 10.1016 / j.dss.2005.02.004 .См. Также статью Принци и Ван ден Поэль Prinzie, A; Ванденпол, Д. (2007). «Прогнозирование последовательностей приобретения бытовой техники: Марков / Марков для анализа дискриминации и выживания для моделирования последовательной информации в моделях NPTB» . Системы поддержки принятия решений . 44 (1): 28–45. DOI : 10.1016 / j.dss.2007.02.008 .
  41. ^ EMBL-EBI. «ClustalW2 <Выравнивание множественных последовательностей <EMBL-EBI» . www.EBI.ac.uk . Дата обращения 12 июня 2017 .
  42. ^ Т-кофе
  43. ^ «BLAST: Базовый инструмент поиска местного выравнивания» . blast.ncbi.nlm.NIH.gov . Дата обращения 12 июня 2017 .
  44. ^ "Сервер UVA FASTA" . fasta.bioch.Virginia.edu . Дата обращения 12 июня 2017 .
  45. ^ Томпсон JD; Plewniak F; Почта О (1999). «BAliBASE: эталонная база данных по выравниванию для оценки нескольких программ выравнивания» . Биоинформатика . 15 (1): 87–8. DOI : 10.1093 / биоинформатики / 15.1.87 . PMID 10068696 . 
  46. ^ BAliBASE
  47. ^ Томпсон JD; Plewniak F; Поч О. (1999). «Комплексное сравнение нескольких программ выравнивания последовательностей» . Nucleic Acids Res . 27 (13): 2682–90. DOI : 10.1093 / NAR / 27.13.2682 . PMC 148477 . PMID 10373585 .  
  48. ^ «Множественное выравнивание последовательностей: планка» . 3d-alignment.eu . Дата обращения 12 июня 2017 .

Внешние ссылки [ править ]

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