Гэпа представляет собой методы балльного выравнивание двух или более последовательностей. При выравнивании последовательностей введение пробелов в последовательностях может позволить алгоритму выравнивания соответствовать большему количеству терминов, чем выравнивание без пробелов. Однако минимизация зазоров в трассе важна для создания полезной трассы. Слишком много пробелов может сделать выравнивание бессмысленным. Штрафы за пропуски используются для корректировки оценок выравнивания в зависимости от количества и длины пропусков. Пять основных типов штрафов за пробелы: постоянные, линейные, аффинные, выпуклые и профильные. [1]
Приложения
- Выравнивание генетических последовательностей - в биоинформатике пробелы используются для учета генетических мутаций, возникающих из-за вставок или делеций в последовательности, иногда называемых инделениями . Вставки или делеции могут происходить из-за одиночных мутаций, несбалансированного кроссовера в мейозе , неправильного спаривания цепи и хромосомной транслокации . [2] Понятие пробела в выравнивании важно во многих биологических приложениях, поскольку вставки или делеции включают всю субпоследовательность и часто возникают в результате одного мутационного события. [3] Более того, единичные мутационные события могут создавать разрывы разного размера. Следовательно, при подсчете баллов необходимо оценивать пропуски в целом при выравнивании двух последовательностей ДНК. Рассмотрение нескольких пробелов в последовательности как большего одиночного пробела снизит приписывание высокой стоимости мутациям. Например, две белковые последовательности могут быть относительно похожими, но различаться через определенные промежутки времени, поскольку один белок может иметь разные субъединицы по сравнению с другим. Представление этих различных подпоследовательностей как пробелов позволит нам рассматривать эти случаи как «хорошие совпадения», даже если в последовательности есть длинные последовательные прогоны с операциями indel. Следовательно, использование хорошей модели штрафа за пробелы позволит избежать низких оценок в выравниваниях и повысит шансы нахождения истинного выравнивания. [3] При выравнивании генетических последовательностей пробелы представлены штрихами (-) при выравнивании последовательностей белок / ДНК. [1]
- Функция Unix diff - вычисляет минимальную разницу между двумя файлами аналогично обнаружению плагиата.
- Проверка орфографии - штрафы за пропуски могут помочь найти правильно написанные слова с кратчайшим расстоянием редактирования до слова с ошибкой. Пробелы могут указывать на пропущенную букву в неправильно написанном слове.
- Обнаружение плагиата - штрафы за пропуски позволяют алгоритмам определять, где разделы документа являются плагиатом, путем размещения пропусков в исходных разделах и сопоставления того, что является идентичным. Штраф за пробелы для определенного документа определяет, какая часть данного документа, вероятно, является оригинальной или является плагиатом.
Приложения биоинформатики
Глобальное выравнивание
Глобальное выравнивание выполняет сквозное выравнивание запрашиваемой последовательности с эталонной последовательностью. В идеале этот метод выравнивания наиболее подходит для близкородственных последовательностей одинаковой длины. Алгоритм Нидлмана-Вунша - это метод динамического программирования , используемый для глобального выравнивания. По сути, алгоритм делит проблему на набор подзадач, а затем использует результаты подзадач для восстановления решения исходного запроса. [4]
Полуглобальное выравнивание
Полуглобальное выравнивание используется для поиска конкретного совпадения в большой последовательности. Пример включает поиск промоторов в последовательности ДНК. В отличие от глобального выравнивания, оно не допускает отсутствия концевых разрывов в одной или обеих последовательностях. Если концевые пробелы наказываются в одной последовательности 1, но не в последовательности 2, это дает выравнивание, которое содержит последовательность 2 в последовательности 1.
Местное выравнивание
Локальное выравнивание последовательностей сопоставляет непрерывную часть одной последовательности с непрерывной частью другой. [5] Алгоритм Смита-Уотермана основан на оценке совпадений и несоответствий. Совпадения увеличивают общую оценку выравнивания, тогда как несоответствия уменьшают оценку. Тогда хорошее выравнивание дает положительный результат, а плохое выравнивание - отрицательное. Локальный алгоритм находит выравнивание с наивысшей оценкой, рассматривая только те выравнивания, которые имеют положительный результат, и выбирая из них лучшее. Алгоритм представляет собой алгоритм динамического программирования . При сравнении белков используется матрица сходства, в которой каждому возможному остатку присваивается оценка. Оценка должна быть положительной для одинаковых остатков и отрицательной для разнородной пары остатков. За пропуски обычно накладываются штрафы с использованием линейной функции зазора, которая назначает начальный штраф за открытие зазора и дополнительный штраф за расширение зазора, увеличивая длину зазора.
Матрица оценок
Матрицы замещения, такие как BLOSUM , используются для выравнивания последовательностей белков. [6] Матрица замещения присваивает оценку выравниванию любой возможной пары остатков. [6] В общем, разные матрицы замен предназначены для обнаружения сходства между последовательностями, которые отличаются в разной степени. Одна матрица может быть достаточно эффективной в относительно широком диапазоне эволюционных изменений. [6] Матрица BLOSUM-62 - одна из лучших матриц замещения для обнаружения слабого сходства белков. [6] Матрицы BLOSUM с большими числами предназначены для сравнения близкородственных последовательностей, тогда как матрицы с низкими числами предназначены для сравнения отдаленных связанных последовательностей. Например, BLOSUM-80 используется для выравниваний, которые более похожи по последовательности, а BLOSUM-45 используется для выравниваний, которые расходятся друг от друга. [6] Для особенно длинных и слабых выравниваний матрица BLOSUM-45 может обеспечить наилучшие результаты. Короткие выравнивания легче обнаружить с помощью матрицы с более высокой «относительной энтропией», чем у BLOSUM-62. Серия BLOSUM не включает никаких матриц с относительной энтропией, подходящих для самых коротких запросов. [6]
Indels
Во время репликации ДНК репликационный аппарат склонен делать два типа ошибок при дублировании ДНК. Эти две ошибки репликации представляют собой вставки и удаления отдельных оснований ДНК из цепи ДНК (инделки). [7] Индели могут иметь серьезные биологические последствия, вызывая мутации в цепи ДНК, которые могут привести к инактивации или чрезмерной активации целевого белка. Например, если в кодирующей последовательности встречается один или два нуклеотида, результатом будет сдвиг рамки считывания или мутация сдвига рамки считывания, которая может сделать белок неактивным. [7] Биологические последствия инделей часто пагубны и часто связаны с такими человеческими патологиями, как рак . Однако не все индели являются мутациями со сдвигом рамки считывания. Если индели встречаются в тринуклеотидах, результатом является удлинение белковой последовательности, что также может иметь последствия для функции белка. [7]
Типы
Постоянный
Это простейший вид штрафа за пропуск: фиксированная отрицательная оценка присваивается каждому пропуску, независимо от его длины. [3] [8] Это побуждает алгоритм делать меньшее количество больших промежутков, оставляя более крупные смежные участки.
ATTGACCTGA|| |||||AT --- CCTGA
Выравнивание двух коротких последовательностей ДНК с знаком «-», обозначающим разрыв в одну пару оснований. Если каждый матч стоил 1 очко, а весь разрыв -1, общий счет: 7 - 1 = 6.
Линейный
По сравнению со штрафом за постоянный разрыв, штраф за линейный разрыв учитывает длину (L) каждой вставки / удаления в промежутке. Следовательно, если штраф за каждый вставленный / удаленный элемент равен B и длина промежутка L; общий штраф за разрыв будет произведением двух BL. [9] Этот метод поддерживает более короткие промежутки, при этом общий балл уменьшается с каждым дополнительным промежутком.
ATTGACCTGA|| |||||AT --- CCTGA
В отличие от штрафа за постоянный зазор, учитывается размер зазора. При матче со счетом 1 и каждым разрывом -1, здесь счет будет (7 - 3 = 4).
Аффинный
Наиболее широко используемая функция штрафа за пропуск - это штраф за аффинный разрыв. Штраф за аффинный пробел объединяет компоненты как постоянного, так и линейного штрафа за пропуск, принимая форму. Это вводит новые термины: A известен как штраф за открытие промежутка, B штраф за расширение промежутка и L длина промежутка. Открытие зазора относится к затратам, необходимым для открытия зазора любой длины, а расширение зазора - к затратам на увеличение длины существующего зазора на 1. [10] Часто неясно, какими должны быть значения A и B. различается в зависимости от цели. В общем, если интерес заключается в поиске близких совпадений (например, удаление последовательности вектора во время секвенирования генома), следует использовать более высокий штраф за пропуски для уменьшения открытий пропусков. С другой стороны, штраф за разрыв следует уменьшить, если вы заинтересованы в поиске более отдаленного матча. [9] Соотношение между A и B также влияет на размер зазора. Если размер зазора важен, используются маленькие A и большие B (более дорогостоящие для увеличения зазора), и наоборот. Важно только соотношение A / B, так как умножение обоих на одну и ту же положительную константу k увеличит все штрафы на k: kA + kBL = k (A + BL), что не изменит относительный штраф между различными выравниваниями.
Выпуклый
Использование аффинного штрафа за разрыв требует присвоения фиксированных значений штрафа как за открытие, так и за расширение промежутка. Это может быть слишком жестким для использования в биологическом контексте. [11]
Логарифмический зазор принимает вид и был предложен, поскольку исследования показали, что распределение размеров отступов подчиняется степенному закону. [12] Другой предложенной проблемой с использованием аффинных пробелов является предпочтение выравнивания последовательностей с более короткими пробелами. Штраф за логарифмический пробел был изобретен, чтобы модифицировать аффинный пробел так, чтобы желательны длинные пробелы. [11] Однако, в отличие от этого, было обнаружено, что использование логарифматических моделей привело к плохому согласованию по сравнению с аффинными моделями. [12]
На основе профиля
Алгоритмы профильного выравнивания являются мощными инструментами для обнаружения гомологических отношений белков с повышенной точностью выравнивания. [13] Выравнивание профиля-профиля основано на статистических профилях частоты отступов из нескольких выравниваний последовательностей, полученных с помощью поиска PSI-BLAST. [13] Вместо использования матриц замещения для измерения сходства пар аминокислот, методы выравнивания профиль-профиль требуют функции оценки на основе профиля для измерения сходства пар векторов профиля. [13] При выравнивании профиля по профилю используются функции компенсации зазора. Информация о пропусках обычно используется в форме частотных профилей indel, которые более специфичны для выравниваемых последовательностей. ClustalW и MAFFT применили этот вид определения штрафа за разрыв для своих множественных выравниваний последовательностей. [13] С помощью этой модели можно повысить точность выравнивания, особенно для белков с низкой идентичностью последовательностей. Некоторые алгоритмы выравнивания профиля и профиля также обрабатывают информацию о вторичной структуре как один член в своих оценочных функциях, что повышает точность выравнивания. [13]
Сравнение временных сложностей
Использование выравнивания в вычислительной биологии часто включает последовательности различной длины. Важно выбрать модель, которая будет эффективно работать при известном входном размере. Время, необходимое для запуска алгоритма, называется временной сложностью.
Тип | Время |
---|---|
Штраф за постоянный разрыв | O (мин) |
Штраф за аффинный пробел | O (мин) |
Штраф за выпуклый зазор | О (мн lg (m + n)) |
Вызовы
Когда дело доходит до работы с пробелами, возникает несколько проблем. При работе с популярными алгоритмами кажется, что существует мало теоретических оснований для вида функций штрафа за пропуски. [14] Следовательно, для любой ситуации выравнивания размещение зазора должно быть определено эмпирически. [14] Кроме того, штрафы за пробелы в парном выравнивании, такие как штраф за аффинные пробелы, часто реализуются независимо от типов аминокислот во вставленном или удаленном фрагменте или на разорванных концах, несмотря на доказательства того, что определенные типы остатков предпочтительны в областях пробела. [14] Наконец, выравнивание последовательностей подразумевает выравнивание соответствующих структур, но взаимосвязь между структурными особенностями разрывов в белках и их соответствующими последовательностями известна лишь частично. Из-за этого сложно включить структурную информацию в штрафы за пробелы. [14] Некоторые алгоритмы используют прогнозируемую или фактическую структурную информацию, чтобы смещать размещение зазоров. Однако лишь небольшая часть последовательностей имеет известные структуры, и большинство проблем выравнивания связано с последовательностями с неизвестной вторичной и третичной структурой. [14]
Рекомендации
- ^ a b «Глоссарий» . Розалинда . Команда Розалинда . Проверено 20 мая 20 .
- ^ Кэрролл, Ридж, Клемент, Снелл, Хайрам, Перри, Марк, Куинн (1 января 2007 г.). «Эффекты штрафов за открытие и продление пропусков» (PDF) . Международный журнал исследований и приложений в области биоинформатики . Проверено 9 сентября 2014 .CS1 maint: несколько имен: список авторов ( ссылка )
- ^ а б в «Штраф за пропуск» (PDF) . Алгоритмы молекулярной биологии . 2006-01-01. Архивировано из оригинального (PDF) 26 июня 2013 года . Проверено 13 сентября 2014 .
- ^ Леск, Артур М. (26.07.2013). «биоинформатика» . Британская энциклопедия . Британская энциклопедия . Проверено 12 сентября 2014 .
- ^ Vingron, M .; Уотерман, MS (1994). «Выравнивание последовательности и выбор наказания. Обзор концепций, тематических исследований и последствий». Журнал молекулярной биологии . 235 (1): 1–12. DOI : 10.1016 / S0022-2836 (05) 80006-3 . PMID 8289235 .
- ^ а б в г д е «Матрицы замещения BLAST» . NCBI . Проверено 27 ноября 2012 .
- ^ а б в Гарсия-Диас, Мигель (2006). «Механизм генетического глиссандо: структурная биология индел-мутаций». Направления биохимических наук . 31 (4): 206–214. DOI : 10.1016 / j.tibs.2006.02.004 . PMID 16545956 .
- ^ «Глоссарий - Штраф за постоянный разрыв» . Розалинда . Команда Розалинда. 12 август 2014 . Проверено 12 августа 2014 .
- ^ а б Hodgman C, French A, Westhead D (2009). BIOS Instant Notes в биоинформатике . Наука о гирляндах. С. 143–144. ISBN 978-0203967249.
- ^ «Глобальное выравнивание с оценочной матрицей и штрафом за аффинный разрыв» . Розалинда . Команда Розалинда. 2012-07-02 . Проверено 12 сентября 2014 .
- ^ а б Сун, Винг-Кин (2011). Алгоритмы в биоинформатике: практическое введение . CRC Press. С. 42–47. ISBN 978-1420070347.
- ^ а б Картрайт, Рид (05.12.2006). «Стоимость логарифмического разрыва снижает точность выравнивания» . BMC Bioinformatics . 7 : 527. DOI : 10,1186 / 1471-2105-7-527 . PMC 1770940 . PMID 17147805 .
- ^ а б в г д Ван Ц., Ян RX, Ван XF, Си Дж. Н., Чжан З. (12 октября 2011 г.). «Сравнение штрафов за линейные зазоры и штрафов за переменные зазоры на основе профиля при выравнивании профиля по профилю». Comput Biol Chem . 35 (5): 308–318. DOI : 10.1016 / j.compbiolchem.2011.07.006 . PMID 22000802 .
- ^ а б в г д Врабл Ю.О., Гришин Н.В. (1 января 2004 г.). «Пробелы в структурно подобных белках: к улучшению множественного выравнивания последовательностей». Белки . 54 (1): 71–87. DOI : 10.1002 / prot.10508 . PMID 14705025 . S2CID 20474119 .
дальнейшее чтение
- Тейлор WR, Манро RE (1997). «Многопоточность: размещение условных пробелов» . Сложите Des . 2 (4): S33-9. DOI : 10.1016 / S1359-0278 (97) 00061-8 . PMID 9269566 .
- Тейлор WR (1996). «Штраф за нелокальный разрыв за выравнивание профиля». Bull Math Biol . 58 (1): 1–18. DOI : 10.1007 / BF02458279 . PMID 8819751 . S2CID 189884646 .
- Вингрон М., Уотерман М.С. (1994). «Выравнивание последовательности и выбор наказания. Обзор концепций, тематических исследований и последствий». J Mol Biol . 235 (1): 1–12. DOI : 10.1016 / S0022-2836 (05) 80006-3 . PMID 8289235 .
- Панюков В.В. (1993). «В поисках устойчивых совпадений: сходство и расстояние». Comput Appl Biosci . 9 (3): 285–90. DOI : 10.1093 / биоинформатики / 9.3.285 . PMID 8324629 .
- Александров Н.Н. (1992). «Локальное множественное выравнивание по матрице консенсуса». Comput Appl Biosci . 8 (4): 339–45. DOI : 10.1093 / биоинформатики / 8.4.339 . PMID 1498689 .
- Хайн Дж (1989). «Новый метод, который одновременно выравнивает и реконструирует предковые последовательности для любого количества гомологичных последовательностей, когда дана филогения» . Mol Biol Evol . 6 (6): 649–68. DOI : 10.1093 / oxfordjournals.molbev.a040577 . PMID 2488477 .
- Хеннеке CM (1989). «Алгоритм множественного выравнивания последовательностей для гомологичных белков с использованием информации о вторичной структуре и, возможно, ключевого выравнивания по функционально важным сайтам». Comput Appl Biosci . 5 (2): 141–50. DOI : 10.1093 / биоинформатики / 5.2.141 . PMID 2751764 .
- Райх Дж. Г., Драбш Х, Даумлер А (1984). «О статистической оценке сходства последовательностей ДНК» . Nucleic Acids Res . 12 (13): 5529–43. DOI : 10.1093 / NAR / 12.13.5529 . PMC 318937 . PMID 6462914 .