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

Отметим, что результаты данной статьи были независимо получены Галилом и Джанкарло [5]; для аффинного штрафа за открытие гэпа Готох [ ] предложил алгоритм для решения задачи выравнивания с временем выполнения O(n2). В работе [ ] Эппштейн представил более быстрый алгоритм для решения той же задачи выравнивания последовательностей с вогнутой функцией штрафа за открытие гэпа с временем выполнения O(n2). Вопрос о том, существует ли субквадратичный алгоритм для решения этой задачи, остается открытым. Следует отметить, что субквадратичные алгоритмы для решения задачи выравнивания последовательностей существуют в случаях, когда метрика не основана на модели штрафа за открытие гэпа и вычисляется как ^2i=1S(Xl'[i],Y'[i]), основываясь только на функции оценки S(a, b), где a; b 2 £ [ f_g, где "_" обозначает занимаемую память [3,8].