4551
правка
Супердерево максимального соответствия: различия между версиями
Перейти к навигации
Перейти к поиску
Супердерево максимального соответствия (посмотреть исходный код)
Версия от 22:52, 19 октября 2015
, 19 октября 2015→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Супердерево максимального соответствия, рис. 1 Пусть T – дерево с…») |
Irina (обсуждение | вклад) |
||
| Строка 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 – дерево, показанное справа | ||
Задача нахождения супердерева максимального соответствия (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. | ||
== Основные результаты == | == Основные результаты == | ||