4501
правка
Локальное выравнивание (с вогнутыми штрафами за гэп): различия между версиями
Перейти к навигации
Перейти к поиску
м
Локальное выравнивание (с вогнутыми штрафами за гэп) (посмотреть исходный код)
Версия от 15:45, 20 мая 2021
, 20 мая 2021→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Теорема 1. Если функция W(k) является вогнутой, это дает нам алгоритм для вычисления оптимального выравнивания, который выполняется за время O( | '''Теорема 1. Если функция W(k) является вогнутой, это дает нам алгоритм для вычисления оптимального выравнивания, который выполняется за время <math>O(n^2 \; log \; n)</math>, где n – длина каждой строки, и использует O(n) ожидаемой памяти.''' | ||
Следствие 1. | '''Следствие 1'''. Если W(k) является аффинной функцией, этот же алгоритм выполняется за время <math>O(n^2)</math>. | ||
'''Теорема 2. Для некоторых специальных типов штрафных функций алгоритм может быть модифицирован для более быстрого выполнения.''' | |||
• | '''• Если W(k) является P-кусочной аффинной кривой, то алгоритм можно модифицировать таким образом, что он будет выполняться за время <math>O(n^2 \; log \; P)</math>.''' | ||
• Если W(k) является вогнутой функцией при k > K, алгоритм может быть модифицирован для выполнения за время O(K + | '''• Для логарифмической штрафной функции, W(k) = a + b log k, алгоритм может быть модифицирован так, чтобы выполняться за <math>O(n^2)</math> времени.''' | ||
'''• Если W(k) является вогнутой функцией при k > K, алгоритм может быть модифицирован для выполнения за время <math>O(K + n^2 \; log \; n)</math>.''' | |||
== Применение == | == Применение == | ||