Klawitter, Jonathan - The agreement distance of rooted phylogenetic networks

dmtcs:4593 - Discrete Mathematics & Theoretical Computer Science, May 23, 2019, Vol. 21 no. 3
The agreement distance of rooted phylogenetic networks

Authors: Klawitter, Jonathan

The minimal number of rooted subtree prune and regraft (rSPR) operations needed to transform one phylogenetic tree into another one induces a metric on phylogenetic trees - the rSPR-distance. The rSPR-distance between two phylogenetic trees $T$ and $T'$ can be characterised by a maximum agreement forest; a forest with a minimum number of components that covers both $T$ and $T'$. The rSPR operation has recently been generalised to phylogenetic networks with, among others, the subnetwork prune and regraft (SNPR) operation. Here, we introduce maximum agreement graphs as an explicit representations of differences of two phylogenetic networks, thus generalising maximum agreement forests. We show that maximum agreement graphs induce a metric on phylogenetic networks - the agreement distance. While this metric does not characterise the distances induced by SNPR and other generalisations of rSPR, we prove that it still bounds these distances with constant factors.


Source : oai:arXiv.org:1806.05800
Volume: Vol. 21 no. 3
Section: Graph Theory
Published on: May 23, 2019
Submitted on: June 18, 2018
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Quantitative Biology - Populations and Evolution,05C90, 92D15, 68R10


Share