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

''Филогенетическое дерево'' – это бинарное корневое неупорядоченное дерево с уникальными метками листьев. ''Филогенетическая сеть'' представляет собой обобщение филогенетического дерева, формально определямое как корневой связный ориентированный ациклический граф, в котором: (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].

Далее рассматривается задача построения тонкослойной сети N, согласующейся с максимальным количеством корневых триплетов из T для любого (не обязательно плотного) множества T. Поскольку из теоремы 2 следует, что эта задача является NP-полной, были исследованы алгоритмы аппроксимации для ее приближенного решения. Алгоритм называется k-аппроксимируемым, если он всегда возвращает тонкослойную сеть N, такую, что N(T)/|T| > k, где N(T) – количество корневых триплетов в T, согласующихся с N.

Теорема 3. Пусть дано множество корневых триплетов T. Не существует алгоритма аппроксимации, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 0.4883.

Теорема 4. Пусть дано множество корневых триплетов T. Существует алгоритм аппроксимации, результатом работы которого является тонкослойная сеть N, такая, что N(T)/|T| > 5/12. Время работы алгоритма составляет О(\А(Т)\\Т\Ъ).