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

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

Рассмотрим два корневых дерева [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math] с n листьями у каждого. Внутренние вершины каждого дерева имеют не менее двух потомков. Листья каждого дерева помечены метками из одного и того же множества меток, ни одна конкретная метка в дереве не повторяется более одного раза. Поддерево соответствия [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math] определяется следующим образом. Пусть [math]\displaystyle{ L_1 \; }[/math] – подмножество листьев [math]\displaystyle{ T_1 \; }[/math], а [math]\displaystyle{ L_2 \; }[/math] – подмножество тех листьев [math]\displaystyle{ T_2 \; }[/math], которые имеют те же метки, что и листья в [math]\displaystyle{ L_1 \; }[/math]. Поддерево [math]\displaystyle{ T_1 \; }[/math], порожденное [math]\displaystyle{ L_1 \; }[/math], представляет собой поддерево соответствия [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math] в том и только том случае, если оно изоморфно поддереву [math]\displaystyle{ T_2 \; }[/math], порожденному [math]\displaystyle{ L_2 \; }[/math]. Задача нахождения поддерева максимального соответствия (Maximum Agreement Subtree, MAST) пытается найти наибольшее поддерево соответствия [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math].

Термины «порожденное поддерево» и «изоморфизм» нуждаются в определении. Интуитивно поддерево T, порожденное подмножеством L листьев T, представляет собой топологическое поддерево T, элементами которого являются только листья из L, сохраняющее информацию о ветвлении, относящуюся к L. Более формально, для любых двух листьев a, b дерева T обозначим за [math]\displaystyle{ lca_T (a, b) \; }[/math] их самого низкого общего предка в T. Если a = b, [math]\displaystyle{ lca_T(a, b) = a \; }[/math]. Поддерево U дерева T, порожденное подмножеством листьев L, представляет собой дерево с множеством листьев L и множеством внутренних вершин [math]\displaystyle{ \{ lca_T(a, b) | a, b \in L \} \; }[/math], наследующее отношение родства от T, то есть для всех [math]\displaystyle{ a, b \in L, lca_U(a, b) = lca_T(a, b) \; }[/math].

Интуитивно два дерева представляются изоморфными, если потомки каждой вершины одного из деревьев могут быть переупорядочены таким образом, что метки листьев в каждом дереве идут в одном и том же порядке и формы двух деревьев становятся идентичными. Формально два дерева [math]\displaystyle{ U_1 \; }[/math] и [math]\displaystyle{ U_2 \; }[/math] с одним и тем же набором меток листьев называются изоморфными, если существует взаимно однозначное отображение [math]\displaystyle{ \mu \; }[/math] между их вершинами, отображающее листья на листья с теми же метками, такое, что для любых двух различных листьев [math]\displaystyle{ a, b \in U_1, \mu (lca_{U_1} (a, b)) = lca_{U_2} (\mu (a), \mu (b)) \; }[/math].

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

