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

1 Citation (Scopus)

Abstract

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
Pages109-125
Number of pages17
ISBN (Print)9783319212326
DOIs
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)
Volume9199
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Conference on Algorithms for Computational Biology, AlCoB 2015
Country/TerritoryMexico
CityMexico City
Period4/08/155/08/15

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this