Embedding phylogenetic trees in networks of low treewidth
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Bounds on the Treewidth of Level-k Rooted Phylogenetic Networks
Phylogenetic networks are directed acyclic graphs that depict the genomic evolution of related taxa. Reticulation nodes in such networks (nodes with more than one parent) represent reticulate evolutionary events, such as…
Tree DecompositionUnsupervised Learning of Phylogenetic Trees via Split-Weight Embedding
Unsupervised learning has become a staple in classical machine learning, successfully identifying clustering patterns in data across a broad range of domain applications. Surprisingly, despite its accuracy and elegant si…
ClusteringDifferentiable Phylogenetics via Hyperbolic Embeddings with Dodonaphy
Motivation: Navigating the high dimensional space of discrete trees for phylogenetics presents a challenging problem for tree optimisation. To address this, hyperbolic embeddings of trees offer a promising approach to en…
DecoderDeciding the existence of a cherry-picking sequence is hard on two trees
Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earli…
A Fast and Scalable Method for Inferring Phylogenetic Networks from Trees by Aligning Lineage Taxon Strings
The reconstruction of phylogenetic networks is an important but challenging problem in phylogenetics and genome evolution, as the space of phylogenetic networks is vast and cannot be sampled well. One approach to the pro…