The complexity of inferring a minimally resolved phylogenetic supertree

Jesper Andreas Jansson, Richard S. Lemence, Andrzej Lingas

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

A recursive algorithm by Aho, Sagiv, Szymanski, and Ullman [1] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [4], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MinRS). We also present an exponential-time algorithm for solving MinRS exactly which is based on tree separators. It runs in 2O(n logk) time when every node is required to have at most k children which are internal nodes and where n is the cardinality of the leaf label set of the input trees.
Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics - 10th International Workshop, WABI 2010, Proceedings
Pages262-273
Number of pages12
DOIs
Publication statusPublished - 10 Nov 2010
Externally publishedYes
Event10th International Workshop on Algorithms in Bioinformatics, WABI 2010 - Liverpool, United Kingdom
Duration: 6 Sep 20108 Sep 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6293 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Workshop on Algorithms in Bioinformatics, WABI 2010
Country/TerritoryUnited Kingdom
CityLiverpool
Period6/09/108/09/10

Keywords

  • minimally resolved supertree
  • NP-hardness
  • Phylogenetic tree
  • rooted triplet
  • tree separator

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this