4551
правка
Нахождение ближайшей подстроки: различия между версиями
Материал из WEGA
Нахождение ближайшей подстроки (посмотреть исходный код)
Версия от 16:46, 1 декабря 2019
, 1 декабря 2019→Применение
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 64: | Строка 64: | ||
Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. | Алгоритмы решения задачи CLOSEST SUBSTRING широко применяются при анализе биологических последовательностей. При нахождении мотивов задача заключается в поиске «сигнала», общего для множества выбранных строк, представляющих последовательности ДНК или белка. Одним из вариантов представления таких сигналов являются приближенно сохраненные подстроки, встречающиеся в каждой из входных строк. Применение расстояния Хэмминга в качестве биологически значимой меры расстояния позволяет рассматривать задачу в формулировке CLOSEST SUBSTRING. | ||
Например, Саго [9] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет O( | Например, Саго [9] изучала способы поиска мотивов при помощи решения задачи CLOSEST SUBSTRING (и ее обобщений) с использованием суффиксных деревьев; у этого подхода время выполнения в наихудшем случае составляет <math>O(k^2 m \cdot L^d \cdot |\Sigma|^d)</math>. Для поиска мотивов также были предложены эвристики, применимые к задаче CLOSEST SUBSTRING; в частности, Певзнер и Зе [8] представили алгоритм под названием WINNOWER, а Булер и Томпа [1] использовали технику случайных проекций. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
