4551
правка
Нахождение ближайшей подстроки: различия между версиями
Материал из WEGA
Нахождение ближайшей подстроки (посмотреть исходный код)
Версия от 16:44, 1 декабря 2019
, 1 декабря 2019нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 22: | Строка 22: | ||
Теорема 1 [4, 5]. Задача CLOSEST SUBSTRING является NP-полной и остается таковой в специальном случае CLOSEST STRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. Задача CLOSEST STRING является NP-полной даже в случае ограничения в виде бинарного алфавита. | '''Теорема 1 [4, 5]. Задача CLOSEST SUBSTRING является NP-полной и остается таковой в специальном случае CLOSEST STRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. Задача CLOSEST STRING является NP-полной даже в случае ограничения в виде бинарного алфавита.''' | ||
Следующая теорема дает ключевое представление об аппроксимируемости задачи: | Следующая теорема дает ключевое представление об аппроксимируемости задачи: | ||
Теорема 2 [6]. Задача CLOSEST SUBSTRING (также как CLOSEST STRING) допускает применение схем аппроксимации с полиномиальным временем выполнения (PTAS), в которых целевой функцией является минимальное расстояние Хэмминга d. | '''Теорема 2 [6]. Задача CLOSEST SUBSTRING (также как CLOSEST STRING) допускает применение схем аппроксимации с полиномиальным временем выполнения (PTAS), в которых целевой функцией является минимальное расстояние Хэмминга d.''' | ||
| Строка 36: | Строка 36: | ||
Теорема 3[3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита. | '''Теорема 3[3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита.''' | ||
Теорема 4[7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита. | '''Теорема 4[7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита.''' | ||
| Строка 48: | Строка 48: | ||
Теорема 5 [7]. Не существует алгоритма, решающего задачу CLOSEST SUBSTRING приближенно за время <math>f(d, k) \cdot n^{o(log \; d)}</math> и точно за время <math>g(d, k) \cdot n^{o(log \; log \; k)}</math> для некоторых функций f и g, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. | '''Теорема 5 [7]. Не существует алгоритма, решающего задачу CLOSEST SUBSTRING приближенно за время <math>f(d, k) \cdot n^{o(log \; d)}</math> и точно за время <math>g(d, k) \cdot n^{o(log \; log \; k)}</math> для некоторых функций f и g, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время.''' | ||
| Строка 54: | Строка 54: | ||
Теорема 6 [7]. Задача CLOSEST SUBSTRING может быть решена за время <math>f(d) \cdot n^{O(log \; d)}</math> для некоторой функции f, где, более точно, <math>f(d) = |\Sigma|^{d(log \; d + 2)}</math>. | '''Теорема 6 [7]. Задача CLOSEST SUBSTRING может быть решена за время <math>f(d) \cdot n^{O(log \; d)}</math> для некоторой функции f, где, более точно, <math>f(d) = |\Sigma|^{d(log \; d + 2)}</math>.''' | ||
Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время <math>g(d, k) \cdot n^{O(log \; log \; k)}</math> для некоторой функции g, где, более точно, <math>g(d, k) = (|\Sigma| d)^{O(kd)}</math>. | '''Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время <math>g(d, k) \cdot n^{O(log \; log \; k)}</math> для некоторой функции g, где, более точно, <math>g(d, k) = (|\Sigma| d)^{O(kd)}</math>.''' | ||
Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время <math>O(|\Sigma|^L \cdot n)</math>, проверяя все возможные строки над алфавитом S. | Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время <math>O(|\Sigma|^L \cdot n)</math>, проверяя все возможные строки над алфавитом S. | ||
== Применение == | == Применение == | ||
Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. Например, Саго [ ] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет O(k2m- Ld ■ \S\d). Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [ ] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций. | Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. | ||
Например, Саго [9] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет O(k2m- Ld ■ \S\d). Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [ ] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций. | |||
== Открытые вопросы == | == Открытые вопросы == | ||
