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

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

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

Теорема 2. Пусть " – параметр, " > 0. Тогда существует рандомизированный алгоритм, такой, что с вероятностью не менее 1 — k~2 расстояние в необщих ребрах между каждой парой входных филогенетических деревьев из Л может быть аппроксимировано с коэффициентом (1 + ") от действительного расстояния; время исполнения этого алгоритма составляет O(k(n2 + k log k)/"2).

В общем случае, пусть даны два входных филогенетических дерева R и R0 с одним и тем же множеством меток листьев и одним и тем же мультимножеством весов ребер, n – число листьев в каждом дереве. Обобщенная задача нахождения расстояния в необщих ребрах может быть легко решена за время O(n2) путем последовательного применения теоремы 1. Время исполнения удалось улучшить Хону и коллегам [ ].

Теорема 3. Расстояние в необщих ребрах между деревьями R и R0 может быть найдено за время O(n log n).