Задачи поиска ближайшей строки и ближайшей подстроки: различия между версиями
Irina (обсуждение | вклад) м (Irina переименовал страницу Задачи нахождения ближайшей строки и ближайшей подстроки в [[Задачи поиска ближайшей строки и ближайшей подс…) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача | Задача поиска центральной строки, «похожей» на каждую заданную строку, часто возникает в вычислительной биологии и теории кодирования. | ||
Строка 6: | Строка 6: | ||
Задача 1 (задача | Задача 1 (задача поиска ближайшей строки) | ||
Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | Дано: набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | ||
Строка 16: | Строка 16: | ||
Задача 2 (задача | Задача 2 (задача поиска ближайшей подстроки) | ||
Дано: целое число L и набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. | Дано: целое число L и набор строк <math>S = \{ s_1, s_2, ..., s_n \}</math>, каждая из которых имеет длину m. |
Версия от 12:04, 27 октября 2019
Постановка задачи
Задача поиска центральной строки, «похожей» на каждую заданную строку, часто возникает в вычислительной биологии и теории кодирования.
Встречаются две версии этой задачи. Первая из них возникает в теории кодирования, когда мы ищем код, не слишком отличающийся от заданного набора фрагментов кода.
Задача 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].