Поддерево максимального соответствия (для трех или более деревьев)

Ключевые слова и синонимы: выравнивание деревьев

Постановка задачи

Задача нахождения поддерева максимального соответствия для k деревьев (k-MAST) представляет собой обобщение подобной же задачи для двух деревьев (Maximum Agreement Subtree, MAST). Рассмотрим кортеж из k корневых деревьев с помеченными листьями [math]\displaystyle{ (T_1, T_2, ..., T_k) \; }[/math]. Пусть [math]\displaystyle{ A = \{ a_1, a_2, ..., a_n \} \; }[/math] – множество меток листьев. Любое подмножество [math]\displaystyle{ B \subseteq A \; }[/math] уникальным образом определяет так называемое топологическое ограничение T|B дерева T согласно B. А именно, T|B является топологическим поддеревом T, натянутым на все листья, помеченные элементами из B, и самых низких общих предков всех пар этих листьев. Отношение наследования в T|B определяется таким образом, чтобы оно было согласовано с отношением наследования в T. Подмножество B множества A, такое, что [math]\displaystyle{ T^1|B, ..., T^k|B \; }[/math] являются изоморфными, называется множеством соответствия.

Задача 1 (k-MAST)

Дано: Кортеж [math]\displaystyle{ \overrightarrow{T} = (T^1, ..., T^k) \; }[/math] деревьев с помеченными листьями, с общим набором меток [math]\displaystyle{ A = \{ a_1, ..., a_n \} \; }[/math], таким, что для каждого дерева [math]\displaystyle{ T_i \; }[/math] существует взаимно однозначное отображение между множеством листьев этого дерева и множеством меток A.

Требуется: найти k-MAST(T), равное множеству соответствия максимальной мощности дерева T.

Основные результаты

В общем случае задача k-MAST является NP-полной для [math]\displaystyle{ k \ge 3 \; }[/math] [1]. В предположении, что степень хотя бы одного из деревьев ограничена, Фарах и коллеги предложили алгоритм, на базе которого была сформулирована следующая теорема:

Теорема 1. Если степень деревьев в кортеже [math]\displaystyle{ \overrightarrow{T} = (T^1, ..., T^k) \; }[/math] ограничена числом d, то значение k-MAST(T) может быть вычислено за время [math]\displaystyle{ O(kn^3 + n^d) \; }[/math].

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

Вспомним, что классический динамический алгоритм вычисления MAST для двух бинарных деревьев за время [math]\displaystyle{ O(n^2) \; }[/math] [11] обрабатывает все пары внутренних вершин двух деревьев восходящим образом. Для каждой пары таких вершин он вычисляет значение MAST для поддеревьев, корнями которых являются вершины этой пары. Имеется [math]\displaystyle{ O(n^2) \; }[/math] пар таких вершин; значение MAST для поддеревьев, корнями которых является заданная пара вершин, может быть вычислено за константное время из значений MAST ранее обработанных пар вершин.

Чтобы подготовить почву для более общего случая, обозначим за [math]\displaystyle{ k-MAST(\overrightarrow{v}) \; }[/math] решение задачи k-MAST для поддеревьев [math]\displaystyle{ T^1(v_1), ..., T^k(v_k) \; }[/math], где [math]\displaystyle{ T^i(v_i) \; }[/math] – поддерево [math]\displaystyle{ T^i \; }[/math] с корнем [math]\displaystyle{ v_i \; }[/math]. Если для всех i [math]\displaystyle{ u_i \; }[/math] является непосредственным потомком [math]\displaystyle{ v_i \; }[/math] в [math]\displaystyle{ T^i \; }[/math], то [math]\displaystyle{ \overrightarrow{v} \; }[/math] доминирована [math]\displaystyle{ \overrightarrow{u} \; }[/math] (обозначается [math]\displaystyle{ \overrightarrow{v} \prec \overrightarrow{u} \; }[/math]).

