Abstract
A rearrangement operation makes a small graph-theoretical change to a
phylogenetic network to transform it into another one. For unrooted
phylogenetic trees and networks, popular rearrangement operations are tree
bisection and reconnection (TBR) and prune and regraft (PR) (called subtree
prune and regraft (SPR) on trees). Each of these operations induces a metric on
the sets of phylogenetic trees and networks. The TBR-distance between two
unrooted phylogenetic trees $T$ and $T'$ can be characterised by a maximum
agreement forest, that is, a forest with a minimum number of components that
covers both $T$ and $T'$ in a certain way. This characterisation has
facilitated the development of fixed-parameter tractable algorithms and
approximation algorithms. Here, we introduce maximum agreement graphs as a
generalisations of maximum agreement forests for phylogenetic networks. While
the agreement distance -- the metric induced by maximum agreement graphs --
does not characterise the TBR-distance of two networks, we show that it still
provides constant-factor bounds on the TBR-distance. We find similar results
for PR in terms of maximum endpoint agreement graphs.
Users
Please
log in to take part in the discussion (add own reviews or comments).