A More Practical Algorithm for the Rooted Triplet Distance

Jesper Andreas Jansson, Ramesh Rajaby

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

2017. The rooted triplet distance is a measure of the dissimilarity of two phylogenetic trees with identical leaf label sets. An algorithm by Brodal et al. that computes it in O(n log n) time and O(n log n) space, where n is the number of leaf labels, has recently been implemented in the software package tqDist. In this article, we show that replacing the hierarchical decomposition tree used in Brodal et al.'s algorithm by a centroid paths-based data structure yields an O(n log3n)-time and O(n log n)-space algorithm that, although slower in theory, is faster in practice as well as less memory consuming. Simulations for values of n up to 4,000,000 support our claims experimentally.
Original languageEnglish
Pages (from-to)106-126
Number of pages21
JournalJournal of Computational Biology
Volume24
Issue number2
DOIs
Publication statusPublished - 1 Feb 2017
Externally publishedYes

Keywords

  • centroid path decomposition tree
  • implementation
  • phylogenetic tree comparison
  • rooted triplet distance

ASJC Scopus subject areas

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

Cite this