4551
правка
Нахождение ближайшей подстроки: различия между версиями
Перейти к навигации
Перейти к поиску
м
Нахождение ближайшей подстроки (посмотреть исходный код)
Версия от 16:50, 1 декабря 2019
, 1 декабря 2019→См. также
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
| Строка 74: | Строка 74: | ||
• Задача нахождения ближайшей строки (Closest String) является специальным случаем CLOSEST SUBSTRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. | • Задача нахождения ближайшей строки (Closest String) является специальным случаем CLOSEST SUBSTRING, в котором искомая строка s должна иметь ту же длину, что и исходные строки. | ||
• Задача выбора различающей подстроки (Distinguishing Substring Selection) представляет собой обобщение CLOSEST SUBSTRING, в котором заданы второе множество входных строк и дополнительное целое число | • Задача выбора различающей подстроки (Distinguishing Substring Selection) представляет собой обобщение CLOSEST SUBSTRING, в котором заданы второе множество входных строк и дополнительное целое число d', а искомое решение в виде строки s, помимо основного требования CLOSEST SUBSTRING, должно иметь расстояние Хэмминга не менее d' от каждой подстроки длины L второго множества строк. | ||
• Задача поиска консенсусных образцов (Consensus Patterns) получается путем замены в определении задачи CLOSEST SUBSTRING максимума из расстояний Хэмминга на сумму этих расстояний. Таким образом, задача CONSENSUS PATTERNS отвечает на вопрос: | • Задача поиска консенсусных образцов (Consensus Patterns) получается путем замены в определении задачи CLOSEST SUBSTRING максимума из расстояний Хэмминга на сумму этих расстояний. Таким образом, задача CONSENSUS PATTERNS отвечает на вопрос: существует ли строка s длины L, такая, что <math>\sum_{i = 1, ... m} d_H(s, s'_i) \le d</math>? | ||
Задача CONSENSUS PATTERNS является специальным случаем задачи нахождения подстрок максимальной экономичности (SUBSTRING PARSIMONY), в которой филогенетическое дерево из определения SUBSTRING PARSIMONY представляет собой звездчатое дерево. | Задача CONSENSUS PATTERNS является специальным случаем задачи нахождения подстрок максимальной экономичности (SUBSTRING PARSIMONY), в которой филогенетическое дерево из определения SUBSTRING PARSIMONY представляет собой звездчатое дерево. | ||