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

Представляет собой задачу сопоставления с образцом для деревьев с помеченными листьями. Каждое дерево на входе рассматривается как образец ветвления, порождающий конкретную группу листьев. Пусть имеется набор деревьев с идентичными множествами листьев; необходимо найти максимальное подмножество листьев по образцу ветвления, на котором входные деревья совпадают. Дерево максимальной совместимости – это дерево, содержащее такой набор листьев и включающее образцы ветвления входных деревьев для этих листьев. Задача нахождения дерева максимальной совместимости (maximum compatible problem, MCP) заключается в нахождении такого дерева или, что эквивалентно, его набора листьев. Больше всего решение этой задачи необходимо в филогенетике – для измерения сходства между эволюционными деревьями или для формирования консенсуса для множества деревьев. Впервые задача была поставлена в [9] и [10] под названием MRST (поддерево максимальной уточненности). Предыдущие работы рассматривали хорошо известную задачу нахождения [[поддерево максимального соответствия|поддерева максимального соответствия]] (maximum agreement subtree, MAST). Решением MAST будет нахождение наибольшего подмножества листьев, на котором все входные деревья '''точно''' совпадают. Более точно, алгоритм MAST ищет дерево, у которого схема ветвления изоморфна схеме поддерева каждого из входных деревьев, тогда как MCT ищет дерево, содержащее схему ветвления (т.е. группы) поддерева каждого входного дерева. В результате дерево, полученное по алгоритму MCT, оказывается более информативным, поскольку оно может содержать схему ветвления, представленную только в одном из деревьев, если она не противоречит остальным деревьям. Если все входные деревья являются бинарными, эти задачи эквивалентны. Ганапати и Уорноу [5] первыми предложили алгоритм для решения задачи MCT в общем виде. Алгоритм работает на базе простого динамического подхода, близкого к используемому при решении MAST [12], и имеет время исполнения, экспоненциальное относительно количества входных деревьев и максимальной степени вершин входных деревьев. Позднее в [2] был предложен алгоритм с фиксированными параметрами, использующий только один параметр. Также были получены приближенные результаты [1, 6] – недорогие алгоритмы с полиномиальным временем исполнения, аппроксимирующие дополнение задачи MCT с константным порогом.

Было показано, что задача MCT является NP-полной для 6 деревьев ([9]) и для 2 деревьев [10]. NP-полнота появляется, когда по меньшей мере одно из входных деревьев имеет неограниченную степень. Для случая двух деревьев с ограниченной степенью Хайн и коллеги упоминают алгоритм с полиномиальным временем исполнения, основанный на выравнивании деревьев [10]. Ганапати и Уорноу [5] предложили экспоненциальный алгоритм для решения задачи MCT в общем виде. Они показали, как для двух деревьев <math>T_1, T_2 \;</math> вычислить бинарное дерево MCT для любой пары поддеревьев <math>(S_1 \in T_1, S_2 \in T_2) \;</math> при помощи динамических алгоритмов. Поддеревья, корни которых имеют высокую степень, обрабатываются путем рассмотрения каждого возможного разбиения потомков корня на два множества. Из-за этого в оценке сложности появляется экспоненциальный терм относительно d – максимальной степени вершин входных деревьев. Если имеются k входных деревьев, то рассматриваются кортежи из k поддеревьев и производится подобное же разбиение потомков корневых вершин на два множества для k поддеревьев. Следовательно, сложность по-прежнему является экспоненциальной относительно k.

'''Теорема 1 ([5]). Пусть L – множество, содержащее n листьев. Задача MCT для набора из k корневых деревьев с листьями из L, в котором каждое дерево имеет степень не выше d + 1, может быть решена за время <math>O(2^{2kd} n^k) \;</math>.'''

'''Теорема 2 ([5]). Пусть дан набор из k некорневых деревьев, степени которых не превышают d + 1, с множеством листьев мощности n. Тогда задача MCT может быть решена за время <math>O(2^{2kd} n^{k+1}) \;</math>.'''

'''1. Задача <math>MCT_p \;</math> для корневых деревьев может быть решена за время <math>O(min \{ 3^p kn, 2.27^p + kn^3 \}) \;</math>.'''

'''2. Задача <math>MCT_p \;</math> для некорневых деревьев может быть решена за время <math>O \big( (p + 1) \times min \{ 3^p kn, 2.27^p + kn^3 \} \big) \;</math>.'''

'''1. MCT является W[1]-полной относительно D.'''

'''2. MCT не может быть решена за время <math>O(N^{o(2^{D/2})}) \;</math>, если только не выполняется <math>SNP \subseteq SE \;</math>, где N обозначает длину входных элементов, т.е. N = O(kn).'''

'''Алгоритмы аппроксимации'''

Идея локализации и последующего успешного удаления всех конфликтов между входными деревьями также привела к созданию алгоритмов аппроксимации для ''дополнения'' задачи MCT, обозначаемого CMCT. Пусть L – множество листьев каждого дерева входного набора T. Целью задачи CMCT является выбор наименьшего числа листьев <math>S \subseteq I \;</math>, таких, что набор <math>\{ T_i | (L - S): T_i \in \mathcal{T} \} \;</math> является совместимым.

'''Теорема 6 ([1]). Существует алгоритм 3-аппроксимации с временем исполнения <math>O(kn + n^2) \;</math> для решения задачи CMCT на наборе k корневых деревьев с n листьев.'''