Штраф за пропуск

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

• 1 Приложения
• 2 Биоинформатические приложения
  • 2.1 Глобальное выравнивание
  • 2.2 Полуглобальное выравнивание
  • 2.3 Локальное выравнивание
  • 2.4 Матрица оценки
  • 2.5 Отступы
• 3 типа
  • 3.1 Константа
  • 3.2 Линейная
  • 3.3 Аффинная
  • 3.4 Выпуклая
  • 3.5 На основе профиля
• 4 Сравнение временных сложностей
• 5 Проблемы
• 6 Ссылки
  • 6.1 Дополнительная литература

• Выравнивание генетических последовательностей - В биоинформатике пробелы используются для учета генетических мутаций, происходящих из вставки или удаления в последовательности, иногда называемые вставками. Вставки или делеции могут происходить из-за единичных мутаций, несбалансированного кроссовера в мейозе, неправильного спаривания соскользнувшей нити и хромосомной транслокации. Понятие пробела в выравнивании важно во многих биологических приложениях, поскольку вставки или делеции включают всю подпоследовательность и часто возникают в результате одного мутационного события. Более того, единичные мутационные события могут создавать разрывы разного размера. Следовательно, при оценке пробелов необходимо оценивать в целом при выравнивании двух последовательностей ДНК. Рассмотрение нескольких пробелов в последовательности как большего одиночного пробела уменьшит приписывание высокой стоимости мутациям. Например, две белковые последовательности могут быть относительно похожими, но различаться через определенные интервалы, поскольку один белок может иметь разные субъединицы по сравнению с другим. Представление этих различных подпоследовательностей как пробелов позволит нам рассматривать эти случаи как «хорошие совпадения», даже если в последовательности есть длинные последовательные прогоны с операциями indel. Таким образом, использование хорошей модели штрафа за пробел позволит избежать низких оценок при выравнивании и повысит шансы найти истинное выравнивание. При выравнивании генетических последовательностей пробелы отображаются как тире (-) при выравнивании последовательности белок / ДНК.
• Unix diff функция - вычисляет минимальную разницу между двумя файлами аналогично обнаружению плагиата.
• Проверка орфографии - Штрафы за пропуск могут помочь найти правильно написанные слова с кратчайшим расстоянием редактирования до слова с ошибкой. Пробелы могут указывать на пропущенную букву в неправильно написанном слове.
• Обнаружение плагиата - Штрафы за пропуски позволяют алгоритмам обнаруживать плагиат разделов документа путем размещения пробелов в исходных разделах и сопоставления идентичных. Штраф за пробелы для определенного документа определяет, какая часть данного документа, вероятно, является оригинальной или является плагиатом.
• Распознавание речи

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

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

Полуглобальное выравнивание

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

Локальное выравнивание

Пример выравнивания белковой последовательности

Локальная последовательность выравнивание сопоставляет непрерывную часть одной последовательности с непрерывной частью другой. Алгоритм Смита-Уотермана основан на оценке совпадений и несоответствий. Совпадения увеличивают общую оценку выравнивания, тогда как несоответствия уменьшают оценку. Тогда хорошее выравнивание дает положительный результат, а плохое выравнивание - отрицательное. Локальный алгоритм находит выравнивание с наивысшей оценкой, рассматривая только те выравнивания, которые имеют положительный результат, и выбирая из них лучшее. Это алгоритм динамического программирования. При сравнении белков используется матрица сходства, в которой каждому возможному остатку присваивается оценка. Оценка должна быть положительной для одинаковых остатков и отрицательной для разнородной пары остатков. За пропуски обычно накладываются штрафные санкции с использованием линейной функции зазора, которая назначает начальный штраф за открытие зазора и дополнительный штраф за расширение зазора, увеличивая длину зазора.

Матрица оценки

Матрица Blosum-62

Матрицы замещения, такие как BLOSUM, используются для выравнивания последовательностей белков. Матрица замещения присваивает оценку выравниванию любой возможной пары остатков. В общем, разные матрицы замен предназначены для обнаружения сходства между последовательностями, которые отличаются в разной степени. Единая матрица может быть достаточно эффективной в относительно широком диапазоне эволюционных изменений. Матрица BLOSUM-62 - одна из лучших матриц замещения для обнаружения слабого сходства белков. Матрицы BLOSUM с большими числами предназначены для сравнения близкородственных последовательностей, а матрицы с низкими числами предназначены для сравнения отдаленных связанных последовательностей. Например, BLOSUM-80 используется для выравнивания, которые более похожи по последовательности, а BLOSUM-45 используется для выравниваний, которые расходятся друг от друга. Для особенно длинных и слабых выравниваний матрица BLOSUM-45 может обеспечить наилучшие результаты. Короткие выравнивания легче обнаружить с помощью матрицы с более высокой «относительной энтропией», чем у BLOSUM-62. Серия BLOSUM не включает никаких матриц с относительной энтропией, подходящей для кратчайших запросов.