Финден и Гордон [8] предложили эвристический алгоритм для решения задачи MAST на бинарных деревьях с временем выполнения [math]\displaystyle{ O(n^5) \; }[/math], не гарантирующий оптимального решения. Кубицка, Кубицкий и Макморрис [13] предложили алгоритм с временем [math]\displaystyle{ O(n^{(0,5 + \epsilon) log \; n)} }[/math] для той же задачи. Первый алгоритм решения этой задачи за полиномиальное время разработали Стил и Уорноу [15]; время его выполнения составляло [math]\displaystyle{ O(n^2) \; }[/math]. Стил и Уорноу также рассматривали случаи небинарных и некорневых деревьев. Этот алгоритм требует [math]\displaystyle{ O(n^2) \; }[/math] времени для корневых и некорневых деревьев с фиксированной степенью и [math]\displaystyle{ O(n^{4,5 \; log \; n} ) }[/math] для корневых и некорневых деревьев произвольной степени. Кроме того, они предложили линейную редукцию от корневого дерева к некорневому. Фарак и Торуп предложили алгоритм с временем выполнения [math]\displaystyle{ O(nc^{\sqrt{log \; n}}) }[/math] для решения задачи MAST на бинарных деревьях, где [math]\displaystyle{ c \; }[/math] – константа величиной больше 1. Для деревьев с произвольной степенью этот алгоритм требует [math]\displaystyle{ O(n^2 c^{\sqrt{log \; n}}) \; }[/math] времени для некорневого случая [6] и [math]\displaystyle{ O(n^{1,5 \; log \; n}) }[/math] – для корневого [7]. Фарак, Пжытычка и Торуп получили алгоритм с временем выполнения [math]\displaystyle{ O(n \; log^3 n) \; }[/math] для решения задачи MAST на бинарных деревьях. Као [12] удалось получить алгоритм для этой же задачи с временем выполнения [math]\displaystyle{ O(n \; log^2 \; n) \; }[/math]. Для деревьев степени d он выполняется за время [math]\displaystyle{ O(min \{ n d^2 \; log \; d \; log^2 n, n d^{3/2} \; log^3 n \} ) }[/math].

Также была исследована задача MAST для более чем двух деревьев. Амир и Кеселман [1 ] показали, что проблема является NP-полной даже для трех деревьев с неограниченной степенью. Однако для трех или более деревьев с ограниченной степенью известны полиномиальные алгоритмы [1, 5].

Далее представлен алгоритм Коула и Харихарана для решения задачи MAST на двух бинарных деревьях. Он был получен в результате модернизации алгоритма с временем [math]\displaystyle{ O(n \; log^3 n) \; }[/math] [4] (финальная журнальная версия [3] представляет собой сочетание обеих работ). Алгоритм с временем выполнения [math]\displaystyle{ O(n \; log^3 n) \; }[/math] из [4] использует следующий подход (хотя авторы и не излагали его в таком виде). Он определяет два специальных случая и затем решает задачу для общего случая путем интерполяции этих специальных случаев.

Специальный случай 1: внутренние вершины обоих деревьев формируют путь. Задача MAST в этом случае фактически сводится к задаче нахождения самой длинной возрастающей последовательности в графе размера n. Хорошо известно, что она может быть решена за время [math]\displaystyle{ O(n \; log \; n) }[/math].

Специальный случай 2: оба дерева, [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math], являются полными бинарными деревьями. Для каждой вершины v дерева [math]\displaystyle{ T_2 \; }[/math] только определенные вершины u в [math]\displaystyle{ T_1 \; }[/math] могут быть отображены на v практичным образом, в том смысле, что поддерево [math]\displaystyle{ T_1 \; }[/math] с корнем в u и поддерево [math]\displaystyle{ T_2 \; }[/math] с корнем в v имеют непустое поддерево соответствия. Существует [math]\displaystyle{ O(n \; log^2 n) }[/math] таких пар (u, v), что можно показать следующим образом. Заметим, что для того, чтобы две вершины (u, v) составляли такую пару, поддерево [math]\displaystyle{ T_1 \; }[/math] с корнем в u и поддерево [math]\displaystyle{ T_2 \; }[/math] с корнем в v должны иметь общую метку листа. Для каждой метки существуют только [math]\displaystyle{ O(log^2 n) \; }[/math] таких пар, полученных сопряжением каждого потомка листа с этой меткой в дереве [math]\displaystyle{ T_1 \; }[/math] с каждым потомком листа с этой меткой в дереве [math]\displaystyle{ T_2 \; }[/math]. Таким образом, общее число интересных пар составляет [math]\displaystyle{ O(n \; log^2 n) }[/math]. Для каждой пары вычисление MAST требует O(1) времени, поскольку вопрос заключается просто в нахождении лучшего способа сопряжения их потомков.

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

