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

Перейти к навигации Перейти к поиску
Строка 58: Строка 58:


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


== Экспериментальные результаты ==
== Экспериментальные результаты ==
4501

правка

Навигация