Abstract
The R+-F+-Consistency problem takes as input two sets R+ and R- of resolved triplets and two sets F+ and F- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R+ ⊂ F+ and no elements in R- ⊂ F- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R-=θ whose running time is linear in the size of the input and therefore optimal.
Original language | English |
---|---|
Pages (from-to) | 740-754 |
Number of pages | 15 |
Journal | Journal of Computational Biology |
Volume | 25 |
Issue number | 7 |
DOIs | |
Publication status | Published - Jul 2018 |
Keywords
- computational complexity
- phylogenetic tree
- rooted triplets consistency
- tree algorithm
ASJC Scopus subject areas
- Modelling and Simulation
- Molecular Biology
- Genetics
- Computational Mathematics
- Computational Theory and Mathematics