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

Эта задача представляет собой задачу сопоставления с образцом для деревьев с помеченными листьями. Каждое дерево на входе рассматривается как образец ветвления, порождающий конкретную группу листьев. Пусть имеется набор деревьев с идентичными множествами листьев; необходимо найти максимальное подмножество листьев по образцу ветвления, на котором входные деревья совпадают. Дерево максимальной совместимости – это дерево, содержащее такой набор листьев и включающее образцы ветвления входных деревьев для этих листьев. Задача нахождения дерева максимальной совместимости (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.

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

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

'''Теорема 5 ([6]).''' Пусть дан набор <math>\mathcal{T} \;</math> из k корневых деревьев с множеством листьев L мощности n. Тогда существует алгоритм 3-аппроксимации задачи MCT с временем исполнения <math>O(k^2 n^2) \;</math>.

Время исполнения этого алгоритма позднее было улучшено:

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