Locating a Tree in a Phylogenetic Network in Quadratic Time
arXiv:1502.03379 · doi:10.1007/978-3-319-16706-0_12
Abstract
A fundamental problem in the study of phylogenetic networks is to determine whether or not a given phylogenetic network contains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic networks. We also show that the number of reticulations in a reticulation visible or nearly stable phylogenetic network is bounded from above by a function linear in the number of taxa.
Accepted to RECOMB 2015
Cited by in corpus (7)
- Locating a Tree in a Reticulation-Visible Network in Cubic Time
- Counting Tree-Child Networks and Their Subclasses
- Bounding the Size of a Network Defined By Visibility Property
- On Tree Based Phylogenetic Networks
- Locating a Phylogenetic Tree in a Reticulation-Visible Network in Quadratic Time
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- Counting and Enumerating Galled Networks