Обмен ближайшими соседями и относительные расстояния: различия между версиями

В данном обзоре будут рассмотрены результаты исследований расстояния на базе преобразований для [[эволюционные деревья|эволюционных деревьев]]. В различных публикациях было предложено несколько моделей измерения расстояний для эволюционных деревьев. Самой известной из них, вероятно, можно считать модель расстояния ''обмена ближайшими соседями'' (nearest neighbor interchange, nni), независимо введенную в [10] и [9]. Помимо расстояния nni, стоит также обратить внимание на родственное понятие, называемое расстоянием ''переноса поддеревьев'' и введенное в [5, 6]. Несколько работ, среди авторов которых были Дасгупта, Хе, Цзян, Ли, Тромп и Чжан, продемонстрировали следующие результаты:

 

Вначале определим расстояние обмена ближайшими соседями и расстояние переноса поддеревьев с линейной стоимостью для невзвешенных деревьев; затем расширим эти понятия на взвешенные деревья. Далее будет считаться, что эволюционное (или [[филогенетическое дерево|филогенетическое]]) дерево является неупорядоченным, имеет листья с уникальными метками и непомеченные внутренние вершины, может быть корневым или некорневым, взвешенным или невзвешенным, а все внутренние вершины имеют степень 3.

 

Считается, что операция nni действует на это внутреннее ребро. Расстояние обмена ближайшими соседями, [[D_{nni}(T_1, T_2) \;]], между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальное число операций nni, необходимое для преобразования одного дерева в другое.

Расстояние переноса поддеревьев между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальное количество поддеревьев, необходимое для преобразования <math>T_1 \;</math> в <math>T_2 \;</math> [5, 6, 7]. Иногда на практике бывает необходимо проводить различие между разными операциями переноса поддеревьев, поскольку они встречаются с разной частотой. В таком случае можно назначить каждой операции переноса поддерева стоимость, равную расстоянию (в числе пройденных вершин), на которое поддерево перенесено в текущем дереве. Расстояние переноса поддеревьев с линейной стоимостью, <math>D_{lcst}(T_1, T_2) \;</math>, между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальная стоимость, затрачиваемая на преобразование <math>T_1 \;</math> в <math>T_2 \;</math> при помощи операций переноса поддеревьев [1, 2].

Модели обмена ближайшими соседями и переноса поддеревьев с линейной стоимостью  можно естественным образом расширить на взвешенные деревья. В первом случае расширение выполнить несложно: операции nni просто присваивается стоимость, равная весу ребра, над которым она производится. Чтобы обмен ближайшими соседями между взвешенными деревьями <math>T_1 \;</math> и <math>T_2 \;</math> был осуществимым, необходимо, чтобы выполнялись следующие условия: (1) для каждой метки листа a вес ребра в <math>T_1 \;</math>, инцидентного a, равен весу ребра в <math>T_2 \;</math>, инцидентного a; (2) мультимножества весов внутренних ребер <math>T_1 \;</math> и <math>T_2 \;</math> совпадают.