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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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