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

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

Деревья, которые здесь рассматриваются, представляют собой эволюционные (филогенетические) деревья. Такое дерево T имеет множество листьев L(T), находящихся во взаимно-однозначном соответствии с множеством меток, и является либо корневым (в этом случае все внутренние вершины имеют не менее двух потомков), либо некорневым (в этом случае внутренние вершины имеют степень не ниже трех). Размером |T| дерева T является число его листьев. Пусть дано множество меток L и дерево T; ограничение T согласно L, обозначаемое T|L, представляет собой дерево, полученное следующим образом: взять наименьший порожденный подграф T, соединяющий листья с метками из L \ L(T), а затем удалить две некорневых вершины любой степени, чтобы дерево стало гомеоморфно неприводимым. Два дерева T и T0 являются изоморфными (T = T0) в том и только том случае, если существует изоморфизм графов T 7! T0, сохраняющий метки листьев (и корень, если оба дерева были корневыми). Дерево T уточняет дерево T0 (T D T0), если T может быть преобразовано в T путем коллапсирования некоторых его внутренних ребер (под коллапсированием ребра понимается его удаление и слияние его конечных точек). На рис. 1 приведены примеры таких отношений между деревьями.

Отметим, что дерево T, должным образом уточняющее дерево T0, согласуется со всей эволюционной историей T0, но при этом содержит дополнительную информацию, отсутствующую в T0: по меньшей мере одна вершина высокой степени из T заменяется в T несколькими вершинами меньших степеней, следовательно, T содержит больше событий видообразования, чем T0. Пусть имеется набор T = {T1, T2, ... : : Tk} входных деревьев с идентичными множествами листьев L. Мы говорим, что дерево T с листьями из L совместимо с T в том и только том случае, если 8Ti 2 T, T D TijL(T). Если существует дерево T, совместимое с T, такое, что L(T) = L, то набор T называется совместимым. Для решения вопроса, является ли набор деревьев совместимым, давно известны линейные алгоритмы (см., например, в [8]). Задача нахождения дерева максимальной совместимости представляет собой вариант естественной оптимизации данной задачи, позволяющий обрабатывать наборы несовместимых деревьев.

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

Дано: набор деревьев T с идентичными множествами листьев. Требуется: найти дерево, совместимое с T, с наибольшим числом листьев. Такое дерево обозначается MCT(T),

его пример приведен на рис. 2. Заметим, что 8T ; jMCT(T)j > jMAST(T)j, и MCT эквивалентно MAST в случае, если входные деревья являются бинарными. Также стоит отметить, что задачи MCT и MAST имеют несколько оптимальных решений.

[[Файл:MCT1.jpg]]

Набор из двух несовместимых входных деревьев fT1;T2g и их дерево максимальной совместимости T = MCT(T1 ; T2). Если удалить лист d, входные деревья станут совместимыми, поскольку ЦТ) = fa;b;c;eg. Здесь дерево T строго уточняет T2, ограниченное согласно L(T), что выражается тем обстоятельством, что потомки вершины дерева T2 (изображенной серым цветом) распределены между несколькими связанными вершинами T (также серого цвета). Отметим также, что jMCT(T1 ; T2)j > jMAST(T1 ; T2)j

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

Было показано, что задача 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).

Пусть T – набор деревьев с листьями из множества L. В работе [2] рассматривалась следующая задача, названная MCTp: пусть даны T и p 2 [0; n]; верно ли jMCT(T)j > n-p?

Теорема 3 ([2]).

1. Задача MCTp для корневых деревьев может быть решена за время O(minf3pkn; 2:27p + kn3g).

2. Задача MCTp для некорневых деревьев может быть решена за время O({p + 1) x minf3p kn; 2:27p + kn3}).

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

Идея локализации и последующего успешного удаления всех конфликтов между входными деревьями также привела к созданию алгоритмов аппроксимации для дополнения задачи MCT, обозначаемого CMCT. Пусть L – множество листьев каждого дерева входного набора T. Целью задачи CMCT является выбор наименьшего числа листьев SCI, таких, что набор fTij(L - S) : Ti 2 Tg является совместимым.

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

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

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

 

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