Необщие ребра в филогенетических деревьях: различия между версиями

'''Теорема 1. Пусть T и T' – два входных филогенетических дерева с одним и тем же множеством меток листьев, n – число листьев в каждом дереве. Тогда расстояние в необщих ребрах между деревьями T и T' может быть найдено за время O(n).'''

Пусть <math>\Delta \;</math> – набор из k филогенетических деревьев с одним и тем же множеством меток листьев, n – число листьев в каждом дереве. Задача нахождения расстояния в необщих ребрах для всех пар может быть решена путем применения теоремы 1 к каждой паре филогенетических деревьев; таким образом, время ее решения составляет <math>O(k^2 n) \;</math>. Паттенгейл и Морэ [9] предложили рандомизированный алгоритм на базе [7] для приближенного решения задачи, который работает быстрее в случае <math>n \le k \le 2^n \;</math>.

'''Теорема 2. Пусть <math>\varepsilon \;</math> – параметр, <math>\varepsilon > 0 \;</math>. Тогда существует рандомизированный алгоритм, такой, что с вероятностью не менее <math>1 - k^{-2} \;</math> расстояние в необщих ребрах между каждой парой входных филогенетических деревьев из <math>\Delta \;</math> может быть аппроксимировано с коэффициентом <math>(1 + \varepsilon) \;</math> от действительного расстояния; время исполнения этого алгоритма составляет <math>O(k(n^2 + k \; log \; k) / \varepsilon^2)</math>.'''

В общем случае, пусть даны два входных филогенетических дерева R и R' с одним и тем же множеством меток листьев и одним и тем же мультимножеством весов ребер, n – число листьев в каждом дереве. Обобщенная задача нахождения расстояния в необщих ребрах может быть легко решена за время <math>O(n^2) \;</math> путем последовательного применения теоремы 1. Время исполнения удалось улучшить Хону и коллегам [5].