Нахождение ближайшей подстроки: различия между версиями

Здесь <math>d_H(s, s'_i)</math> обозначает расстояние Хэмминга между s и <math>s'_i</math>, т. е. количество позиций, в которых s и <math>s'_i</math> различаются. Согласно нотации, применявшейся в работе [7], m обозначает среднюю длину входных строк, а n – суммарный размер входных данных задачи.

'''Теорема 1 [4, 5]. Задача CLOSEST SUBSTRING является NP-полной и остается таковой в специальном случае CLOSEST STRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. Задача CLOSEST STRING является NP-полной даже в случае ограничения бинарным алфавитом.'''

'''Теорема 2 [6]. Задача CLOSEST SUBSTRING (также как CLOSEST STRING) допускает применение аппроксимационных схем с полиномиальным временем выполнения (PTAS), в которых целевой функцией является минимальное расстояние Хэмминга d.'''

В рандомизированной версии упомянутая в теореме 2 схема PTAS с высокой вероятностью находит решение с расстоянием Хэмминга <math>(1 + \epsilon)d_{opt}</math> для оптимального значения <math>d_{opt}</math> за время <math>(k^2 m)^{O(log|\Sigma| / \epsilon^4)}</math>. Эту рандомизированную версию PTAS можно дерандомизировать с увеличением накладных расходов. Прямолинейная и эффективная аппроксимация задачи CLOSEST STRING с коэффициентом 2 достигается путем проверки всех подстрок одной из входных строк, имеющих длину L.

'''Теорема 3 [3]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра k даже для бинарного алфавита.'''

'''Теорема 4 [7]. Задача CLOSEST SUBSTRING является W[1]-сложной относительно параметра d даже для бинарного алфавита.'''

Теорема 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 также следует

'''Теорема 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-КНФ может быть решена за субэкспоненциальное время.'''

Для неограниченных алфавитов были получены более строгие границы за счет того, что было показано, что не существует PTAS с временем выполнения <math>f(\epsilon) \cdot n^{o(1 / \epsilon)}</math> для задачи CLOSEST SUBSTRING для любой функции f, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время [10]. Следующие утверждения дают возможность получить точные алгоритмы решения задачи CLOSEST SUBSTRING для небольших фиксированных значений d и k, соответствующие границе, приведенной в теореме 5:

Относительно заданного в задаче параметра L задачу CLOSEST SUBSTRING можно тривиально решить за время <math>O(|\Sigma|^L \cdot n)</math>, проверяя все возможные строки над алфавитом <math>\Sigma</math>.

Например, Саго [9] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет <math>O(k^2 m \cdot L^d \cdot |\Sigma|^d)</math>. Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [8] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций.

Остается нерешенным вопрос [7], можно ли аппроксимационную схему с временем выполнения <math>n^{O(1 / \epsilon^4)}</math>, предложенную в работе [6], улучшить до <math>n^{O(log \; 1 / \epsilon)}</math> в соответствии с границей, полученной на основе теоремы 4.

• Задача выбора различающей подстроки (Distinguishing Substring Selection) представляет собой обобщение CLOSEST SUBSTRING, в котором заданы второе множество входных строк и дополнительное целое число d', а искомое решение в виде строки s, помимо основного требования CLOSEST SUBSTRING, должно иметь расстояние Хэмминга не менее d' от каждой подстроки длины L второго множества строк.

• Задача поиска консенсусных образцов (Consensus Patterns) получается путем замены в определении задачи CLOSEST SUBSTRING максимума из расстояний Хэмминга на сумму этих расстояний. Таким образом, задача CONSENSUS PATTERNS отвечает на вопрос: существует ли строка s длины L, такая, что <math>\sum_{i = 1, ... m} d_H(s, s'_i) \le d</math>?