Наивное расширение алгоритма для двух деревьев на алгоритм для k деревьев потребует перевычисления [math]\displaystyle{ k-MAST(\overrightarrow{v}) \; }[/math] для всех возможных кортежей [math]\displaystyle{ \overrightarrow{v} \; }[/math] посредством обработки этих кортежей в порядке, согласующемся с отношением доминирования. Основная идея, позволяющая избежать возникновения сложности [math]\displaystyle{ \Omega (n^k) \; }[/math], заключается в замене вычисления [math]\displaystyle{ k-MAST(\overrightarrow{v}) \; }[/math] вычислением связанного с ним значения, [math]\displaystyle{ mast(\overrightarrow{v}) \; }[/math], представляющего собой размер максимального множества соответствия для поддеревьев [math]\displaystyle{ (T^1, ..., T^k) \; }[/math] с корнями в [math]\displaystyle{ (v_1, ..., v_k) \; }[/math], при условии дополнительного ограничения, заключающегося в том, что сами поддеревья соответствия имеют корни в [math]\displaystyle{ v_1, ..., v_k \; }[/math], соответственно. Очевидно, что [math]\displaystyle{ k-MAST(T^1, ..., T^k) = max_{\overrightarrow{v}} \; mast(\overrightarrow{v}) \; }[/math] .

Преимущество вычисления mast вместо k-MAST следует из того факта, что большинство значений mast являются нулевыми и можно достаточно эффективно определить [math]\displaystyle{ \overrightarrow{v} \; }[/math] с ненулевыми значениями mast.

Примечание 1. Если [math]\displaystyle{ mast(\overrightarrow{v}) \gt 0 \; }[/math], то [math]\displaystyle{ \overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \; }[/math] для некоторых меток листьев a, b, где [math]\displaystyle{ lca^{T^i} (a, b) \; }[/math] – самый низкий общий предок листьев с метками a и b в дереве V.

Кортеж [math]\displaystyle{ \overrightarrow{v} \; }[/math], такой, что [math]\displaystyle{ \overrightarrow{v} = (lca^{T^1} (a, b), ..., lca^{T^k} (a, b)) \; }[/math] для некоторых [math]\displaystyle{ a, b \in A \; }[/math], называется lca-кортежем. Согласно примечанию 1, достаточно вычислить значения mast только для lca-кортежей. Как и при использовании наивного подхода, [math]\displaystyle{ mast(\overrightarrow{v}) \; }[/math] вычисляется из значений mast других lca-кортежей, доминируемых [math]\displaystyle{ \overrightarrow{v} \; }[/math]. Еще одно важное наблюдение заключается в том, что для вычисления [math]\displaystyle{ mast(\overrightarrow{v}) \; }[/math] необходимы только некоторые lca-кортежи, доминируемые [math]\displaystyle{ \overrightarrow{v} \; }[/math]. Чтобы реализовать его, Фарах и коллеги определяют так называемое отношение истинного доминирования и показывают, что значение mast для любого lca-кортежа [math]\displaystyle{ \overrightarrow{v} \; }[/math] может быть вычислено из значений mast lca-кортежей, истинно доминируемых [math]\displaystyle{ \overrightarrow{v} \; }[/math], и что отношение истинного доминирования имеет размер [math]\displaystyle{ O(n^3) \; }[/math].

Отношение истинного доминирования

Проиндексируем потомков каждой внутренней вершины любого дерева на произвольном пути. Пусть имеется пара [math]\displaystyle{ \overrightarrow{v}, \overrightarrow{w} }[/math] lca-кортежей, такая, что [math]\displaystyle{ \overrightarrow{w} \prec \overrightarrow{v} \; }[/math]. Соответствующее отношение доминирования ассоциирует ее с направлением [math]\displaystyle{ \overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}} = (\delta_1, ..., \delta_k) }[/math], по которому [math]\displaystyle{ \overrightarrow{w_i} \; }[/math] спускается от потомка [math]\displaystyle{ v_i \; }[/math], индексированного с [math]\displaystyle{ \delta_i \; }[/math]. Пусть [math]\displaystyle{ v_i(j) \; }[/math] – потомок [math]\displaystyle{ v_i \; }[/math] с индексом [math]\displaystyle{ j \; }[/math]. Доминирование по направлению считается активным, если поддеревья с корнями в [math]\displaystyle{ v_1(\delta_1),..., v_к(\delta+k) \; }[/math] имеют по меньшей мере одну общую метку листа. Заметим, что каждая метка листа может обозначать только одно активное направление и, следовательно, каждый lca-кортеж может иметь не более и активных направлений доминирования. Два направления [math]\displaystyle{ \overrightarrow{\delta}_{\overrightarrow{w} \prec \overrightarrow{v}} }[/math] и [math]\displaystyle{ \overrightarrow{\delta}_{\overrightarrow{u} \prec \overrightarrow{v}} }[/math] называются совместимыми в том и только том случае, если векторы направлений различаются по всем координатам.

