License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.69
URN: urn:nbn:de:0030-drops-170070
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17007/
van Iersel, Leo ;
Jones, Mark ;
Weller, Mathias
Embedding Phylogenetic Trees in Networks of Low Treewidth
Abstract
Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2^O(t²)⋅|N| time and space.
BibTeX - Entry
@InProceedings{vaniersel_et_al:LIPIcs.ESA.2022.69,
author = {van Iersel, Leo and Jones, Mark and Weller, Mathias},
title = {{Embedding Phylogenetic Trees in Networks of Low Treewidth}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {69:1--69:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17007},
URN = {urn:nbn:de:0030-drops-170070},
doi = {10.4230/LIPIcs.ESA.2022.69},
annote = {Keywords: fixed-parameter tractability, treewidth, phylogenetic tree, phylogenetic network, display graph, tree containment, embedding}
}
|
Keywords: |
|
fixed-parameter tractability, treewidth, phylogenetic tree, phylogenetic network, display graph, tree containment, embedding |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
