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

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