Determining the consistency of resolved triplets and fan triplets

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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.

Details

Authors
Organisations
External organisations
  • Kyoto University
  • Hong Kong Polytechnic University
  • National University of Singapore
  • Genome Institute of Singapore
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computational Mathematics

Keywords

  • Algorithm, Computational complexity, Phylogenetic tree, Rooted triplets consistency
Original languageEnglish
Title of host publicationResearch in Computational Molecular Biology - 21st Annual International Conference, RECOMB 2017, Proceedings
PublisherSpringer Verlag
Pages82-98
Number of pages17
Volume10229 LNCS
ISBN (Print)9783319569697
Publication statusPublished - 2017
Publication categoryResearch
Peer-reviewedYes
Event21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017 - Hong Kong, China
Duration: 2017 May 32017 May 7

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10229 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference21st Annual International Conference on Research in Computational Molecular Biology, RECOMB 2017
CountryChina
CityHong Kong
Period2017/05/032017/05/07