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

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

Три некорневых дерева: дерево T; дерево T’, такое, что T’ = T | {a, c, e}; дерево T’’, такое, что T’’ D T