Embedding phylogenetic trees in networks of low treewidthArticle
Authors: Leo van Iersel ; Mark Jones ; Mathias Weller
NULL##NULL##NULL
Leo van Iersel;Mark Jones;Mathias Weller
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.