A more practical algorithm for the rooted triplet distance

Jesper Andreas Jansson, Ramesh Rajaby

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

2 Citations (Scopus)


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. [2] that computes it in O(n log n) time, where n is the number of leaf labels, has recently been implemented in the software package tqDist [14]. In this paper, 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 log3 n)-time algorithm that, although slower in theory, is easier to implement and apparently faster in practice. Simulations for values of n up to 1, 000, 000 support our claims experimentally.
Original languageEnglish
Title of host publicationAlgorithms for Computational Biology - 2nd International Conference, AlCoB 2015, Proceedings
PublisherSpringer Verlag
Number of pages17
ISBN (Print)9783319212326
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event2nd International Conference on Algorithms for Computational Biology, AlCoB 2015 - Mexico City, Mexico
Duration: 4 Aug 20155 Aug 2015

Publication series

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


Conference2nd International Conference on Algorithms for Computational Biology, AlCoB 2015
CityMexico City


  • Bioinformatics
  • Centroid path decomposition tree
  • Phylogenetic tree comparison
  • Rooted triplet distance

ASJC Scopus subject areas

  • General Computer Science
  • Theoretical Computer Science


Dive into the research topics of 'A more practical algorithm for the rooted triplet distance'. Together they form a unique fingerprint.

Cite this