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
Fingerprint
Dive into the research topics of 'Determining the consistency of resolved triplets and fan triplets'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver