Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/67330
Title: Determining the consistency of resolved triplets and fan triplets
Authors: Jansson, J 
Lingas, A
Rajaby, R
Sung, W
Keywords: Algorithm
Computational complexity
Phylogenetic tree
Rooted triplets consistency
Issue Date: 2017
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2017, v. 10229, p. 82-98 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
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.
Description: 21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017, Hong Kong, China, 3-7 May 2017
URI: http://hdl.handle.net/10397/67330
ISBN: 9783319569697
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/978-3-319-56970-3_6
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

80
Checked on Jun 26, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.