4551
правка
Построение тонкослойной филогенетической сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Построение тонкослойной филогенетической сети (посмотреть исходный код)
Версия от 19:44, 6 сентября 2017
, 6 сентября 2017нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Филогенетическое дерево – это бинарное корневое неупорядоченное …») |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
Филогенетическое дерево – это бинарное корневое неупорядоченное дерево с уникальными метками листьев. Филогенетическая сеть представляет собой обобщение филогенетического дерева, формально определямое как корневой связный ориентированный ациклический граф, в котором: (1) полустепень выхода каждой вершины не превышает 2; (2) полустепень захода каждой вершины равна 1 или 2, кроме корневой вершины, у которой она равна 0; (3) ни одна вершина не имеет полустепени захода и выхода, одновременно равные 1; (4) все вершины с полустепенью выхода 0 помечены элементами конечного множества L таким образом, что никаким двум вершинам не присваивается одинаковая метка. Вершины с полустепенью выхода 0 называются листьями и идентифицируются по соответствующим им элементам L. Для любой филогенетической сети N обозначим за U(N) неориентированный граф, полученный из N в результате замены каждого ориентированного ребра неориентированным. N называется тонкослойной филогенетической сетью (или просто тонкослойной сетью), если все циклы в U(N) являются вершинно-непересекающимися. Тонкослойные сети в разных источниках также называются топологиями с независимыми событиями рекомбинации [17], галловыми деревьями [3], gt-сетями [13] и филогенетическими сетями первого уровня [2, 7]. | ''Филогенетическое дерево'' – это бинарное корневое неупорядоченное дерево с уникальными метками листьев. ''Филогенетическая сеть'' представляет собой обобщение филогенетического дерева, формально определямое как корневой связный ориентированный ациклический граф, в котором: (1) полустепень выхода каждой вершины не превышает 2; (2) полустепень захода каждой вершины равна 1 или 2, кроме корневой вершины, у которой она равна 0; (3) ни одна вершина не имеет полустепени захода и выхода, одновременно равные 1; (4) все вершины с полустепенью выхода 0 помечены элементами конечного множества L таким образом, что никаким двум вершинам не присваивается одинаковая метка. Вершины с полустепенью выхода 0 называются ''листьями'' и идентифицируются по соответствующим им элементам L. Для любой филогенетической сети N обозначим за <math>\mathcal{U} (N) \;</math> неориентированный граф, полученный из N в результате замены каждого ориентированного ребра неориентированным. N называется ''тонкослойной филогенетической сетью'' (или просто ''тонкослойной сетью''), если все циклы в <math>\mathcal{U} (N) \;</math> являются вершинно-непересекающимися. Тонкослойные сети в разных источниках также называются ''топологиями с независимыми событиями рекомбинации'' [17], <math>галловыми деревьями</math> [3], <math>gt-сетями</math> [13] и ''филогенетическими сетями первого уровня'' [2, 7]. | ||