Display sets of normal and tree-child networks

Janosch Döcker¹ ; Simone Linz² ; Charles Semple³

¹University of Tübingen
²University of Auckland
³University of Canterbury

The electronic journal of combinatorics, Tome 28 (2021) no. 1

Résumé

Phylogenetic networks are leaf-labelled directed acyclic graphs that are used in computational biology to analyse and represent the evolutionary relationships of a set of species or viruses. In contrast to phylogenetic trees, phylogenetic networks have vertices of in-degree at least two that represent reticulation events such as hybridisation, lateral gene transfer, or reassortment. By systematically deleting various combinations of arcs in a phylogenetic network $\mathcal N$, one derives a set of phylogenetic trees that are embedded in $\mathcal N$. We recently showed that the problem of deciding if two binary phylogenetic networks embed the same set of phylogenetic trees is computationally hard, in particular, we showed it to be $\Pi^P_2$-complete. In this paper, we establish a polynomial-time algorithm for this decision problem if the initial two networks consist of a normal network and a tree-child network; two well-studied topologically restricted subclasses of phylogenetic networks, with normal networks being more structurally constrained than tree-child networks. The running time of the algorithm is quadratic in the size of the leaf sets.

Détail

DOI : 10.37236/9128

Classification : 05C82, 05C20, 05C85, 92D15, 92C42
Mots-clés : phylogenetic networks, leaf-labelled directed acyclic graphs