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

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

Задача 1. Дерево максимальной совместимости (MCT)

Требуется: найти дерево, совместимое с <math>\mathcal{T} \;</math>, с наибольшим числом листьев. Такое дерево обозначается MCT(T), его пример приведен на рис. 2.

Заметим, что <math>\forall \mathcal{T}, |MCT(mathcal{T})| \ge |MAST(mathcal{T})| \;</math>, и MCT эквивалентно MAST в случае, если входные деревья являются бинарными. Также стоит отметить, что задачи MCT и MAST имеют несколько оптимальных решений.

Точные алгоритмы

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

Теорема 2 ([5]). Пусть дан набор из k некорневых деревьев, степени которых не превышают d + 1, с множеством листьев мощности n. Тогда задача MCT может быть решена за время O(22kd nk+1).

Терм 3pkn возникает из-за использования алгоритма, который вначале за время O(kn) локализует множество S из трех листьев, на котором входные деревья конфликтуют, а затем рекурсивным образом вычисляет деревья максимальной совместимости T1, T2 и T3 для каждого из трех наборов T1, T2 и T3, соответственно, полученных посредством удаления принадлежащего S листа из входных деревьев, и затем возвращает Ti, такое, что \T\ максимально (для i 2 [1; 3]). Терм 2:27p + kn3 появляется из-за использования алгоритма, выполняющего редукцию MCT до 3-HITTING SET. Гийемо и Николя получили отрицательный результат при рассмотрении возможности разрешимости MCT с фиксированными параметрами для входных деревьев степени не выше D.

2. MCT не может быть решена за время O(No(2D/2)), если только не выполняется SNP С SE, где N обозначает длину входных элементов, т.е. N = O(kn).

Теорема 5 ([6]). Пусть дан набор T из k корневых деревьев с множеством листьев L мощности n. Тогда существует алгоритм 3-аппроксимации задачи MCT с временем исполнения O(k2n2).

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

В будущем имеет смысл изучение варианта алгоритма MCT, в котором некоторые листья обязательно должны быть представлены в выходном дереве. Эта проблема появляется тогда, когда биологи хотят, чтобы определенные виды, занимающие важное место в их исследовании, обязательно содержались в выходном дереве. Для задачи MAST на двух деревьях этот вариант с ограничениями показал такую же сложность, как и стандартный вариант [ ]. Однако для MCT подобное ограничение может быть связано с решением нескольких проблем оптимизации. Еще одна необходимая работа – это серия экспериментов по измерению диапазона параметров, для которых окажутся полезными алгоритмы точного или приближенного решения задачи MCT.

 

* ''[[Поддерево максимального соответствия (для двух бинарных деревьев)]]