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

Поддерево максимальной уточненности (MRST)

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

Деревья, которые здесь рассматриваются, представляют собой эволюционные (филогенетические) деревья. Такое дерево 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 имеют несколько оптимальных решений.

Набор из двух несовместимых входных деревьев 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]).

Терм 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).

Идея локализации и последующего успешного удаления всех конфликтов между входными деревьями также привела к созданию алгоритмов аппроксимации для дополнения задачи 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.

 

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