On the subnet prune and regraft distance

Jonathan Klawitter¹ ; Simone Linz¹

¹University of Auckland

The electronic journal of combinatorics, Tome 26 (2019) no. 2

Résumé

Phylogenetic networks are rooted directed acyclic graphs that represent evolutionary relationships between species whose past includes reticulation events such as hybridisation and horizontal gene transfer. To search the space of phylogenetic networks, the popular tree rearrangement operation rooted subtree prune and regraft (rSPR) was recently generalised to phylogenetic networks. This new operation – called subnet prune and regraft (SNPR) – induces a metric on the space of all phylogenetic networks as well as on several widely-used network classes. In this paper, we investigate several problems that arise in the context of computing the SNPR-distance. For a phylogenetic tree $T$ and a phylogenetic network $N$, we show how this distance can be computed by considering the set of trees that are embedded in $N$ and then use this result to characterise the SNPR-distance between $T$ and $N$ in terms of agreement forests. Furthermore, we analyse properties of shortest SNPR-sequences between two phylogenetic networks $N$ and $N'$, and answer the question whether or not any of the classes of tree-child, reticulation-visible, or tree-based networks isometrically embeds into the class of all phylogenetic networks under SNPR.

Détail

DOI : 10.37236/7860

Classification : 05C90, 05C82, 92D15, 68R10
Mots-clés : phylogenetic network, search operation, SNPR-distance, reticulation, fixed-parameter tractable problem