Определение 1. [math]\displaystyle{ \overrightarrow{v} \; }[/math] истинно доминирует [math]\displaystyle{ \overrightarrow{u} \; }[/math] (обозначается [math]\displaystyle{ \overrightarrow{u} \lt \overrightarrow{v} \; }[/math]), если [math]\displaystyle{ \overrightarrow{v} \; }[/math] доминирует [math]\displaystyle{ \overrightarrow{u} \; }[/math] по активному направлению [math]\displaystyle{ \overrightarrow{ \delta } }[/math] и существует другой кортеж, [math]\displaystyle{ \overrightarrow{w} \; }[/math], также доминируемый [math]\displaystyle{ \overrightarrow{v} \; }[/math] по активному направлению [math]\displaystyle{ \overrightarrow{ \delta_{\bot}} }[/math], совместимому с [math]\displaystyle{ \delta \; }[/math].

На основе определения истинного доминирования и того факта, что каждая метка листа может относиться только к одному активному направлению доминирования, можно сделать следующие наблюдения:

Примечание 2. Отношение строгого доминирования [math]\displaystyle{ \lt \; }[/math] на lca-кортежах имеет размер [math]\displaystyle{ O(n^3) \; }[/math]. Кроме того, оно может быть вычислено за время [math]\displaystyle{ O(kn^3) \; }[/math].

Примечание 3. Для любого lca-кортежа [math]\displaystyle{ \overrightarrow{v} \; }[/math], в случае, если [math]\displaystyle{ mast(\overrightarrow{v}) \gt 0 \; }[/math], имеет место одна из двух ситуаций: (1) [math]\displaystyle{ \overrightarrow{v} \; }[/math] представляет собой lca-кортеж, состоящий из листьев с одной и той же меткой; (2) [math]\displaystyle{ \overrightarrow{v} \; }[/math] истинно доминирует некоторый lca-кортеж.

Остается показать, как можно вычислить значения [math]\displaystyle{ mast(\overrightarrow{v}) \; }[/math]. Для каждого lca-кортежа [math]\displaystyle{ \overrightarrow{v} \; }[/math] строится так называемый граф совместимости [math]\displaystyle{ G(\overrightarrow{v}) \; }[/math]. Вершинами [math]\displaystyle{ G(\overrightarrow{v}) \; }[/math] являются активные направления из [math]\displaystyle{ \overrightarrow{v} \; }[/math]; между двумя вершинами имеется ребро в том и только том случае, если соответствующие направления совместимы. Вершины [math]\displaystyle{ G(\overrightarrow{v}) \; }[/math] имеют веса; вес вершины, соответствующей активному направлению [math]\displaystyle{ \overrightarrow{ \delta } \; }[/math], равен максимальному значению mast lca-кортежа, доминируемого v по этому направлению. Пусть [math]\displaystyle{ MWC(G(\overrightarrow{v})) \; }[/math] – клика с максимальным весом в [math]\displaystyle{ G(\overrightarrow{v}) \; }[/math].

Восходящий алгоритм вычисления ненулевых значений mast основан на следующей рекурсивной зависимости, корректность которой непосредственно задают соответствующие определения и Примечание 3.

Лемма 2. Для любого lca-кортежа [math]\displaystyle{ \overrightarrow{v} \; }[/math] [math]\displaystyle{ mast(\overrightarrow{v}) = max \{ 1, }[/math] если все элементы [math]\displaystyle{ \overrightarrow{v} \; }[/math] являются листьями; [math]\displaystyle{ MWC(G(\overrightarrow{v})) \; }[/math] в противном случае[math]\displaystyle{ \} \; }[/math]

Наконец, остается продемонстрировать, что после того, как lca-кортежи и отношение строгого доминирования предварительно вычислены, вычисление всех ненулевых значений mast может быть выполнено за время [math]\displaystyle{ O(n^d) \; }[/math]. Это производится при помощи генерации всех возможных клик для всех значений [math]\displaystyle{ G(\overrightarrow{v}) \; }[/math]. Используя тот факт, что степень по меньшей мере одного дерева ограничена [math]\displaystyle{ d \; }[/math], можно показать, что все клики могут быть сгенерированы за время [math]\displaystyle{ O \bigg( \sum_{l \le d} \binom{n}{l}) = O(d^3(ne/d)^d \bigg) \; }[/math] и что их имеется [math]\displaystyle{ O(d(ne/d)^d) \; }[/math] штук [6].

