The agreement distance of rooted phylogenetic networks
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 agreeme...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4593/pdf |
| _version_ | 1797270015643222016 |
|---|---|
| author | Jonathan Klawitter |
| author_facet | Jonathan Klawitter |
| author_sort | Jonathan Klawitter |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:33Z |
| format | Article |
| id | doaj.art-8c0b0fd63ba74e3a962db1fbe6d6a0b2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:33Z |
| publishDate | 2019-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-8c0b0fd63ba74e3a962db1fbe6d6a0b22024-03-07T15:39:17ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-05-01Vol. 21 no. 3Graph Theory10.23638/DMTCS-21-3-194593The agreement distance of rooted phylogenetic networksJonathan KlawitterThe 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.https://dmtcs.episciences.org/4593/pdfmathematics - combinatoricscomputer science - discrete mathematicsquantitative biology - populations and evolution05c90, 92d15, 68r10 |
| spellingShingle | Jonathan Klawitter The agreement distance of rooted phylogenetic networks Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics quantitative biology - populations and evolution 05c90, 92d15, 68r10 |
| title | The agreement distance of rooted phylogenetic networks |
| title_full | The agreement distance of rooted phylogenetic networks |
| title_fullStr | The agreement distance of rooted phylogenetic networks |
| title_full_unstemmed | The agreement distance of rooted phylogenetic networks |
| title_short | The agreement distance of rooted phylogenetic networks |
| title_sort | agreement distance of rooted phylogenetic networks |
| topic | mathematics - combinatorics computer science - discrete mathematics quantitative biology - populations and evolution 05c90, 92d15, 68r10 |
| url | https://dmtcs.episciences.org/4593/pdf |
| work_keys_str_mv | AT jonathanklawitter theagreementdistanceofrootedphylogeneticnetworks AT jonathanklawitter agreementdistanceofrootedphylogeneticnetworks |