Введение
Штраф за гэп (пробел) – это метод оценки выравнивания двух или более последовательностей. При выравнивании последовательностей, введение гэпов (пробелов) в последовательности может позволить алгоритму выравнивания найти больше совпадений, чем при выравнивании без гэпов. Однако, минимизация гэпов (пробелов) в выравнивании важна для получения значимого результата. Слишком большое количество гэпов (пробелов) может сделать выравнивание бессмысленным. Штрафы за гэпы (пробелы) используются для корректировки оценок выравнивания в зависимости от количества и длины гэпов (пробелов). Основные типы штрафов за гэпы (пробелы) включают постоянные, линейные, аффинные, выпуклые и профильные.
Приложения
В биоинформатике пробелы используются для учета генетических мутаций, возникающих в результате вставок или делеций в последовательности, которые иногда называют инделами. Вставки или делеции могут возникать из-за отдельных мутаций, несбалансированного кроссинговера в мейозе, ошибок спаривания скользящих цепей и хромосомных транслокаций. Понятие пробела при выравнивании важно для многих биологических приложений, поскольку вставки или делеции охватывают целую подпоследовательность и часто являются результатом единичного мутационного события. Более того, отдельные мутационные события могут создавать пробелы разного размера. Поэтому при расчете оценок пробелы необходимо учитывать как единое целое при выравнивании двух последовательностей ДНК. Рассмотрение нескольких пробелов в последовательности как одного большого пробела позволит снизить высокую стоимость, приписываемую мутациям. Например, две последовательности белков могут быть относительно похожи, но отличаться в определенных интервалах, поскольку один белок может иметь другую субъединицу по сравнению с другим. Представление этих различных подпоследовательностей в виде пробелов позволит рассматривать такие случаи как «хорошие совпадения», даже если в последовательности присутствуют длинные последовательные участки с операциями вставки-делеции. Следовательно, использование хорошей модели штрафов за пробелы позволит избежать низких оценок при выравнивании и повысить вероятность нахождения истинного выравнивания.
Полуглобальное выравнивание
Использование полуглобального выравнивания предназначено для поиска конкретного соответствия в большой последовательности. Примером может служить поиск промоторов в последовательности ДНК. В отличие от глобального выравнивания, оно не предусматривает штрафов за пробелы в начале или конце одной или обеих последовательностей. Если штраф за пробелы в начале или конце применяется только к последовательности 1, а не к последовательности 2, то результатом будет выравнивание, в котором последовательность 2 содержится внутри последовательности 1.
Местное выравнивание
Локальное выравнивание последовательностей сопоставляет непрерывный участок одной последовательности с непрерывным участком другой. Алгоритм Смита-Уотермана основан на присвоении баллов за совпадения и несовпадения. Совпадения повышают общий балл выравнивания, а несовпадения – понижают. Хорошее выравнивание имеет положительный балл, а плохое – отрицательный. Локальный алгоритм находит выравнивание с наивысшим баллом, рассматривая только выравнивания с положительными баллами и выбирая лучшее из них. Алгоритм является алгоритмом динамического программирования. При сравнении белков используется матрица сходства, которая присваивает балл каждой возможной паре аминокислотных остатков. Балл должен быть положительным для сходных остатков и отрицательным для несходных пар остатков. Пробелы обычно штрафуются с использованием линейной функции штрафов за пробелы, которая назначает начальный штраф за открытие пробела и дополнительный штраф за его удлинение, увеличивая длину пробела.
Сродственный
Наиболее широко используемой функцией штрафа за разрывы является аффинный штраф за разрывы. Аффинный штраф за разрывы сочетает в себе компоненты как постоянного, так и линейного штрафа за разрывы, принимая вид. Это вводит новые параметры: A известно как штраф за открытие разрыва, B – штраф за удлинение разрыва, а L – длина разрыва. Открытие разрыва относится к стоимости, необходимой для создания разрыва любой длины, а удлинение разрыва – к стоимости увеличения длины существующего разрыва на 1. Часто неясно, какими должны быть значения A и B, поскольку они варьируются в зависимости от задачи. В общем случае, если целью является поиск близкородственных соответствий (например, удаление векторной последовательности при секвенировании генома), следует использовать более высокий штраф за разрывы, чтобы уменьшить количество открытий разрывов. С другой стороны, штраф за разрывы следует снижать при поиске более далёких соответствий. Логарифмический штраф за разрывы имеет вид и был предложен, поскольку исследования показали, что распределение размеров вставок и делеций подчиняется степенному закону. Другая проблема, связанная с использованием аффинных разрывов, заключается в предпочтении выравнивания последовательностей с более короткими разрывами. Логарифмический штраф за разрывы был разработан для модификации аффинного штрафа таким образом, чтобы длинные разрывы были предпочтительнее. Выравнивания профилов профилов основаны на статистических профилях частоты вставок и делеций, полученных из множественных выравниваний последовательностей, сгенерированных при поисках PSI BLAST. Следовательно, в любой ситуации выравнивания положение разрыва должно определяться эмпирически. Кроме того, штрафы за разрывы при попарном выравнивании, такие как аффинный штраф за разрывы, часто применяются независимо от типов аминокислот во вставленном или удалённом фрагменте или на концах разрыва, несмотря на доказательства того, что в областях разрывов предпочтительны определённые типы остатков. Наконец, выравнивание последовательностей подразумевает выравнивание соответствующих структур, но взаимосвязь между структурными особенностями разрывов в белках и их соответствующими последовательностями известна лишь неполно. Из-за этого включение структурной информации в штрафы за разрывы затруднено. Некоторые алгоритмы используют предсказанную или фактическую структурную информацию для смещения положения разрывов. Однако известные структуры имеют лишь у меньшинства последовательностей, и большинство задач выравнивания включают последовательности с неизвестной вторичной и третичной структурой.