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

DOI : 10.23638/DMTCS-21-3-19

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