Штраф за разрыв - Gap penalty

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

Приложения

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

Приложения биоинформатики

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

Основная статья: Алгоритм Нидлмана-Вунша

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

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

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

Местное выравнивание

Основная статья: Алгоритм Смита – Уотермана

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

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

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

Основная статья: Матрица замещения

Матрица Blosum-62

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

Indels

Основная статья: Indel

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

Типы

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

Постоянный

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

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

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

Линейный

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

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

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

Аффинный

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

Выпуклый

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

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

На основе профиля

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

Сравнение временных сложностей

Дальнейшая информация: Сложность времени

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

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

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

Вызовы

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

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

1. «Глоссарий». Розалинда. Команда Розалинд. Проверено 09.11.14. Проверить значения даты в: | accessdate = (помощь)
2. Кэрролл, Ридж, Клемент, Снелл, Хайрам, Перри, Марк, Куинн (1 января 2007 г.). «Последствия штрафов за открытие и продление пропуска» (PDF). Международный журнал исследований и приложений в области биоинформатики. Проверено 09.09.14. Проверить значения даты в: | accessdate = (помощь)
3. «Штраф за разрыв» (PDF). Алгоритмы молекулярной биологии. 2006-01-01. Архивировано из оригинал (PDF) на 2013-06-26. Проверено 13.09.14. Проверить значения даты в: | дата доступа = (помощь)
4. «Глоссарий». Розалинда. Команда Розалинд. Проверено 09.11.14. Проверить значения даты в: | accessdate = (помощь)
5. Леск, Артур М. (26.07.2013). «биоинформатика». Британская энциклопедия. Британская энциклопедия. Получено 2014-09-12.
6. Vingron, M .; Уотерман, М. С. (1994). «Выравнивание последовательности и выбор наказания. Обзор концепций, тематических исследований и последствий». Журнал молекулярной биологии. 235 (1): 1–12. Дои:10.1016 / S0022-2836 (05) 80006-3. PMID  8289235.
7. «Матрицы замещения BLAST». NCBI. Получено 2012-11-27.
8. Гарсия-Диас, Мигель (2006). «Механизм генетического глиссандо: структурная биология индел-мутаций». Тенденции в биохимических науках. 31 (4): 206–214. Дои:10.1016 / j.tibs.2006.02.004. PMID  16545956.
9. «Глоссарий - Штраф за постоянный разрыв». Розалинда. Команда Розалинда. 12 августа 2014 г.. Получено 12 августа 2014.
10. Hodgman C, French A, Westhead D (2009). Мгновенные заметки BIOS в биоинформатике. Наука о гирляндах. С. 143–144. ISBN  978-0203967249.
11. «Глобальное согласование с оценочной матрицей и штрафом за аффинный разрыв». Розалинда. Команда Розалинда. 07.02.2012. Получено 2014-09-12. Проверить значения даты в: | дата = (помощь)
12. Сун, Винг-Кин (2011). Алгоритмы в биоинформатике: практическое введение. CRC Press. С. 42–47. ISBN  978-1420070347.
13. Картрайт, Рид (5 декабря 2006 г.). «Стоимость логарифмического зазора снижает точность выравнивания». BMC Bioinformatics. 7: 527. Дои:10.1186/1471-2105-7-527. ЧВК  1770940. PMID  17147805. Проверить значения даты в: | дата = (помощь)
14. Ван Ц., Ян RX, Ван XF, Си Дж. Н., Чжан З. (12 октября 2011 г.). «Сравнение штрафов за линейные зазоры и штрафов за переменные зазоры на основе профиля при выравнивании профиля по профилю». Comput Biol Chem. 35 (5): 308–318. Дои:10.1016 / j.compbiolchem.2011.07.006. PMID  22000802.
15. Врабл Ю.О., Гришин Н.В. (1 января 2004 г.). «Пробелы в структурно подобных белках: к улучшению множественного выравнивания последовательностей». Белки. 54 (1): 71–87. Дои:10.1002 / prot.10508. PMID  14705025. S2CID  20474119.

дальнейшее чтение

• Тейлор WR, Манро RE (1997). "Многопоточность: условное размещение пробелов". Сложите Des. 2 (4): S33-9. Дои:10.1016 / S1359-0278 (97) 00061-8. PMID  9269566.
• Тейлор WR (1996). «Нелокальный штраф за зазор за выравнивание профиля». Бык математика биол. 58 (1): 1–18. Дои:10.1007 / BF02458279. PMID  8819751. S2CID  189884646.
• Вингрон М., Уотерман М.С. (1994). «Выравнивание последовательности и выбор наказания. Обзор концепций, тематических исследований и последствий». Дж Мол Биол. 235 (1): 1–12. Дои:10.1016 / S0022-2836 (05) 80006-3. PMID  8289235.
• Панюков В.В. (1993). «Нахождение устойчивых совпадений: сходство и расстояние». Comput Appl Biosci. 9 (3): 285–90. Дои:10.1093 / биоинформатика / 9.3.285. PMID  8324629.
• Александров Н.Н. (1992). «Локальное множественное согласование с помощью матрицы консенсуса». Comput Appl Biosci. 8 (4): 339–45. Дои:10.1093 / биоинформатика / 8.4.339. PMID  1498689.
• Хайн Дж (1989). «Новый метод, который одновременно выравнивает и реконструирует предковые последовательности для любого количества гомологичных последовательностей, когда задана филогения». Мол Биол Эвол. 6 (6): 649–68. Дои:10.1093 / oxfordjournals.molbev.a040577. PMID  2488477.
• Хеннеке CM (1989). «Алгоритм множественного выравнивания последовательностей для гомологичных белков с использованием информации о вторичной структуре и, возможно, ключевого выравнивания функционально важных сайтов». Comput Appl Biosci. 5 (2): 141–50. Дои:10.1093 / биоинформатика / 5.2.141. PMID  2751764.
• Райх JG, Drabsch H, Daumler A (1984). «О статистической оценке сходства последовательностей ДНК». Нуклеиновые кислоты Res. 12 (13): 5529–43. Дои:10.1093 / nar / 12.13.5529. ЧВК  318937. PMID  6462914.