Embedding phylogenetic trees in networks of low treewidth
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914676243169280 |
|---|---|
| author | van Iersel, Leo Jones, Mark Weller, Mathias |
| author_facet | van Iersel, Leo Jones, Mark Weller, Mathias |
| contents | Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods.We present the first algorithm for (rooted) \textsc{Tree Containment} using the treewidth $t$ of the input network $N$ as parameter, showing that the problem can be solved in $2^{O(t^2)}\cdot|N|$ time and space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_00574 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Embedding phylogenetic trees in networks of low treewidth van Iersel, Leo Jones, Mark Weller, Mathias Populations and Evolution Discrete Mathematics Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods.We present the first algorithm for (rooted) \textsc{Tree Containment} using the treewidth $t$ of the input network $N$ as parameter, showing that the problem can be solved in $2^{O(t^2)}\cdot|N|$ time and space. |
| title | Embedding phylogenetic trees in networks of low treewidth |
| topic | Populations and Evolution Discrete Mathematics |
| url | https://arxiv.org/abs/2207.00574 |