Супердерево максимального соответствия: различия между версиями

Пусть T – дерево, листья которого уникальным образом снабжены метками из набора таксонов S. Под уникальным образом мы понимаем то обстоятельство, что в T нет двух листьев с одинаковыми метками. Если дано подмножество S' множества S, то топологическое ограничение T согласно S' (обозначается T|S') представляет собой дерево, полученное в результате удаления из T всех вершин, не лежащих ни на одном пути из корня к листу из подмножества S', вместе с инцидентными им ребрами, и последующего сжатия каждого ребра между вершиной, имеющей только одного потомка, и самим этим потомком (см. рисунок). Для любого дерева T обозначим множество меток его листьев как <math>\Lambda (T) \;</math>.

Пусть T – исходное дерево с левой стороны. Тогда дерево справа T|{a, c, d} – это топологическое ограничение дерева T.

Задача 1. Пусть <math>D = \{ T_1, T_2, ..., T_k \} \;</math> – множество корневых неупорядоченных деревьев, в котором каждое дерево <math>T_i \;</math> имеет уникальные метки листьев, при этом множества меток листьев <math>\Lambda (T_i) \;</math> могут перекрываться. Задача нахождения супердерева максимального соответствия заключается в построении дерева <math>Q \;</math> с уникальными метками листьев, с множеством меток листьев <math>\Lambda (Q) \subseteq \bigcup_{T_i \in D} \Lambda (T_i) \;</math>, таким, что <math>| \Lambda (Q) | \;</math> максимально и для каждого <math>T_i \in D \;</math> топологическое ограничение <math>T_i \;</math> согласно <math>\Lambda (Q) \;</math> изоморфно топологическому ограничению <math>Q \;</math> согласно <math>\Lambda (T_i) \;</math>.

Далее будут использоваться следующие обозначения: <math>n = | \bigcup_{T_i \in D} \Lambda (T_i) | \;</math>, <math>k = | D | \;</math> и <math>D = max_{T_i \in D} \big\{ deg(T_i) \big\} \;</math>, где <math>deg(T_i) \;</math> – степень <math>T_i \;</math>.

'''Лемма 1 ([8])'''. Для любого множества <math>D = \{ T_1, T_2, ..., T_k \} \;</math> корневых неупорядоченных деревьев с уникальными метками листьев, таких, что <math>\Lambda(T_1) = \Lambda(T_2) = ... = \Lambda(T_k) \;</math>, оптимальное решение задачи MASP для D является оптимальным решением задачи MAST для D, и наоборот.

'''Теорема 2. ([8])''' Если k = 2 (имеются два дерева), супердерево максимального соответствия может быть найдено за время <math>O(T_{MAST} + n) \;</math>, где <math>T_{MAST} \;</math> – время, необходимое для вычисления поддерева максимального соответствия двух деревьев с O(n) листьями. Заметим, что <math>T_{MAST} = O( \sqrt{Dn} \; log(2n/D)) \;</math> (см. [9]).

 

'''Теорема 3 ([1])'''. Для любого фиксированного k > 2 в случае, если каждый лист D встречается в 1 дереве либо в k деревьев, супердерево максимального соответствия может быть найдено за время <math>O(T'_{MAST} + kn) \;</math>, где <math>T'_{MAST} \;</math> – время, необходимое для вычисления поддерева максимального соответствия k деревьев с метками листьев из <math>\bigcap_{T_i \in D} \Lambda(T_i) \;</math>. Заметим, что <math>T'_{MAST} = O(km^3 + m^D) \;</math>, где <math>n = | \bigcap_{T_i \in D} \Lambda(T_i) | \;</math> (см. [4]).

Для случая, когда множество k бинарных деревьев T имеют степень D и n различных меток листьев, Хоанг и Сунг [7] предложили следующее решение для нахождения MASP с фиксированными параметрами и полиномиальным временем выполнения.

'''Задача 2'''. Пусть <math>D = \{ T_1, T_2, ..., T_k \} \;</math> – множество корневых неупорядоченных деревьев, в котором каждое дерево <math>T_i \;</math> имеет уникальные метки листьев, при этом множества меток листьев <math>\Lambda(T_i) \;</math> могут перекрываться. Задача нахождения супердерева максимальной совместимости (MCSP) заключается в построении дерева <math>Q \;</math> с уникальными метками листьев, с множеством меток листьев <math>\Lambda(Q) \subseteq \bigcup_{T_i \in D} \Lambda(T_i) \;</math>, таким, что <math>| \Lambda(Q) | \;</math> максимально и для каждого <math>T_i \in D \;</math> топологическое ограничение поддерева <math>Q_i' \;</math> дерева <math>Q \;</math> согласно <math>\Lambda(T_i) \;</math> уточняет топологическое ограничение <math>T'_i \;</math> согласно <math>T_i \;</math>; иначе говоря, <math>T'_i \;</math> может быть получено путем коллапсирования определенных ребер <math>Q'_i \;</math>.