Embedding Phylogenetic Trees in Networks of Low Treewidth
L.J.J. van Iersel (TU Delft - Discrete Mathematics and Optimization)
Mark Jones (TU Delft - Discrete Mathematics and Optimization)
Mathias Weller (Centre national de la recherche scientifique (CNRS))
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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 2O(t2) |N| time and space.
help_outline