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

Отметим, что результаты данной статьи были независимо получены Галилом и Джанкарло [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].