В данной работе были предложены две оптимизации, каждая из которых приводит к сокращению времени выполнения на коэффициент log n.

Оптимизация 1: время выполнения алгоритма для специального случая полных деревьев улучшается до [math]\displaystyle{ O(n \; log \; n) }[/math] следующим образом. Пара вершин (u, v), [math]\displaystyle{ u \in T_1 \; }[/math], [math]\displaystyle{ v \in T_2 \; }[/math], считается интересной, если существует поддерево соответствия, отображающее u на v. Как показано ниже, для полных деревьев общее число интересных пар (u, v) составляет всего [math]\displaystyle{ O(n \; log \; n) }[/math]. Рассмотрим вершину v в дереве [math]\displaystyle{ T_2 \; }[/math]. Пусть [math]\displaystyle{ L_2 \; }[/math] – множество листьев, являющихся потомками v. Пусть [math]\displaystyle{ L_1 \; }[/math] – множество тех листьев [math]\displaystyle{ T_1 \; }[/math], которые имеют те же метки, что и листья в [math]\displaystyle{ L_2 \; }[/math]. Отображены на v могут быть только вершины u, принадлежащие к поддереву [math]\displaystyle{ T_1 \; }[/math], порожденному [math]\displaystyle{ L_1 \; }[/math]. Количество таких вершин составляет O(размер поддерева [math]\displaystyle{ T_2 }[/math] с корнем в v). Таким образом, общее число интересных пар представляет собой сумму всех поддеревьев [math]\displaystyle{ T_2 \; }[/math], или [math]\displaystyle{ O(n \; log \; n) }[/math].

В результате число интересных пар (u, v) сокращается до [math]\displaystyle{ O(n \; log \; n) }[/math]. Обработка одной пары требует O(1) времени (это менее очевидно, поскольку определение потомков вершины u, являющихся корнями поддеревьев, с которыми могут быть сопоставлены два поддерева v, является нетривиальной задачей). Построение вышеописанного порожденного поддерева может быть выполнено за время [math]\displaystyle{ O(|L_1|) \; }[/math], что будет показано далее. Это достигается путем предварительной подготовки деревьев [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math] за время O(n) таким образом, чтобы нахождение наименьшего общего предка занимало O(1) времени.

Оптимизация 2: как и в [4], когда деревья не являются полными бинарными деревьями, алгоритм рассматривает центроидные пути и сопоставляет пары центроидных путей. Стоимость O(log n), которую алгоритм из [4] вносит в обработку каждой такой интересной пары, возникает в случае крупных (полиномиальных относительно n) экземпляров обобщенной задачи нахождения самой длинной возрастающей последовательности. На первый взгляд представляется неочевидным, что крупные экземпляры этой задачи могут возникать для достаточно большого числа интересных пар; к сожалению, на деле это оказывается именно так. Однако эти экземпляры задачи могут иметь определенную структуру. Используя (статические) взвешенные деревья, можно обрабатывать пары интересных вершин за время O(1) в среднем на одну пару с использованием подходящим образом параметризованного анализа.

Случай с более высокой степенью

Эту технику можно обобщить на случаи более высоких степеней d > 2, за счет сочетания ее с техниками из ([6, глава 2]) для неограниченных степеней. Полученный алгоритм теоретически должен выполняться за время [math]\displaystyle{ O(min \{ n \sqrt{d} \; log^2 \; n, nd \; log n \; log \; d \} ) }[/math]; однако на деле время его выполнения составляет [math]\displaystyle{ O(n \sqrt{d} \; log \; n) }[/math].

Применение

