Jonathan Klawitter - The agreement distance of rooted phylogenetic networks

dmtcs:4593 - Discrete Mathematics & Theoretical Computer Science, May 23, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-19
The agreement distance of rooted phylogenetic networksArticle

Authors: Jonathan Klawitter

    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.


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

    Consultation statistics

    This page has been seen 583 times.
    This article's PDF has been downloaded 241 times.