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

Материал из WEGA
Перейти к навигации Перейти к поиску
мНет описания правки
 
(не показаны 3 промежуточные версии этого же участника)
Строка 13: Строка 13:




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




Строка 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.'''




В рандомизированной версии упомянутая в теореме 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 одной из входных строк.
В рандомизированной версии упомянутая в теореме 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.




Строка 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 даже для бинарного алфавита.'''




Строка 45: Строка 45:




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




Строка 59: Строка 59:
'''Теорема 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>, проверяя все возможные строки над алфавитом <math>\Sigma</math>.


== Применение ==
== Применение ==
Строка 67: Строка 67:


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


== См. также ==
== См. также ==

Текущая версия от 13:42, 1 октября 2023

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

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

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

Задача нахождения ближайшей подстроки (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)