Применение

Актуальность задачи k-MAST связана с необходимостью сравнения эволюционных деревьев. Недавние достижения в разработке экспериментальных техник в молекулярной биологии дали много разных данных, которые могут быть использованы для построения эволюционных деревьев. Разнообразие данных в сочетании с разнообразием методов построения эволюционных деревьев нередко приводит к ситуации, когда эволюция одного и того же множества видов объясняется различными эволюционными деревьями. Задача нахождения поддерева максимального соответствия возникла как способ нахождения соответствия между подобными деревьями и как метод определения общего для таких деревьев поддерева. Эта задача впервые была определена Финденом и Гордоном в контексте двух бинарных деревьев [7]. Авторы также предложили эвристический алгоритм решения задачи. Динамический алгоритм вычисления значений MAST для двух бинарных деревьев за время [math]\displaystyle{ O(n^2) \; }[/math] был изложен в [11]. Впоследствии было предложено несколько усовершенствований для повышения скорости работы алгоритмов вычисления значений MAST для двух деревьев в свете различных предположений о корнях и о степенях деревьев [5, 10, 8 и список литературы в них].

Задача нахождения MAST для трех и более деревьев с неограниченными степенями является NP-полной [1]. Амир и Кеселман предложили алгоритм для k деревьев с ограниченными степенями сложности [math]\displaystyle{ O(kn^{d+1} + n^2d) =; }[/math]. Описанный здесь алгоритм обеспечивает время [math]\displaystyle{ O(kn^3 + n^d) \; }[/math] для случая, когда число деревьев равно k и степень хотя бы одного дерева ограничена [math]\displaystyle{ d \; }[/math]. Для [math]\displaystyle{ d = 2 \; }[/math] сложность алгоритма зависит от первого терма. Алгоритм сложности [math]\displaystyle{ O(kn^3) \; }[/math] для данного случая был предложен Брайантом [4], реализация этого алгоритма со сложностью [math]\displaystyle{ O(n^2 \; log^{k-1} \; n) }[/math] изложена в [9].

Задача k-MAST является разрешимой при помощи алгоритмов с фиксированным параметром p, где p – наименьшее количество меток листьев, таких, что удаление соответствующих листьев приводит к возникновению соответствия (см. [3] и список литературы). Возможность аппроксимации MAST и соответствующая задача изучались в [2] и литературе по списку.

См. также

• Поддерево максимального соответствия (для двух бинарных деревьев)
• Супердерево максимального соответствия
• Дерево максимальной совместимости

Литература

1. Amir, A., Keselman, D.: Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM J. Comput. 26(6), 1656-1669 (1997)

2. Berry, V., Guillemot, S., Nicolas, F., Paul, C.: On the approximation of computing evolutionary trees. In: COCOON, pp. 115-125.(2005)

3. Berry, V., Nicolas, F.: Improved parameterized complexity of the maximum agreement subtree and maximum compatible tree problems. IEEE/ACM Trans. Comput. Biology Bioinform. 3(3), 289-302 (2006)

4. Bryand, D.: Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis. In: Ph.D. thesis, Dept. Math., University of Canterbury (1997)

5. Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T., Thorup, M.: An o(n log n) algorithm for the maximum agreement subtree problem for binary trees. SIAM J. Comput., pp. 1385-1404. (2001)

6. Farach, M., Przytycka, T.M., Thorup, M.: On the agreement of many trees. Inf. Process. Lett. 55(6), 297-301 (1995)

7. Finden, C.R., Gordon, A.D.: Obtaining common pruned trees. J.Classific. 2, 255-276 (1985)

8. Kao, M.-Y., Lam, T.-W., Sung, W.-K., Ting, H.-F.: An even faster and more unifying algorithm for comparing trees via unbalanced bipartite matchings.J.Algorithms 40(2),212-233 (2001)

9. Lee, C.-M., Hung, L.-J., Chang, M.-S., Tang, C.-Y.: An improved algorithm for the maximum agreement subtree problem. BIBE, p. 533 (2004)

10. Przytycka, T.M.:Transforming rooted agreement into unrooted agreement. J. Comput. Biol. 5(2), 335-349 (1998)

11. Steel, M.A., Warnow, T.: Kaikoura tree theorems: Computing the maximum agreement subtree. Inf. Process. Lett. 48(2), 77-82(1993)