Determining the consistency of resolved triplets and fan triplets

Jesper Andreas Jansson, Andrzej Lingas, Ramesh Rajaby, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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 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 R-=θ whose running time is linear in the size of the input and therefore optimal.

Original languageEnglish
Pages (from-to)740-754
Number of pages15
JournalJournal of Computational Biology
Volume25
Issue number7
DOIs
Publication statusPublished - Jul 2018

Keywords

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

ASJC Scopus subject areas

  • Modelling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this