Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Постановка задачи == Задача нахождения центральной строки, «похожей» на каждую заданну…»)
 
мНет описания правки
Строка 8: Строка 8:
Задача 1 (задача нахождения ближайшей строки)
Задача 1 (задача нахождения ближайшей строки)


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


Требуется: найти минимальное значение d и строки длины m, находящиеся в пределах расстояния Хэмминга d от каждой строки <math>s_i \in S</math>.
Требуется: найти минимальное значение d и строки длины m, находящиеся в пределах расстояния Хэмминга d от каждой строки <math>s_i \in S</math>.
Строка 18: Строка 18:
Задача 2 (задача нахождения ближайшей подстроки)
Задача 2 (задача нахождения ближайшей подстроки)


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


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

Версия от 23:28, 26 октября 2019

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

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


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


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

Применение