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

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

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

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

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

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

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

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

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

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

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