Minimal phylogenetic supertrees and local consensus trees

Jesper Andreas Jansson, Wing Kin Sung

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

Abstract

The problem of constructing a minimally resolved phylogenetic supertree (i.e., having the smallest possible number of internal nodes) that contains all of the rooted triplets from a consistent set R is known to be NP-hard. In this paper, we prove that constructing a phylogenetic tree consistent with R that contains the minimum number of additional rooted triplets is also NP-hard, and develop exact, exponential-time algorithms for both problems. The new algorithms are applied to construct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaf label set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in all trees in S, where "minimal" means either having the smallest possible number of internal nodes or the smallest possible number of rooted triplets. The second variant generalizes the RV-II tree, introduced by Kannan, Warnow, and Yooseph in 1998.
Original languageEnglish
Title of host publication41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Volume58
ISBN (Electronic)9783959770163
DOIs
Publication statusPublished - 1 Aug 2016
Externally publishedYes
Event41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krakow, Poland
Duration: 22 Aug 201626 Aug 2016

Conference

Conference41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
Country/TerritoryPoland
CityKrakow
Period22/08/1626/08/16

Keywords

  • Bioinformatics
  • Computational complexity
  • Local consensus
  • Minimal supertree
  • Phylogenetic tree
  • Rooted triplet

ASJC Scopus subject areas

  • Software

Cite this