Format

Send to

Choose Destination
J Comput Biol. 2018 Jul;25(7):740-754. doi: 10.1089/cmb.2017.0256. Epub 2018 Feb 16.

Determining the Consistency of Resolved Triplets and Fan Triplets.

Author information

1
1 Department of Computing, The Hong Kong Polytechnic University , Hung Hom, Kowloon, Hong Kong .
2
2 Department of Computer Science, Lund University , Lund, Sweden .
3
3 School of Computing, NUS Graduate School for Integrative Sciences and Engineering, National University of Singapore , Singapore .
4
4 Genome Institute of Singapore , Genome, Singapore, Singapore .

Abstract

The [Formula: see text] Consistency problem takes as input two sets [Formula: see text] and [Formula: see text] of resolved triplets and two sets [Formula: see text] and [Formula: see text] of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in [Formula: see text] and no elements in [Formula: see text] 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 [Formula: see text] whose running time is linear in the size of the input and therefore optimal.

KEYWORDS:

computational complexity; phylogenetic tree; rooted triplets consistency; tree algorithm

PMID:
29451395
DOI:
10.1089/cmb.2017.0256

Supplemental Content

Full text links

Icon for Atypon
Loading ...
Support Center