Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; and
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
  • 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-01-15 01:22:25
@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}},
}