Advanced

Determining the consistency of resolved triplets and fan triplets

Jansson, Jesper LU ; Lingas, Andrzej LU ; Rajaby, Ramesh and Sung, Wing Kin (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:
author
organization
publishing date
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
  • 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
2019-01-06 14:04:34
@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},
  keyword      = {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},
  volume       = {25},
  year         = {2018},
}