Indels

Во время репликации ДНК механизм репликации склонен к созданию двух типов ошибки при дублировании ДНК. Эти две ошибки репликации представляют собой вставки и удаления отдельных оснований ДНК из цепи ДНК (инделки). Индели могут иметь серьезные биологические последствия, вызывая мутации в цепи ДНК, которые могут привести к инактивации или чрезмерной активации целевой белок. Например, если в кодирующей последовательности встречается один или два нуклеотида, результатом будет сдвиг рамки считывания или мутация сдвига рамки, которая может сделать белок неактивным. Биологические последствия инделек часто вредны и часто связаны с такими человеческими патологиями, как рак. Однако не все индели являются мутациями сдвига рамки считывания. Если в тринуклеотидах встречаются инделения, результатом является расширение белковой последовательности, которое также может иметь последствия для функции белка.

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

Константа

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

ATTGACCTGA || ||||| AT --- CCTGA

Выравнивание двух коротких последовательностей ДНК, где "-" обозначает разрыв в одну пару оснований. Если каждое совпадение приносило 1 очко, а весь разрыв равен -1, то общий балл: 7-1 = 6.

Линейный

По сравнению со штрафом за постоянный разрыв, штраф за линейный разрыв учитывается учитывать длину (L) каждой вставки / удаления в промежутке. Следовательно, если штраф за каждый вставленный / удаленный элемент равен B и длина промежутка L; общий штраф за разрыв будет произведением двух BL. Этот метод способствует более коротким пропускам, при этом общий балл уменьшается с каждым дополнительным пропуском.

ATTGACCTGA || ||||| AT --- CCTGA

В отличие от постоянного штрафа за пропуск, учитывается размер зазора. При матче со счетом 1 и каждым разрывом -1, здесь счет будет (7 - 3 = 4).

Аффинная функция

Самая широко используемая функция штрафа за пропуск - это штраф за аффинный разрыв. Штраф за аффинный разрыв объединяет компоненты как постоянного, так и линейного штрафа за разрыв, принимая форму $A\; +\; B\; \cdot \; L\; \{\backslash \; displaystyle\; A\; +\; B\; \backslash \; cdot\; L\}$. Это вводит новые термины: A известен как штраф за открытие промежутка, B штраф за удлинение промежутка и L длина промежутка. Открытие зазора относится к затратам, необходимым для открытия зазора любой длины, а расширение зазора - к стоимости увеличения длины существующего зазора на 1. Часто неясно, какими должны быть значения A и B, поскольку они различаются в зависимости от цель. В общем, если интерес заключается в поиске близких совпадений (например, удаление последовательности вектора во время секвенирования генома), следует использовать более высокий штраф за пропуски для уменьшения открытий пропусков. С другой стороны, штраф за разрыв следует уменьшить, если вы заинтересованы в поиске более отдаленного матча. Отношения между A и B также влияют на размер зазора. Если размер зазора важен, используются маленькие A и большие B (более дорогостоящие для увеличения зазора), и наоборот. Важно только соотношение A / B, так как умножение обоих на одну и ту же положительную константу k увеличит все штрафы на k: kA + kBL = k (A + BL), что не меняет относительный штраф между различными выравниваниями.

Выпуклый

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

Логарифмический пробел принимает форму $G\; (L)\; =\; A\; +\; C\; ln\; \; L\; \{\backslash \; displaystyle\; G\; (L)\; =\; A\; +\; C\; \backslash \; ln\; L\}$и был предложен, поскольку исследования показали, что распределение размеров отступов подчиняется степенному закону. Другой предлагаемой проблемой с использованием аффинных пробелов является предпочтение выравнивания последовательностей с более короткими пробелами. Штраф за логарифмический пробел был изобретен для изменения аффинного пробела так, что желательны длинные пробелы. Однако, в отличие от этого, было обнаружено, что использование логарифматических моделей привело к плохому выравниванию по сравнению с аффинными моделями.

Профильное

Алгоритмы выравнивания профиля-профиля являются мощными инструментами для обнаружения отношения гомологии белков с повышенной точностью выравнивания. Выравнивания профилей и профилей основаны на статистических профилях частоты отступов из множественных выравниваний последовательностей, полученных с помощью поиска PSI-BLAST. Вместо использования матриц замещения для измерения сходства пар аминокислот, методы выравнивания профиль-профиль требуют функции оценки на основе профиля для измерения сходства пар векторов профиля. При выравнивании профиля по профилю используются функции компенсации зазора. Информация о пропусках обычно используется в форме частотных профилей indel, которые более специфичны для выравниваемых последовательностей. ClustalW и MAFFT применили этот вид определения штрафа за разрыв для своих множественных выравниваний последовательностей. С помощью этой модели можно повысить точность выравнивания, особенно для белков с низкой идентичностью последовательностей. Некоторые алгоритмы выравнивания профиля и профиля также используют информацию о вторичной структуре в качестве одного члена в своих оценочных функциях, что повышает точность выравнивания.

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

