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 (2017) 21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10229 LNCS. p.82-98
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 paper 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
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Algorithm, Computational complexity, Phylogenetic tree, Rooted triplets consistency
host publication
Research in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings
series title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
volume
10229 LNCS
pages
17 pages
publisher
Springer
conference name
21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017
conference location
Hong Kong, China
conference dates
2017-05-03 - 2017-05-07
external identifiers
  • scopus:85018377352
ISSN
16113349
03029743
ISBN
9783319569697
DOI
10.1007/978-3-319-56970-3_6
language
English
LU publication?
yes
id
051ba956-02f6-492f-ac58-3f8ea988cab0
date added to LUP
2017-05-23 10:15:29
date last changed
2025-01-07 13:58:27
@inproceedings{051ba956-02f6-492f-ac58-3f8ea988cab0,
  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 paper 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}},
  booktitle    = {{Research in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings}},
  isbn         = {{9783319569697}},
  issn         = {{16113349}},
  keywords     = {{Algorithm; Computational complexity; Phylogenetic tree; Rooted triplets consistency}},
  language     = {{eng}},
  pages        = {{82--98}},
  publisher    = {{Springer}},
  series       = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
  title        = {{Determining the consistency of resolved triplets and fan triplets}},
  url          = {{http://dx.doi.org/10.1007/978-3-319-56970-3_6}},
  doi          = {{10.1007/978-3-319-56970-3_6}},
  volume       = {{10229 LNCS}},
  year         = {{2017}},
}