4551
правка
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями
Материал из WEGA
Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок (посмотреть исходный код)
Версия от 19:50, 9 октября 2023
, 9 октября 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что | '''Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le \frac2 {k - 1}{k} = 2 - \frac{2}{k}.</math>''' | ||
Метод центральной звезды стремится получить такое выравнивание, которое согласуется с оптимальным парным выравниванием центральной строки со всеми остальными строками. Граница выводится на основе неравенства треугольника оценочной функции. Временная сложность данного метода составляет O( | Метод центральной звезды стремится получить такое выравнивание, которое согласуется с оптимальным парным выравниванием центральной строки со всеми остальными строками. Граница выводится на основе неравенства треугольника оценочной функции. Временная сложность данного метода составляет <math>O(k^2 \ell^2)</math>, где <math>\ell^2</math> – время решения задачи парного выравнивания методом динамического программирования, а <math>k^2</math> – время поиска центральной строки <math>X_c</math>, дающей минимальное значение <math>\sum_{i \ne c} D(X_c, X_i).</math> | ||
Теорема 2. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен рандомизированный алгоритм, который позволяет получить выравнивание A, такое, что | '''Теорема 2. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен рандомизированный алгоритм, который позволяет получить выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le 2 + \frac{1}{r - 1}</math> с вероятностью не менее 1 - (Ly-)t для любых r > 1 и p > 1.''' | ||
| Строка 64: | Строка 64: | ||
В ходе работы алгоритма сначала вычисляются все Q) оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку Xi, а вес каждого ребра (Xi ; Xj) равен D(Xi ; Xj). Этот шаг определяет общую временную сложность O(k2t2). Затем для этого графа вычисляется минимальное остовное дерево. Множественное выравнивание должно быть согласовано с оптимальными парными выравниваниями, представленными ребрами этого минимального остовного дерева. | В ходе работы алгоритма сначала вычисляются все Q) оптимальных парных выравниваний для построения графа, в котором каждая вершина представляет отдельную строку Xi, а вес каждого ребра (Xi ; Xj) равен D(Xi ; Xj). Этот шаг определяет общую временную сложность O(k2t2). Затем для этого графа вычисляется минимальное остовное дерево. Множественное выравнивание должно быть согласовано с оптимальными парными выравниваниями, представленными ребрами этого минимального остовного дерева. | ||
== Применение == | == Применение == | ||
