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

Материал из WEGA
Версия от 23:27, 26 октября 2019; Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Задача нахождения центральной строки, «похожей» на каждую заданну…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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


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


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

Применение