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

• вычисление расстояния обмена ближайшими соседями является NP-полной задачей, однако допускает возможность разрешимости с фиксированными параметрами и применение алгоритмов аппроксимации с логарифмическими коэффициентами;

• Предположим, что <math>D_{nni}(T_1, T_2) < d \;</math>. Тогда оптимальная последовательность операций обмена ближайшими соседями, преобразующая <math>T_1 \;</math> в <math>T_2 \;</math>, может быть вычислена за время <math>O(n^2 log \; n + n \cdot 2^{23d/2})</math>.

Еще одна мотивация для исследований в области вычисления расстояния переноса поддеревьев с линейной стоимостью заключается в следующем. Когда в процессе эволюции происходит [[рекомбинация ДНК]], две последовательности встречаются и генерируют новую последовательность, состоящую из генетического материала, взятого слева от точки рекомбинации первой последовательности и справа от точки рекомбинации второй последовательности [5, 6]. С филогенетической точки зрения перед рекомбинацией наследственный материал существующей последовательности был расположен на двух последовательностях – на одной он располагался слева от точки рекомбинации, на второй – справа от точки разрыва. В результате эволюционная история уже не может описываться одним деревом. Событие рекомбинации разбивает последовательности на две соседствующие области. История левой и правой областей может быть описана разными эволюционными деревьями.  Рекомбинация создает различие между эволюционными деревьями, описывающими соседние области. Однако два соседних дерева не могут различаться произвольным образом; одно должно получаться из другого при помощи операции переноса поддеревьев. Когда происходит более одной рекомбинации, описать эволюционную историю можно при помощи списка эволюционных деревьев, каждое из которых соответствует некоторой области последовательностей, и каждое из которых может быть получено из предшественника путем нескольких операций переноса поддеревьев [6]. Вычисление расстояния переноса поддеревьев с линейной стоимостью полезно при реконструкции такого списка деревьев на базе подхода с максимальной экономичностью [5,6].

1. Существует ли алгоритм аппроксимации с константным коэффициентом для вычисления расстояния обмена ближайшими соседями на невзвешенных эволюционных деревьях, или O(log n)-аппроксимация – лучшая из всех?

2. Является ли вычисление расстояния переноса поддеревьев с линейной стоимостью на взвешенных эволюционных деревьях NP-полной задачей, если неуникальные метки листьев не допускаются?

* ''[[Построение галловой филогенетической сети]]