Задачи поиска ближайшей строки и ближайшей подстроки

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

Задача поиска центральной строки, «похожей» на каждую заданную строку, часто возникает в вычислительной биологии и теории кодирования.

Встречаются две версии этой задачи. Первая из них возникает в теории кодирования, когда мы ищем код, не слишком отличающийся от заданного набора фрагментов кода.

Задача 1 (задача поиска ближайшей строки)

Дано: набор строк [math]\displaystyle{ S = \{ s_1, s_2, ..., s_n \} }[/math], каждая из которых имеет длину m.

Требуется: найти минимальное значение d и строку s длины m, находящуюся в пределах расстояния Хэмминга d от каждой строки [math]\displaystyle{ s_i \in S }[/math].

Вторая задача оказывается намного более трудной. Эта задача встречается в приложениях для поиска консервативных областей, генетической идентификации мишени лекарственного препарата, а также генетических зондов в молекулярной биологии.

Задача 2 (задача поиска ближайшей подстроки)

Дано: целое число L и набор строк [math]\displaystyle{ S = \{ s_1, s_2, ..., s_n \} }[/math], каждая из которых имеет длину m.

Требуется: найти минимальное значение d и строку s длины L, находящуюся в пределах расстояния Хэмминга d от имеющей длину L подстроки [math]\displaystyle{ t_i }[/math] строки [math]\displaystyle{ s_i }[/math] для i = 1, 2, ..., n.

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

Следующие результаты представлены в работе [1].

Теорема 1. Существует аппроксимационная схема с полиномиальным временем выполнения для задачи поиска ближайшей строки.

Теорема 2. Существует аппроксимационная схема с полиномиальным временем выполнения для задачи поиска ближайшей подстроки.

Результаты для других метрик можно найти в [10, 11, 12].

Применение

Многие задачи молекулярной биологии включают поиск схожих областей, общих для каждой последовательности, в заданном множестве последовательностей ДНК, РНК или белка. Эти задачи находят применение при локализации сайтов связывания и поиске консервативных областей в невыровненных последовательностях [2, 7, 9, 13, 14], генетической идентификации мишени лекарственного препарата [8], конструировании генетических зондов [8], конструировании универсальных праймеров для ПЦР [4, 8], а помимо вычислительной биологии – в теории кодирования [5, 6]. Подобные задачи могут рассматриваться как различные обобщения задачи поиска общей подстроки, допускающей наличие ошибок. Было предложено несколько метрик для поиска таких областей, общих для всех заданных строк. Популярной и одной из самых фундаментальных метрик является расстояние Хэмминга. Кроме того, в этой сфере используются две известные целевые функции. Одной из них является полная сумма расстояний между центральной строкой (общей подстрокой) и каждой из заданных строк. Второй – максимальное расстояние между центральной строкой и заданной строкой. Более подробное изложение см. в работе [8].

Более общая задача

Задача выбора различающей подстроки получает на входе два множества строк, B и G. Требуется найти подстроку неуказанной длины (обозначаемой L), такую, что она оказывается близкой к подстрокам каждой строки из B и далекой от любой подстроки длины L строк из G. Впрочем, мы можем пройти все возможные значения L и предположить, что каждая строка в G имеет одну и ту же длину L, поскольку множество G может быть реконструировано с тем, чтобы содержать все подстроки длины L в каждой из хороших строк.

Формальное определение задачи выглядит следующим образом. Пусть даны множество [math]\displaystyle{ B = \{ s_1, s_2, ..., s_{n_1} \} }[/math] из [math]\displaystyle{ n_1 }[/math] (плохих) строк длиной не менее L и множество [math]\displaystyle{ G = \{ g_1, g_2, ..., g_{n_2} \} }[/math] из [math]\displaystyle{ n_2 }[/math] (хороших) строк, длина которых в точности равна L, а также два целых числа [math]\displaystyle{ d_b }[/math] и [math]\displaystyle{ d_g }[/math] [math]\displaystyle{ (d_b \le d_g) }[/math]. Задача выбора различающей подстроки (distinguishing substring selection problem, DSSP) заключается в нахождении строки s, такой, что для каждой строки [math]\displaystyle{ s_i \in B }[/math] существует имеющая длину L подстрока [math]\displaystyle{ t_i }[/math] строки [math]\displaystyle{ s_i }[/math] с [math]\displaystyle{ d(s, t_i) \le d_b }[/math], и для каждой строки [math]\displaystyle{ g_i \in G }[/math] имеет место [math]\displaystyle{ d(s, g_i) \ge d_g }[/math]. Здесь d(,) обозначает расстояние Хэмминга между двумя строками. Если все строки в множестве B также имеют длину L, задача называется задачей поиска различающей строки (distinguishing string problem, DSP).

