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

Материал из WEGA
Версия от 12:03, 27 октября 2019; Irina (обсуждение | вклад) (Irina переименовал страницу Задачи нахождения ближайшей строки и ближайшей подстроки в [[Задачи поиска ближайшей строки и ближайшей подс…)
Перейти к навигации Перейти к поиску

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

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


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


Задача 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].

Применение