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

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

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

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

'''Дано''': Две строки X и Y, функция оценки <math>\delta</math> и функция штрафа за открытие гэпа W(k).

Концептуально оценка выравнивания используется для фиксации эволюционного расстояния между двумя заданными последовательностями. Поскольку гэп величиной в более чем один пробел может быть создан одним мутационным событием, в некоторых случаях может быть более уместным рассматривать гэп длиной k в качестве единичного элемента вместо k различных точечных мутаций. Однако вопрос о том, какую функцию штрафа за открытие гэпа следует использовать, весьма непрост и иногда зависит от конкретного приложения. В большинстве приложений, таких как BLAST, используется аффинная функция штрафа, которая на практике до сих пор является доминирующей моделью. С другой стороны, Беннер и др. [2], а также Гу и Ли [13] предложили в некоторых случаях использовать логарифмическую функцию штрафа. Вопрос о том, имеет ли смысл использовать вогнутую функцию штрафа за открытие гэпа в целом, остается открытым.

Отметим, что результаты данной статьи были независимо получены Галилом и Джанкарло [5]; для аффинного штрафа за открытие гэпа Готох [5] предложил алгоритм для решения задачи выравнивания с временем выполнения <math>O(n^2)</math>. В работе [4] Эппштейн представил более быстрый алгоритм для решения той же задачи выравнивания последовательностей с вогнутой функцией штрафа за открытие гэпа с временем выполнения <math>O(n^2)</math>. Вопрос о том, существует ли субквадратичный алгоритм для решения этой задачи, остается открытым. Следует отметить, что субквадратичные алгоритмы для решения задачи выравнивания последовательностей существуют в случаях, когда метрика не основана на модели штрафа за открытие гэпа и вычисляется как <math>\sum_{i = 1}^{\ell} \delta(X'[i], Y'[i])</math>, основываясь только на функции оценки <math>\delta(a, b)</math>, где <math>a, b \in \Sigma \cup \{ </math> _ <math> \} </math>, где "_" обозначает пробел [3, 8].