Временные сложности для различных моделей штрафа за пропуск

Тип	Время
Штраф за постоянный зазор	O (мин)
Штраф за аффинный зазор	O (mn)
Штраф за выпуклый зазор	O (mn lg (m + n))

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

1. ^«Глоссарий». Розалинда. Команда Розалинда. Получено 11.09.14. Проверить значения дат в: | accessdate =()
2. ^Кэрролл, Ридж, Клемент, Снелл, Хайрам, Перри, Марк, Куинн (1 января, 2007). «Эффекты штрафов за открытие и продление пропусков» (PDF). Международный журнал исследований и приложений в области биоинформатики. Дата обращения 09.09.14. Проверить значения дат в: | accessdate =() CS1 maint: несколько имен: список авторов (ссылка )
3. ^ «Штраф за пробел» (PDF). Алгоритмы для молекулярной биологии. 2006-01 -01. Архивировано из исходного (PDF) 26.06.2013. Дата обращения 13.09.14. Проверить значения даты в: | access-date =( )
4. ^"Глоссарий". Rosalind. Rosalind Team. Получено 11.09.14. Проверить значения дат в: | accessdate =()
5. ^Lesk, Arthur M (2013-07-26). "bioinformatics". Encyclopdia Britannica. Encyclopdia Britannica. Проверено 12 сентября 2014 г.
6. ^Vingron, M.; Waterman, MS (1994). »Выравнивание последовательности и выбор наказания. Обзор концепций, тематические исследования. и последствия ". Журнал молекулярной биологии. 235 (1): 1–12. DOI : 10.1016 / S0022-2836 (05) 80006-3. PMID 8289235.
7. ^ «Матрицы замены BLAST». NCBI. Проверено 27 ноября 2012 г.
8. ^ Гарсия-Диас, Мигель (2006). «Механизм генетического глиссандо: структурная биология индел-мутаций». Направления биохимических наук. 31 (4): 206–214. doi : 10.1016 / j.tibs.2006.02.004. PMID 16545956.
9. ^«Глоссарий - штраф за постоянный пробел». Розалинда. Команда Розалинда. 12 августа 2014 г. Дата обращения 12 августа 2014 г.
10. ^ Hodgman C, French A, Westhead D (2009). BIOS Instant Notes в биоинформатике. Наука о гирляндах. С. 143–144. ISBN 978-0203967249.
11. ^«Глобальное согласование с оценочной матрицей и штраф за аффинный разрыв». Розалинда. Команда Розалинда. 07.02.2012. Проверено 12 сентября 2014 г. Проверьте значения даты в: | date =()
12. ^ Sung, Wing-Kin (2011). Алгоритмы в биоинформатике: практическое введение. CRC Press. Pp. 42–47. ISBN 978-1420070347.
13. ^ Картрайт, Рид (5/12/2006). «Стоимость логарифмического зазора снижает точность выравнивания». BMC Bioinformatics. 7 : 527. doi : 10.1186 / 1471-2105-7-527. PMC 1770940. PMID 17147805. Проверить значения даты в: | date =()
14. ^ Wang C, Yan RX, Wang XF, Si JN, Zhang Z (12 октября 2011 г.). «Сравнение штрафов за линейные зазоры и штрафов за переменные зазоры на основе профиля при выравнивании профиля по профилю». Comput Biol Chem. 35 (5): 308–318. doi : 10.1016 / j.compbiolchem.2011.07.006. PMID 22000802.
15. ^ Врабл Ю.О., Гришин Н.В. (1 января 2004 г.). «Пробелы в структурно сходных белках: к улучшению множественного выравнивания последовательностей». Proteins. 54 (1): 71–87. doi : 10.1002 / prot. 10508. PMID 14705025.

Дополнительная литература

• Taylor WR, Munro 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. ПМИД 8289235.
• Панюков В.В. (1993). «Нахождение устойчивых совпадений: сходство и расстояние». Comput Appl Biosci. 9 (3): 285–90. doi : 10.1093 / bioinformatics / 9.3.285. ПМИД 8324629.
• Александров Н.Н. (1992). «Локальное множественное согласование с помощью матрицы консенсуса». Comput Appl Biosci. 8 (4): 339–45. doi : 10.1093 / bioinformatics / 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 / bioinformatics / 5.2.141. PMID 2751764.
• Reich JG, Drabsch H, Daumler A (1984). «О статистической оценке сходства последовательностей ДНК». Nucleic Acids Res. 12 (13): 5529–43. DOI : 10.1093 / nar / 12.13.5529. PMC 318937. PMID 6462914.