4551
правка
Нахождение ближайшей подстроки: различия между версиями
Перейти к навигации
Перейти к поиску
Нахождение ближайшей подстроки (посмотреть исходный код)
Версия от 16:36, 1 декабря 2019
, 1 декабря 2019→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
В рандомизированной версии упомянутая в теореме 2 схема PTAS с высокой вероятностью находит решение с расстоянием Хэмминга (1 + | В рандомизированной версии упомянутая в теореме 2 схема PTAS с высокой вероятностью находит решение с расстоянием Хэмминга <math>(1 + \epsilon)d_{opt}</math> для оптимального значения <math>d_{opt}</math> за время <math>(k^2 m)^{O(log|\Sigma| / \epsilon^4)}</math>. При увеличении накладных расходов эту рандомизированную версию PTAS можно дерандомизировать. Прямолинейная и эффективная аппроксимация с коэффициентом 2 для задачи CLOSEST STRING достигается путем проверки всех подстрок длины L одной из входных строк. | ||
| Строка 36: | Строка 36: | ||
Теорема 3[ ]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита. | Теорема 3[3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита. | ||
Теорема 4[ ]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита. | Теорема 4[7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита. | ||
| Строка 45: | Строка 45: | ||
Теорема 4 также позволяет по-новому взглянуть на вопрос аппроксимируемости задачи: в схеме PTAS для задачи CLOSEST SUBSTRING показатель степени полинома, ограничивающего время выполнения, зависит от коэффициента аппроксимации. Эта схема не является «эффективной» PTAS (EPTAS), то есть PTAS с временем выполнения f( | Теорема 4 также позволяет по-новому взглянуть на вопрос аппроксимируемости задачи: в схеме PTAS для задачи CLOSEST SUBSTRING показатель степени полинома, ограничивающего время выполнения, зависит от коэффициента аппроксимации. Эта схема не является «эффективной» PTAS (EPTAS), то есть PTAS с временем выполнения <math>f(\epsilon) \cdot n^c</math> для некоторой функции f и некоторой константы c и, следовательно, вряд ли окажется полезной на практике. Из теоремы 4 следует, что PTAS с временем выполнения <math>n^{(O(1 / \epsilon^4)}</math>, представленная в [6], скорее всего,не может быть улучшена до EPTAS. Точнее говоря, не существует PTAS с временем выполнения <math>f(\epsilon) \cdot n^{o(log \; 1 \ \epsilon)}</math> для задачи CLOSEST SUBSTRING, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Кроме того, из доказательства теоремы 4 также следует | ||
| Строка 61: | Строка 61: | ||
Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время O(j^l1" • n), проверяя все возможные строки над алфавитом S. | Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время O(j^l1" • n), проверяя все возможные строки над алфавитом S. | ||
== Применение == | == Применение == | ||
Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. Например, Саго [ ] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет O(k2m- Ld ■ \S\d). Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [ ] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций. | Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. Например, Саго [ ] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет O(k2m- Ld ■ \S\d). Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [ ] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций. | ||