Задача поиска различающей строки была впервые предложена в [8] в контексте генетической идентификации мишени лекарственного препарата. Следующие результаты представлены в работе [3].

Теорема 3. Существует аппроксимационная схема с полиномиальным временем выполнения для задачи выбора различающей подстроки. А именно, для любого константного значения [math]\displaystyle{ \epsilon \gt 0 }[/math] алгоритм находит строку s длины L, такую, что для каждого [math]\displaystyle{ s_i \in B }[/math] существует имеющая длину L подстрока [math]\displaystyle{ t_i }[/math] строки [math]\displaystyle{ s_i }[/math] с [math]\displaystyle{ d(t_i, s) \le (1 + \epsilon)d_b }[/math] и для каждой подстроки [math]\displaystyle{ u_i }[/math] длины L каждой строки [math]\displaystyle{ g_i \in G }[/math] имеет место [math]\displaystyle{ d(u_i, s) \ge (1 - \epsilon) d_g }[/math], если существует решение для исходной пары [math]\displaystyle{ (d_b \le d_g) }[/math]. Поскольку существует полиномиальное количество таких пар [math]\displaystyle{ (d_b, d_g) }[/math], мы можем за полиномиальное время перебрать все возможности и найти наиболее подходящую аппроксимацию для соответствующей конкретной задачи.

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

Разработанные здесь схемы PTAS используют техники линейного программирования и рандомизированного округления для решения определенных классов задачи. Таким образом, время выполнения алгоритмов поиска ближайшей строки и ближайшей подстроки оказывается очень высоким. Перспективным направлением может стать разработка более эффективных схем PTAS для обеих задач.

См. также

• Нахождение ближайшей подстроки
• Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок
• Разработка алгоритмов для вычислительной биологии
• Многолокусная ПЦР для сокращения разрывов (при сборке полного генома)

Литература

1. Ben-Dor, A., Lancia, G., Perone, J., Ravi, R.: Banishing bias from consensus sequences. In: Proc. 8th Ann. Combinatorial Pattern Matching Conf., pp. 247-261. (1997)

2. Deng, X., Li, G., Li, Z., Ma, B., Wang, L.: Genetic Design of Drugs Without Side-Effects. SI AM. J. Comput. 32(4), 1073-1090 (2003)

3. Dopazo, J., Rodriguez, A., Saiz, J.C., Sobrino, F.: Design of primers for PCR amplification of highly variable genomes. CABIOS 9,123-125(1993)

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

5. G^sieniec, L., Jansson, J., Lingas, A.: Efficient approximation algorithms for the hamming center problem. In: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms., pp. 135-S906. (1999)

6. Hertz, G., Stormo, G.: Identification of consensus patterns in unaligned DNA and protein sequences: a large-deviation statistical basis for penalizing gaps. In: Proc. 3rd Int'l Conf. Bioinformatics and Genome Research, pp. 201-216. (1995)

7. Lanctot, K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. In: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms, pp. 633-642. (1999)

8. Lawrence, C., Reilly, A.: An expectation maximization (EM) algorithm for the identification and characterization of common sites in unaligned biopolymer sequences. Proteins 7, 41-51 (1990)

9. Li, M., Ma, B., Wang, L.: On the closest string and substring problems. J. ACM 49(2), 157-171 (2002)

10. Li, M., Ma, B., Wang, L.: Finding similar regions in many sequences. J. Comput. Syst. Sci.(1999)

11. Li, M., Ma, B., Wang, L.: Finding similar regions in many strings. In: Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pp. 473-482. Atlanta (1999)

12. Ma, B.: A polynomial time approximation scheme for the closest substring problem. In: Proc. 11th Annual Symposium on Combinatorial Pattern Matching, Montreal, pp. 99-107. (2000)

13. Stormo, G.: Consensus patterns in DNA. In: Doolittle, R.F. (ed.) Molecular evolution: computer analysis of protein and nucleic acid sequences. Methods in Enzymology, vol. 183, pp. 211-221 (1990)

14. Stormo, G., Hartzell III, G.W.: Identifying protein-binding sites from unaligned DNA fragments. Proc. Natl. Acad. Sci. USA. 88, 5699-5703(1991)