Нахождение ближайшей подстроки

Ключевые слова и синонимы

Нахождение приближенной общей подстроки

Постановка задачи

Задача нахождения ближайшей подстроки (CLOSEST SUBSTRING) является базовой задачей при анализе строк с поиском консенсуса, который применяется, в частности, в вычислительной биологии. Его версия разрешимости определяется следующим образом.

Нахождение ближайшей подстроки (CLOSEST SUBSTRING)

Дано: k строк [math]\displaystyle{ s_1, s_2, ..., s_k }[/math] над алфавитом [math]\displaystyle{ \Sigma }[/math] и неотрицательные целые числа d и L.

Вопрос: существует ли строка s длины L, а также существует ли для всех i = 1, ..., k подстрока [math]\displaystyle{ s'_i }[/math] строки [math]\displaystyle{ s_i }[/math] длины L, такая, что [math]\displaystyle{ d_H(s, s'_i) \le d }[/math]?

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

В оптимизационной версии задачи CLOSEST SUBSTRING необходимо найти минимальное значение параметра расстояния d, для которого входные строки позволяют найти решение.

Основные результаты

Сложность классического алгоритма CLOSEST SUBSTRING задается следующим выражением:

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

Следующая теорема дает ключевое представление об аппроксимируемости задачи:

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

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

Следующие два утверждения характеризуют параметризованную сложность задачи относительно обоих параметров d и k:

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

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

Для небинарного алфавита утверждение теоремы 3 было независимо доказано Эванс и коллегами [2]. Теоремы 3 и 4 говорят о том, что существование точного алгоритма решения задачи CLOSEST SUBSTRING с полиномиальными временем выполнения маловероятно как для константного значения d, так и для константного значения k, то есть такого алгоритма не существует за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время.

Теорема 4 также позволяет по-новому взглянуть на вопрос аппроксимируемости задачи: в схеме PTAS для задачи CLOSEST SUBSTRING показатель степени полинома, ограничивающего время выполнения, зависит от коэффициента аппроксимации. Эта схема не является «эффективной» PTAS (EPTAS), то есть PTAS с временем выполнения [math]\displaystyle{ f(\epsilon) \cdot n^c }[/math] для некоторой функции f и некоторой константы c и, следовательно, вряд ли окажется полезной на практике. Из теоремы 4 следует, что PTAS с временем выполнения [math]\displaystyle{ n^{O(1 / \epsilon^4)} }[/math], представленная в [6], скорее всего, не может быть улучшена до EPTAS. Точнее говоря, не существует PTAS с временем выполнения [math]\displaystyle{ f(\epsilon) \cdot n^{o(log \; 1 / \epsilon)} }[/math] для задачи CLOSEST SUBSTRING, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время. Кроме того, из доказательства теоремы 4 также следует

Теорема 5 [7]. Не существует точных алгоритмов решения задачи CLOSEST SUBSTRING за время [math]\displaystyle{ f(d, k) \cdot n^{o(log \; d)} }[/math] и [math]\displaystyle{ g(d, k) \cdot n^{o(log \; log \; k)} }[/math] для некоторых функций f и g, за исключением случая, если задача 3-КНФ может быть решена за субэкспоненциальное время.

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

Теорема 6 [7]. Задача CLOSEST SUBSTRING может быть решена за время [math]\displaystyle{ f(d) \cdot n^{O(log \; d)} }[/math] для некоторой функции f, где, более точно, [math]\displaystyle{ f(d) = |\Sigma|^{d(log \; d + 2)} }[/math].

Теорема 7 [7]. Задача CLOSEST SUBSTRING может быть решена за время [math]\displaystyle{ g(d, k) \cdot n^{O(log \; log \; k)} }[/math] для некоторой функции g, где, более точно, [math]\displaystyle{ g(d, k) = (|\Sigma| d)^{O(kd)} }[/math].

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

Применение

Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING.

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

Открытые вопросы

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

См. также

Следующие задачи тесно связаны с задачей CLOSEST SUBSTRING:

• Задача нахождения ближайшей строки (Closest String) является специальным случаем CLOSEST SUBSTRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки.

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

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

Задача CONSENSUS PATTERNS является специальным случаем задачи нахождения подстрок максимальной экономичности (SUBSTRING PARSIMONY), в которой филогенетическое дерево из определения SUBSTRING PARSIMONY представляет собой звездчатое дерево.

Литература

1. Buhler, J.,Tompa, M.: Finding motifs using random projections. J. Comput. Biol. 9(2), 225-242 (2002)

2. Evans, P.A., Smith, A.D., Wareham, H.T.: On the complexity of finding common approximate substrings. Theor. Comput. Sci. 306(1-3),407-430(2003)

3. Fellows, M.R., Gramm, J., Niedermeier, R.: On the parameterized intractability of motif search problems. Combinatorica 26(2),141-167(2006)

4. Frances, M., Litman, A.: On covering problems of codes. Theor. Comput. Syst. 30,113-119 (1997)

5. Lanctot, J.K.: Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing String Search Problems. Inf. Comput. 185,41-55 (2003)

6. Li, M., Ma, B., Wang, L.: On the Closest String and Substring Problems. J. ACM 49(2), 157-171 (2002)

7. Marx, D.: The Closest Substring problem with small distances. In: Proceedings of the 46th FOCS, pp 63-72. IEEE Press, (2005)

8. Pevzner, P.A., Sze, S.H.: Combinatorial approaches to finding subtle signals in DNA sequences. In: Proc. of 8th ISMB, pp. 269-278. AAAI Press, (2000)

9. Sagot, M.F.: Spelling approximate repeated or common motifs using a suffix tree. In: Proc. of the 3rd LATIN, vol. 1380 in LNCS, pp. 111-127. Springer (1998)

10. Wang,J., Huang, M., Cheng, J.: A Lower Bound on Approximation Algorithms for the Closest Substring Problem. In: Proceedings COCOA 2007, vol. 4616 in LNCS, pp. 291-300 (2007)