Локальное выравнивание (с вогнутыми штрафами за гэп): различия между версиями

Пусть X и Y – две строки (последовательности) алфавита S. Парное выравнивание A строк X и Y отображает X, Y на строки X0, Y0, которые могут содержать пробелы (не в E) таким образом, что выолняется следующее (1) jX0j = jY0j = I; (2) удаление пробелов из X0 и Y0 превращает их в X и Y, соответственно; (3) для любого 1 < i < I значения позиций X0[i] и Y0[i] не могут одновременно быть пробелами, где X0[i] обозначает первый символ в X0.

Для оценки качества выравнивания предложено множество различных метрик (например, расстояние редактирования, матрица замен [11]). В данной статье рассматривается модель штрафа за открытие гэпа.

Гэпом в выравнивании A из X и Y считается максимальная подстрока из смежных пробелов в последовательности X0 или Y0. В выравнивании имеются гэпы и выровненные символы (и X0[i], и Y0[i] не являются пробелами). Оценка пары выровненных символов основана на функции расстояния S(a, b), где a, b 2 S. Обычно S является метрикой, но в данной статье это предположение не требуется. Штраф за гэп длиной k основывается на неотрицательной функции W(k). Оценка выравнивания представляет собой сумму оценок всех выровненных символов и пробелов. Выравнивание является оптимальным, если оно имеет минимально возможную оценку.