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

В работе Миллера и Майерса [9] рассматривается задача парного выравнивания последовательностей, в которой мера расстояния основана на модели штрафа за открытие гэпа. Авторы предложили эффективный алгоритм для решения задачи, в котором штраф за открытие гэпа является вогнутой функцией от длины гэпа.

Пусть X и Y – две строки (последовательности) алфавита S. Парное выравнивание <math>\mathcal{A}</math> строк X и Y отображает X, Y на строки X', Y', которые могут содержать пробелы (не являющиеся частью алфавита <math>\Sigma</math>) таким образом, что выполняется следующее: (1) <math>|X'| = |Y'| = \ell</math>; (2) удаление пробелов из X' и Y' превращает их в X и Y, соответственно; (3) для любого <math>1 \le i \le \ell</math> значения позиций X'[i] и Y'[i] не могут одновременно быть пробелами; здесь X'[i] обозначает первый символ в X'.

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

''Гэпом'' в выравнивании <math>\mathcal{A}</math> строк X и Y считается максимальная подстрока из смежных пробелов в последовательности X' или Y'. В выравнивании имеются гэпы и выровненные символы (и X'[i], и Y'[i] не являются пробелами). Оценка пары выровненных символов основана на функции расстояния <math>\delta(a, b)</math>, где <math>a, b \in \Sigma</math>. Обычно <math>\delta</math> является метрикой, но в данной статье это предположение не требуется. Штраф за гэп длиной k основывается на неотрицательной функции W(k). Оценка выравнивания представляет собой сумму оценок всех выровненных символов и пробелов. Выравнивание является ''оптимальным'', если оно имеет минимально возможную оценку.

Штрафная функция W(k) является ''аффинной'', если W(k) = a + bk, где a, b – константы. Аффинная функция является частным случаем вогнутой функции. Задача об аффинных штрафах рассматривалась в работах [1, 6] и в одноименной статье.