Эффективные методы множественного выравнивания последовательностей с гарантированными границами ошибок: различия между версиями

'''Теорема 1. Пусть A* – оптимальное множественное выравнивание заданных k строк с минимальной оценкой SP. Предложен алгоритм аппроксимации (метод центральной звезды), который позволяет получить множественное выравнивание A, такое, что <math>\frac{SP(A)}{SP(A^*)} \le \frac2 {k - 1}{k} = 2 - \frac{2}{k}.</math>'''

Вместо того чтобы вычислять <math>\binom{k}{2}</math> оптимальные парные выравнивания для поиска наилучшей центральной строки, рандомизированный алгоритм рассматривает только p случайно выбранных строк в качестве кандидатов на наилучшую центральную строку, поэтому для работы этого метода необходимо вычислить только (k - 1)p оптимальных парных выравниваний за время <math>O(kp \ell^2)</math>, где <math>1 \le p \le k</math>.

'''Теорема 3. Пусть T* - оптимальное эволюционное дерево из заданных k строк с минимальной оценкой TA. Предложен алгоритм аппроксимации, позволяющий получить эволюционное дерево T, такое, что <math>\frac{TA(T)}{TA(T^*)} \le \frac2 {k - 1}{k} = 2 - \frac{2}{k}.</math>'''