Minimal phylogenetic supertrees and local consensus trees

Jesper Andreas Jansson, Ramesh Rajaby, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The problem of constructing a minimally resolved phylogenetic supertree (i.e., a rootedtree having the smallest possible number of internal nodes) that contains all of the rooted triplets froma consistent set R is known to be NP-hard. In this article, we prove that constructing a phylogenetictree 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 toconstruct two variants of the local consensus tree; for any set S of phylogenetic trees over some leaflabel set L, this gives a minimal phylogenetic tree over L that contains every rooted triplet present in alltrees in S, where “minimal” means either having the smallest possible number of internal nodes or thesmallest possible number of rooted triplets. (The second variant generalizes the RV-II tree, introducedby Kannan et al. in 1998.) We also measure the running times and memory usage in practice of thenew algorithms for various inputs. Finally, we use our implementations to experimentally investigatethe non-optimality of Aho et al.’s well-known BUILD algorithm from 1981 when applied to the localconsensus tree problems considered here.
Original languageEnglish
Pages (from-to)181-203
JournalAIMS Medical Science
Volume5
Issue number2
DOIs
Publication statusPublished - 2018

Keywords

  • phylogenetic tree
  • rooted triplet
  • local consensus
  • minimal supertree
  • algorithms
  • computational complexity

Cite this