Соглашение о лесе

В математической области теории графов для лес согласия двух данных (помеченных листьями, неприводимых) деревьев — это любой (помеченный листьями, неприводимый) лес , который, неформально говоря, может быть получен из обоих деревьев путем удаления общего числа ребер. .

Согласованные леса впервые возникли при изучении комбинаторных задач, связанных с вычислительной филогенетикой , в частности перестановок деревьев . ^{[ 1 ]}

Предварительные сведения

Напомним, что дерево (или лес) является неприводимым , если в нем отсутствует какой-либо внутренний узел степени 2. В случае корневого дерева (или корневого леса) корень (корни), конечно, могут иметь степень 2, поскольку они не являются внутренними узлами. Любое дерево (или лес) можно сделать несводимым, применив последовательность сокращений ребер .

Неприводимое (корневое или некорневое) дерево $T$ , листья которого взаимно помечены элементами множества $X,$ называется (корневым или некорневым) $X$ -деревом . Такое $X$ -дерево обычно моделирует филогенетическое дерево , где элементы $X$ ( набор таксонов ) могут представлять виды, отдельные организмы, последовательности ДНК или другие биологические объекты.

Два $X$ -дерева $T 1$ и $T 2$ называются изоморфными, если между ними существует изоморфизм графов , сохраняющий метки листов. В случае корневых $X-$ деревьев изоморфизм также должен сохранять корень.

Учитывая $X$ -дерево $T$ и подмножество таксонов $Y \subseteq X$ , минимальное поддерево $T$ , которое соединяет все листья в $Y,$ обозначается $T(Y)$ . Когда $T$ является корневым, тогда $T(Y)$ также является корневым, причем его корнем является узел, ближайший к исходному корню $T$ . Это $поддерево T(Y)$ не обязательно должно быть $Y$ -деревом, поскольку оно может оказаться несократимым. Поэтому мы далее определяем ограниченное поддерево $T|Y$ , которое получается из $T(Y)$ путем подавления всех внутренних узлов степени 2, что дает правильное $Y$ -дерево.

Соглашение о лесах

Лес согласия для двух некорневых $X$ -деревьев $T 1$ и $T 2$ представляет собой разбиение ${X 1, X 2, ..., X k$ } таксонного множества $X,$ удовлетворяющее следующим условиям:

$T 1 |X i$ и $T 2 |X i$ изоморфны для каждого $i \in {1,2,...,k}$ и
поддеревья в ${T 1 (X i) : i \in {1,2,...,k} }$ и ${ T 2 (X i) : i \in {1,2,...,k} }$ являются вершинами -непересекающиеся поддеревья $T 1$ и $T 2$ соответственно.

Разбиение множества ${X 1, X 2, ..., X k$ } отождествляется с лесом ограниченных поддеревьев $F = {T|X 1, T|X 2, ..., T|X k$ }, либо с $Т=Т 1$ или $Т=Т 2$ (выбор становится неактуальным из-за условия 1). Следовательно, лес согласия можно рассматривать либо как часть набора таксонов $X$ , либо как лес (в классическом смысле теории графов) ограниченных поддеревьев.

Размер леса соглашений — это просто количество его компонентов. Интуитивно понятно, что лес согласия размера $k$ для двух филогенетических деревьев — это лес, который можно получить из обоих деревьев путем удаления $(k-1)$ ребер в каждом дереве и последующего подавления внутренних узлов степени $2$ .

Укорененный случай

Ациклические соглашения о лесах

Можно уточнить приведенное выше определение, в результате чего появится концепция леса ациклических соглашений. Лес согласия $F$ для двух $X$ -деревьев $T 1$ и $T 2$ называется ациклическим, если каждый из его компонентов дерева может быть пронумерован таким образом, что если корень одного компонента $X i \in F$ является предком корня другой компонент $X j \in F$ либо в $T 1 ,$ либо $в T 2$ , то номер, присвоенный $X i,$ меньше, чем номер, присвоенный $X j$ .

Другая характеристика ацикличности в лесу согласия заключается в рассмотрении ориентированного графа $GF,$ который имеет множество вершин $F$ и направленное ребро $(X i, X j),$ если и только если $i \neq j$ и выполняется хотя бы одно из двух следующих условий:

корень $T 1 (X i)$ является предком корня $T 1 (X j)$ в $T 1$
корень $T 2 (X i)$ является предком корня $T 2 (X j)$ в $T 2$

Ориентированный граф $GF GF$ называется графом наследования, связанным с лесом согласия $F$ мы называем $F$ ациклическим, если $не, и$ имеет ориентированного цикла.

Проблемы оптимизации

Лес соглашения $F$ (корневой, некорневой, ациклический) для $T 1$ и $T 2$ называется максимальным , если он содержит наименьшее возможное количество элементов (т. е. имеет наименьший размер). В этом контексте максимизируется согласие между двумя деревьями: это объясняет, почему вычисление леса максимального согласия на самом деле означает минимизацию количества его компонентов. Это приводит к двум различным (но связанным) проблемам оптимизации. В обоих случаях мы решили минимизировать $| Ф | - 1,$ а не $| Ф |$ , поскольку первое соответствует количеству разрезов, которые необходимо сделать в каждом дереве, чтобы получить $F$ .

максимальный ≠ максимум
нерутированный MAF соответствует TBR
укорененный MAF соответствует rSPR
ациклический MAF соответствует HYB
AF можно определить на небинарных деревьях.
AF могут быть определены более чем на двух деревьях.
леса с ациклическим соглашением играют роль в вычислении HYB для 3 или более деревьев, но связь намного слабее, чем в случае с 2 деревьями.
Сложность
Алгоритмы FPT
Алгоритмы аппроксимации
Алгоритмы экспоненциального времени

Примечания

^ Йотун Хейн; Тао Цзян; Лушэн Ван; Кайчжун Чжан (1996). «О сложности сравнения эволюционных деревьев» . Дискретная прикладная математика . 71 (1–3): 153–169. дои : 10.1016/S0166-218X(96)00062-5 .

[complexity1996-1] Йотун Хейн; Тао Цзян; Лушэн Ван; Кайчжун Чжан (1996). «О сложности сравнения эволюционных деревьев» . Дискретная прикладная математика . 71 (1–3): 153–169. дои : 10.1016/S0166-218X(96)00062-5 .

[ 1 ]