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

Дано: k строк s1, s2, ..., sk над алфавитом S и неотрицательные целые числа d и L.

Здесь dH(s, s0i) обозначает расстояние Хэмминга между s и si0, т. е. количество позиций, в которых s и si0 различаются. Согласно нотации, применявшейся в работе [ ], m обозначает среднюю длину входных строк, а n – суммарный размер входных данных задачи.

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

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

В рандомизированной версии упомянутая в теореме 2 схема PTAS с высокой вероятностью находит решение с расстоянием Хэмминга (1 + e)dopt для оптимального значения dopt за время (k2■m)o(los|-E|/e4). При увеличении накладных расходов эту рандомизированную версию PTAS можно дерандомизировать. Прямолинейная и эффективная аппроксимация с коэффициентом 2 для задачи CLOSEST STRING достигается путем проверки всех подстрок длины L одной из входных строк.

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

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

Теорема 4 также позволяет по-новому взглянуть на вопрос аппроксимируемости задачи: в схеме PTAS для задачи CLOSEST SUBSTRING показатель степени полинома, ограничивающего время выполнения, зависит от коэффициента аппроксимации. Эта схема не является «эффективной» PTAS (EPTAS), то есть PTAS с временем выполнения f(e) ■ nc для некоторой функции f и некоторой константы c и, следовательно, вряд ли окажется полезной на практике. Из теоремы 4 следует, что PTAS с временем выполнения no{i/e), представленная в [ ], скорее всего,не может быть улучшена до EPTAS. Точнее говоря, не существует PTAS с временем выполнения /(e) • ио(1о«1/е) для задачи CLOSEST SUBSTRING, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Кроме того, из доказательства теоремы 4 также следует

Теорема 5 [7]. Не существует алгоритма, решающего задачу CLOSEST SUBSTRING приближенно за время f(d; k) ■ no(logd) и точно за время g(d; k) • no(logl°gk) для некоторых функций f и g, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время.

Для неограниченных алфавитов были получены более строгие границы за счет того, что было показано, что не существует PTAS с временем выполнения /(e) • и°'1/е' для задачи CLOSEST SUBSTRING для любой функции f, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Следующие утверждения дают возможность получить точные алгоритмы решения задачи CLOSEST SUBSTRING для небольших фиксированных значений d и k, соответствующие границе, приведенной в теореме Theorem 5:

Теорема 6 [7]. Задача CLOSEST SUBSTRING может быть решена за время f(d) ■ n°^°&^ для некоторой функции f, где, более точно, f(d) = \E.

Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время g(d; k) ■ nO(loglogk) для некоторой функции g, где, более точно, g(d; k) = (\E\d)0(kd\.

Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. Например, Саго [ ] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет O(k2m- Ld ■ \S\d). Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [ ] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций.

Остается нерешенным вопрос [ ], можно ли схему аппроксимации с временем выполнения no(-ll€ ), предложенную в работе [ ], улучшить до M°'logl/e' в соответствии с границей, полученной на основе теоремы 4.

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

• Задача поиска консенсусных образцов (Consensus Patterns) получается путем замены в определении задачи CLOSEST SUBSTRING максимума из расстояний Хэмминга на сумму этих расстояний. Таким образом, задача CONSENSUS PATTERNS отвечает на вопрос: существуетли строка s длины L, такая, что