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

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

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

Расстояние переноса поддеревьев между двумя деревьями <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].

В случае переноса поддеревьев с линейной стоимостью кажется логичным, чтобы за перемещение поддерева взималась «плата» в соответствии с пройденным им расстоянием, однако стоит дать более формальное определение. Рассмотрим (некорневые) деревья, в которых каждому ребру <math>e \;</math> приписан вес <math>w(e) \ge 0 \;</math>. Для того чтобы одно дерево можно было преобразовать в другое, необходимо, чтобы полный вес всех ребер был равен единице. Теперь перенос поддеревьев можно определить следующим образом. Выберите поддерево S дерева T в заданной вершине u, выберите ребро <math>e \notin S \;</math>. Расщепите ребро <math>e \;</math> на два ребра <math>e_1 \;</math> и <math>e_2 \;</math> с весами <math>w(e_1) \;</math> и <math>w(e_2) \;</math> <math>(w(e_1), w(e_2) \ge 0,w(e_1) + w(e_2) = w(e))</math>, и переместите S в общую конечную точку <math>e_1 \;</math> и <math>e_2 \;</math>. После этого выполните слияние двух оставшихся ребер e' и e'', смежных с u, в одно ребро с весом w(e') + w(e''). Стоимость этого переноса поддеревьев представляет собой сумму весов всех ребер, через которые перемещается S. Пример переноса приведен на рис. 1. Веса ребер исходного дерева нормализованы, чтобы их общая сумма была равна 1. Поддерево S переносится таким образом, что ребро <math>e_4 \;</math> разбивается на <math>e_6 \;</math> и <math>e_7 \;</math>, при этом <math>w(e_6), w(e_7) \ge 0 \;</math> и <math>w(e_6) + w(e_7) = w(e_4) \;</math> наконец, два ребра <math>e_1 \;</math> и <math>e_2 \;</math> сливаются вместе, образуя ребро <math>e_5 \;</math>, такое, что <math>w(e_5) = w(e_1) + w(e_2) \;</math>. Стоимость переноса S составит <math>w(e_2) + w(e_3) + w(e_6) \;</math>.

Теорема 1 ([2, 3, 4]). Предположим, что деревья <math>T_1 \;</math> и <math>T_2 \;</math> невзвешенные. Тогда верны следующие утверждения:

• Предположим, что <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>.

Теорема 2 ([1, 2, 3, 4]). Предположим, что деревья <math>T_1 \;</math> и <math>T_2 \;</math> взвешенные. Тогда верны следующие утверждения:

Здесь рассматриваются результаты, касающиеся связанных с преобразованиями расстояний для эволюционных деревьев. Такие деревья могут быть корневыми, если известно эволюционное происхождение, а также взвешенными, если известна продолжительность эволюции по каждому ребру. Реконструкция корректного эволюционного дерева для множества видов является одной из фундаментальных, и при этом весьма сложных, проблем эволюционной генетики. За последние десятилетия было разработано несколько подходов к реконструкции эволюционных деревьев, основанных на таких критериях, как максимальные экономичность, совместимость, расстояние и правдоподобие. Результаты применения этих подходов обычно зависят от объема данных и вычислительных ресурсов, использовавшихся в расчетах. В результате на практике из одних и тех же множеств видов нередко получаются разные эволюционные деревья [ ]. Таким образом, представляет интерес возможность сравнения эволюционных деревьев, полученных при помощи разных методов либо при помощи одного и того же метода, но на разных данных.

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

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

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

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