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

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

Пусть 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' определяется сходным образом:

'''Теорема 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].

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

 

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