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

Перейти к навигации Перейти к поиску
(Новая страница: «== Постановка задачи == Супердерево максимального соответствия, рис. 1 Пусть T – дерево с…»)
 
Строка 1: Строка 1:
== Постановка задачи ==
== Постановка задачи ==
   
   
Супердерево максимального соответствия, рис. 1


Пусть T – дерево, листья которого уникальным образом снабжены метками из набора таксонов S. Под уникальным образом мы понимаем то обстоятельство, что в T нет двух листьев с одинаковыми метками. Если дано подмножество S0 множества S, то топологическое ограничение T согласно S0 (обозначается TjS0) представляет собой дерево, полученное в результате удаления из T всех вершин, не лежащих ни на одном пути из корня к листу из подмножества S0, вместе с инцидентными им ребрами, и последующего сжатия каждого ребра между вершиной, имеющей только одного потомка, и самим этим потомком (см. рис. 1). Для любого дерева T обозначим множество меток его листьев как A(T).
[[Файл:Max_agr_supertree.jpg]]


Пусть T – дерево с левой стороны. Тогда Tj fa; c; dg – дерево, показанное справа
Пусть T – дерево с левой стороны. Тогда Tj fa; c; dg – дерево, показанное справа


Пусть T – дерево, листья которого уникальным образом снабжены метками из набора таксонов S. Под уникальным образом мы понимаем то обстоятельство, что в T нет двух листьев с одинаковыми метками. Если дано подмножество S0 множества S, то топологическое ограничение T согласно S0 (обозначается TjS0) представляет собой дерево, полученное в результате удаления из T всех вершин, не лежащих ни на одном пути из корня к листу из подмножества S0, вместе с инцидентными им ребрами, и последующего сжатия каждого ребра между вершиной, имеющей только одного потомка, и самим этим потомком (см. рис. 1). Для любого дерева T обозначим множество меток его листьев как A(T).
    
    
Задача нахождения супердерева максимального соответствия (maximum agreement supertree problem, MASP) [8] определяется следующим образом.
Задача нахождения супердерева максимального соответствия (maximum agreement supertree problem, MASP) [8] определяется следующим образом.
Строка 17: Строка 16:


Далее будут использоваться следующие обозначения: n = \{JTieD А(Щ> k=jDj и D = maxrieD{deg(T,)}, где deg(Ti) – степень Ti.
Далее будут использоваться следующие обозначения: n = \{JTieD А(Щ> k=jDj и D = maxrieD{deg(T,)}, где deg(Ti) – степень Ti.


== Основные результаты ==
== Основные результаты ==
4501

правка

Навигация