Задача нахождения поддерева максимального соответствия естественным образом возникает в биологии и лингвистике; она описывает меру соответствия между двумя эволюционными деревьями видов и языков, соответственно. Эволюционное дерево для набора таксонов (видов или языков) представляет собой корневое дерево, листьями которого являются таксоны, а внутренние вершины содержат информацию о предках. Определение истинного филогенеза набора таксонов нередко вызывает трудности, и одним из вариантов обретения уверенности в правильности конкретного дерева может стать получение нескольких наборов данных в поддержку этого дерева. В случае биологических таксонов можно построить деревья из различных отрезков ДНК нужных видов, называемые деревьями генов. По многим причинам полное согласование таких деревьев невозможно, так что остается задача нахождения консенсуса между различными деревьями генов. Одним из способов нахождения такого консенсуса является поиск поддерева максимального соответствия. Заметим, что дерево генов обычно является бинарным, поскольку репликация ДНК представляет собой процесс бинарного ветвления. Таким образом, случай бинарных деревьев представляет особый интерес.

Еще одним возможным применением является автоматический перевод между двумя языками [10]. Два дерева представляют собой деревья разбора для утверждений с одним и тем же значением на двух языках. Сложность в данном случае связана с несовершенством словарных определений; она заключается в том, что слова не обязательно должны иметь уникальную пару, т.е. слово в листе первого дерева может соответствовать нескольким (обычно их число невелико) словам в листьях второго дерева. Цель состоит в нахождении поддерева максимального соответствия; затем оно будет использоваться для улучшения контекстно-зависимых словарей при автоматическом переводе. В случае, если каждое слово в одном дереве имеет константное число соответствий в другом дереве (возможно, с учетом различных весов), можно использовать вышеприведенный алгоритм, и продолжительность его работы останется равной [math]\displaystyle{ O(n \; log \; n) }[/math]. В более общем случае, если допускается m сопоставленных слов, время работы алгоритма составит [math]\displaystyle{ O((m + n)\; log \; n) }[/math]. Заметим, что при наличии двух наборов слов с равными значениями в двух деревьях размеров [math]\displaystyle{ k_1 \; }[/math] и [math]\displaystyle{ k_2 \; }[/math], соответственно, они порождают [math]\displaystyle{ k_1 k_2 \; }[/math] сопоставлений.

См. также

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

Литература

1. Amir, A., Keselman, D.: Maximum agreement subtree in a set of evolutionary trees. SIAMJ.Comput. 26(6), 1656-1669(1997)

2. Cole, R., Hariharan, R.: An O(nlogn) algorithm for the maximum agreement subtree problem for binary trees. Proc. of the 7th ACM-SIAM SODA, pp. 323-332 (1996)

3. Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T., Thorup, M.: An O(n log n) algorithm for the maximum agreementsubtree problem for binary trees. SI AM J. Comput. 30(5), 1385-1404(2000)

4. Farach, M., Przytycka, T., Thorup, M.: The maximum agreement subtree problem for binary trees. Proc. of 2nd ESA (1995)

5. Farach, M., Przytycka, T., Thorup, M.: Agreement of many bounded degree evolutionary trees. Inf. Process. Lett. 55(6), 297-301 (1995)

6. Farach, M., Thorup, M.: Fast comparison of evolutionary trees. Inf. Comput. 123(1),29-37(1995)

7. Farach, M., Thorup, M.: Sparse dynamic programming for evolutionary-tree comparison. SI AM J. Comput. 26(1), 210-230 (1997)

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

9. Fredman, M.L.: Two applications of a probabilistic search technique: sorting X + Y and building balanced search trees. Proc. of the 7th ACM STOC, pp. 240-244 (1975)

10. Grishman, R., Yangarber, R.: Private Communication. NYU (1995)

11. Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338-355 (1984)

12. Kao, M.-Y.: Tree contractions and evolutionary trees. SIAM J. Comput. 27(6), 1592-1616(1998)

13. Kubicka, E., Kubicki, G., McMorris, F.R.: An algorithm to find agreement subtrees. J. Classific. 12,91-100(1995)

14. Mehlhorn, K.: A best possible bound for the weighted path length of binary search trees. SIAM J. Comput. 6(2), 235-239 (1977)

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