4488
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
В данном обзоре будут рассмотрены результаты исследований расстояния на базе преобразований для эволюционных деревьев. В различных публикациях было предложено несколько моделей измерения расстояний для эволюционных деревьев. Самой известной из них, вероятно, можно считать модель расстояния обмена ближайшими соседями (nearest neighbor interchange, nni), независимо введенную в [ ] и [ ]. Помимо расстояния nni, стоит также обратить внимание на родственное понятие, называемое расстоянием переноса поддеревьев и введенное в [5, 6]. Несколько работ, среди авторов которых были Дасгупта, Хе, Цзян, Ли, Тромп и Чжан, продемонстрировали следующие результаты: | В данном обзоре будут рассмотрены результаты исследований расстояния на базе преобразований для [[эволюционные деревья|эволюционных деревьев]]. В различных публикациях было предложено несколько моделей измерения расстояний для эволюционных деревьев. Самой известной из них, вероятно, можно считать модель расстояния ''обмена ближайшими соседями'' (nearest neighbor interchange, nni), независимо введенную в [10] и [9]. Помимо расстояния nni, стоит также обратить внимание на родственное понятие, называемое расстоянием ''переноса поддеревьев'' и введенное в [5, 6]. Несколько работ, среди авторов которых были Дасгупта, Хе, Цзян, Ли, Тромп и Чжан, продемонстрировали следующие результаты: | ||
• найдено соответствие между расстоянием обмена ближайшими соседями и расстоянием переноса поддеревьев с линейной стоимостью на невзвешенных деревьях; | • найдено соответствие между расстоянием обмена ближайшими соседями и расстоянием переноса поддеревьев с линейной стоимостью на невзвешенных деревьях; | ||
• вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение алгоритмов аппроксимации с логарифмическим коэффициентом; | • вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение алгоритмов аппроксимации с логарифмическим коэффициентом; | ||
• разработан алгоритм 2-аппроксимации для вычисления расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях. | • разработан алгоритм 2-аппроксимации для вычисления расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях. | ||
Вначале определим расстояние обмена ближайшими соседями и расстояние переноса поддеревьев с линейной стоимостью для невзвешенных деревьев; затем расширим эти понятия на взвешенные деревья. Далее будет считаться, что эволюционное (или филогенетическое) дерево является неупорядоченным, имеет листья с уникальными метками и непомеченные внутренние вершины, может быть корневым или некорневым, взвешенным или невзвешенным, а все внутренние вершины имеют степень 3. | Вначале определим расстояние обмена ближайшими соседями и расстояние переноса поддеревьев с линейной стоимостью для невзвешенных деревьев; затем расширим эти понятия на взвешенные деревья. Далее будет считаться, что эволюционное (или [[филогенетическое дерево|филогенетическое]]) дерево является неупорядоченным, имеет листья с уникальными метками и непомеченные внутренние вершины, может быть корневым или некорневым, взвешенным или невзвешенным, а все внутренние вершины имеют степень 3. | ||
Строка 16: | Строка 19: | ||
Операция обмена ближайшими соседями (nni) обменивает два поддерева, разделенных внутренним ребром (u, v), как показано на рис. 1. | Операция обмена ближайшими соседями (nni) обменивает два поддерева, разделенных внутренним ребром (u, v), как показано на рис. 1. | ||
Считается, что операция nni действует на это внутреннее ребро. Расстояние nni | |||
Считается, что операция nni действует на это внутреннее ребро. Расстояние обмена ближайшими соседями, [[D_{nni}(T_1, T_2) \;]], между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> определяется как минимальное число операций nni, необходимое для преобразования одного дерева в другое. | |||
Операцию обмена ближайшими соседями также можно рассматривать как перемещение поддерева за соседнюю внутреннюю вершину. Более общая операция перемещает поддерево из одной точки дерева в другую произвольную точку. На рис. 2 представлена такая операция переноса поддерева. | Операцию обмена ближайшими соседями также можно рассматривать как перемещение поддерева за соседнюю внутреннюю вершину. Более общая операция перемещает поддерево из одной точки дерева в другую произвольную точку. На рис. 2 представлена такая операция переноса поддерева. | ||
Строка 26: | Строка 30: | ||
Расстояние переноса поддеревьев между двумя деревьями | Расстояние переноса поддеревьев между двумя деревьями <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]. | ||
Строка 36: | Строка 40: | ||
'''Взвешенные деревья''' | '''Взвешенные деревья''' | ||
Модели обмена ближайшими соседями и переноса поддеревьев с линейной стоимостью можно естественным образом расширить на взвешенные деревья. В первом случае расширение выполнить несложно: операции nni просто присваивается стоимость, равная весу ребра, над которым она производится. Чтобы обмен ближайшими соседями между взвешенными деревьями | Модели обмена ближайшими соседями и переноса поддеревьев с линейной стоимостью можно естественным образом расширить на взвешенные деревья. В первом случае расширение выполнить несложно: операции 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> совпадают. | ||
правок