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)

148
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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