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

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

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

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

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

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

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

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

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

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

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

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

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

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