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

Ключевые слова и синонимы

Расстояние Робинсона-Фоулдса; метрика Робинсона-Фоулдса

Постановка задачи

Филогенетические деревья представляют собой бинарные деревья, листья которых имеют неповторяющиеся метки. Задача заключается в нахождении хорошо известной метрики, называемой расстоянием в необщих ребрах и позволяющей сравнивать расхождения между двумя филогенетическими деревьями. Грубо говоря, расстояние в необщих ребрах соответствует числу ребер, отличающих одно филогенетическое дерево от другого.

Пусть e – ребро в филогенетическом дереве T. Удаление ребра e разбивает T на два поддерева. Метки листьев также разбиваются на два подмножества, соответствующих поддеревьям. Ребро e называется ребром, порождающим разбиение множества меток листьев. Пусть даны два филогенетических дерева T и T' с одним и тем же количеством листьев и одним и тем же множеством меток листьев. Ребро e дерева T является общим, если существует некоторое ребро e' в дереве T', такое, что ребра e и e' порождают одно и то же разбиение множества меток листьев в соответствующих деревьях. В противном случае ребро e является необщим. Отметим, что деревья T и T' имеют одно и то же число ребер, стало быть, число необщих ребер в T (относительно T') равно числу необщих ребер в T' (относительно T). Это число называется расстоянием в необщих ребрах между деревьями T и T'. Определим две задачи:

Задача нахождения расстояния в необщих ребрах

Дано: два филогенетических дерева с одним и тем же множеством меток листьев

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

Задача нахождения расстояния в необщих ребрах для всех пар

Дано: набор филогенетических деревьев с одним и тем же множеством меток листьев

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

Расширение задачи

У филогенетических деревьев, часто используемых на практике, с ребрами ассоциированы веса. Понятие необщего ребра можно легко расширить на филогенетические деревья с взвешенными ребрами. В данном случае ребро e будет порождать разбиение множества меток листьев, а также мультимножества весов ребер (здесь веса ребер могут быть неуникальными). Пусть даны два филогенетических дерева R и R' с одним и тем же множеством меток листьев и одним и тем же мультимножеством весов ребер. Ребро e дерева R является общим, если существует некоторое ребро e' в дереве R', такое, что ребра e и e' порождают одно и то же разбиение множества меток листьев и мультимножества весов ребер. В противном случае ребро e является необщим. Расстояние в необщих ребрах между деревьями R и R' определяется сходным образом:

Обобщенная задача нахождения расстояния в необщих ребрах

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

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

Основные результаты

Первый линейный алгоритм для нахождения расстояния в необщих ребрах был предложен Дэем [3].

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

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

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

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

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

Применение

Филогенетические деревья широко используются в биологии для моделирования эволюционных взаимоотношений между видами. Многие применяемые методы реконструкции (такие как максимальная экономичность, максимальное правдоподобие, совместимость и матрица расстояний) дают в результате разные филогенетические деревья на основе одного и того же набора видов; любопытно было бы вычислить расхождения между этими деревьями. Кроме того, в процессе сравнения можно обнаружить информацию о редких генетических событиях – таких как рекомбинация или конверсия генов. Чаще всего применяется метрика расхождения под названием «метрика Робинсона-Фоулдса» [11], представляющая собой расстояние в необщих ребрах.

Были предложены и другие метрики расхождения – например, обмен ближайшими соседями (NNI) и расстояние переноса поддеревьев (STT) (подробнее об этом в [2]). Иногда биологи предпочитают именно эти метрики, поскольку они могут использоваться для обнаружения биологических событий, которые и вызвали расхождение. Однако вычислить эти метрики обычно значительно сложнее. В частности, ДасГупта и коллеги показали, что задачи вычисления расстояний NNI и STT являются NP-полными [1, 2]. Для этих задач были разработаны аппроксимационные алгоритмы (NNI: [4, 8], STT: [1, 6]). Любопытно, что для вычисления коэффициентов аппроксимации эти алгоритмы используют расстояние в необщих ребрах.

См. также

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

• Поддерево максимального соответствия

Литература

1. DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J.: On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees. Algorithmica 25(2-3), 176-195 (1999)

2. DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J., Zhang, L.: On Distances between Phylogenetic Trees. In: Proceedings of the Eighth ACM-SIAM Annual Symposium on Discrete Algorithms (SODA), New Orleans, pp. 427-436. SIAM, Philadelphia (1997)

3. Day, W.H.E.: Optimal Algorithms for Comparing Trees with Labeled Leaves. J. Classif. 2, 7-28 (1985)

4. Hon, W.K., Lam, T.W.: Approximating the Nearest Neighbor Intercharge Distance for Non-Uniform-Degree Evolutionary Trees. Int. J. Found. Comp. Sci. 12(4), 533-550 (2001)

5. Hon, W.K., Kao, M.Y., Lam, T.W., Sung, W.K., Yiu, S.M.: Non-shared Edges and Nearest Neighbor Interchanges revisited. Inf. Process. Lett. 91 (3), 129-134 (2004)

6. Hon, W.K., Lam, T.W., Yiu, S.M., Kao, M.Y., Sung, W.K.: Subtree Transfer Distance For Degree-D Phylogenies. Int. J. Found. Comp. Sci. 15(6),893-909 (2004)

7. Johnson, W., Lindenstrauss, J.: Extensions of Lipschitz Mappings into a Hilbert Space. Contemp. Math. 26,189-206 (1984)

8. Li, M., Tromp, J., Zhang, L.: Some Notes on the Nearest Neighbour Interchange Distance. J. Theor. Biol. 26(182), 463-467 (1996)

9. Pattengale, N.D., Moret, B.M.E.: A Sublinear-Time Randomized Approximation Scheme for the Robinson-Foulds Metric. In: Proceedings of the Tenth ACM Annual International Conference on Research in Computational Molecular Biology (RE-COMB), pp. 221-230. Venice, Italy, April 2-5 2006

10. Robinson, D.F.: Comparison of Labeled Trees with Valency Three. J. Comb. Theor. 11,105-119(1971)

11. Robinson, D.F., Foulds, L.R.: Comparison of Phylogenetic Trees. Math. Biosci. 53,131-147 (1981)