4551
правка
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями
Перейти к навигации
Перейти к поиску
м
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок (посмотреть исходный код)
Версия от 21:06, 9 октября 2023
, 9 октября 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
В ходе работы алгоритма сначала вычисляются все <math>\binom{k}{2}</math> оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку | В ходе работы алгоритма сначала вычисляются все <math>\binom{k}{2}</math> оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку <math>X_i</math>, а вес каждого ребра <math>(X_i, X_j)</math> равен <math>D(X_i, X_j)</math>. Этот шаг определяет общую временную сложность <math>O(k^2 \ell^2)</math>. Затем для этого графа вычисляется минимальное остовное дерево. Множественное выравнивание должно быть согласовано с оптимальными парными выравниваниями, представленными ребрами этого минимального остовного дерева. | ||
== Применение == | == Применение == | ||