Geodesic
The agreement distance of unrooted phylogenetic networks
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.23638/DMTCS-22-1-22
Classification : 05C82, 05C90, 05C99, 92C42, 92D15 
@article{DMTCS_2020_22_1_a20,
     author = {Klawitter, Jonathan},
     title = {The agreement distance of unrooted phylogenetic networks},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-22},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-22/}
}
TY  - JOUR
AU  - Klawitter, Jonathan
TI  - The agreement distance of unrooted phylogenetic networks
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-22/
DO  - 10.23638/DMTCS-22-1-22
LA  - en
ID  - DMTCS_2020_22_1_a20
ER  - 
%0 Journal Article
%A Klawitter, Jonathan
%T The agreement distance of unrooted phylogenetic networks
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-22/
%R 10.23638/DMTCS-22-1-22
%G en
%F DMTCS_2020_22_1_a20
Klawitter, Jonathan. The agreement distance of unrooted phylogenetic networks. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi : 10.23638/DMTCS-22-1-22. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-22/

Cité par Sources :