Determining the consistency of resolved triplets and fan triplets
(2018) In Journal of Computational Biology 25(7). p.740-754- 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.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/fdca8f46-46f9-4f36-9165-05a3ec839dfb
- author
- Jansson, Jesper LU ; Lingas, Andrzej LU ; Rajaby, Ramesh and Sung, Wing Kin
- organization
- publishing date
- 2018-07-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- computational complexity, phylogenetic tree, rooted triplets consistency, tree algorithm
- in
- Journal of Computational Biology
- volume
- 25
- issue
- 7
- pages
- 15 pages
- publisher
- Mary Ann Liebert, Inc.
- external identifiers
-
- pmid:29451395
- scopus:85050286790
- ISSN
- 1066-5277
- DOI
- 10.1089/cmb.2017.0256
- language
- English
- LU publication?
- yes
- id
- fdca8f46-46f9-4f36-9165-05a3ec839dfb
- date added to LUP
- 2018-09-12 13:58:35
- date last changed
- 2024-06-24 19:07:20
@article{fdca8f46-46f9-4f36-9165-05a3ec839dfb, abstract = {{<p>The R<sup>+-</sup>F<sup>+-</sup>Consistency problem takes as input two sets R<sup>+</sup> and R<sup>-</sup> of resolved triplets and two sets F<sup>+</sup> and F<sup>-</sup> of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R<sup>+</sup> ⊂ F<sup>+</sup> and no elements in R<sup>-</sup> ⊂ F<sup>-</sup> 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<sup>-</sup>=θ whose running time is linear in the size of the input and therefore optimal.</p>}}, author = {{Jansson, Jesper and Lingas, Andrzej and Rajaby, Ramesh and Sung, Wing Kin}}, issn = {{1066-5277}}, keywords = {{computational complexity; phylogenetic tree; rooted triplets consistency; tree algorithm}}, language = {{eng}}, month = {{07}}, number = {{7}}, pages = {{740--754}}, publisher = {{Mary Ann Liebert, Inc.}}, series = {{Journal of Computational Biology}}, title = {{Determining the consistency of resolved triplets and fan triplets}}, url = {{http://dx.doi.org/10.1089/cmb.2017.0256}}, doi = {{10.1089/cmb.2017.0256}}, volume = {{25}}, year = {{2018}}, }