A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees

Andreas Sand, Gerth Stølting Brodal, Rolf Fagerberg, Christian N. S. Pedersen, Thomas Mailund

Research output: Contribution to journalConference articleResearchpeer-review

87 Downloads (Pure)

Abstract

The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.
Original languageEnglish
Article numberS18
JournalB M C Bioinformatics
Volume14
Issue numberSuppl. 2
Number of pages9
ISSN1471-2105
DOIs
Publication statusPublished - 2013
EventEleventh Asia Pacific Bioinformatics Conference - Vancouver, Canada
Duration: 21. Jan 201324. Jan 2013

Conference

ConferenceEleventh Asia Pacific Bioinformatics Conference
CountryCanada
CityVancouver
Period21/01/201324/01/2013

Fingerprint

Binary trees
Binary Tree
Computing
Rooted Trees
Leaves
Distance Measure
Time Complexity
Counting
Topology
Subset
Experiment
Experiments

Keywords

  • Algorithms
  • Computational Biology/methods
  • Computer Simulation
  • Phylogeny
  • Software

Cite this

Sand, Andreas ; Brodal, Gerth Stølting ; Fagerberg, Rolf ; Pedersen, Christian N. S. ; Mailund, Thomas. / A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees. In: B M C Bioinformatics. 2013 ; Vol. 14, No. Suppl. 2.
@inproceedings{352543bbecaf417f9386da1504357060,
title = "A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees",
abstract = "The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.",
keywords = "Algorithms, Computational Biology/methods, Computer Simulation, Phylogeny, Software",
author = "Andreas Sand and Brodal, {Gerth St{\o}lting} and Rolf Fagerberg and Pedersen, {Christian N. S.} and Thomas Mailund",
year = "2013",
doi = "10.1186/1471-2105-14-S2-S18",
language = "English",
volume = "14",
journal = "B M C Bioinformatics",
issn = "1471-2105",
publisher = "BioMed Central",
number = "Suppl. 2",

}

A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees. / Sand, Andreas; Brodal, Gerth Stølting; Fagerberg, Rolf; Pedersen, Christian N. S.; Mailund, Thomas.

In: B M C Bioinformatics, Vol. 14, No. Suppl. 2, S18, 2013.

Research output: Contribution to journalConference articleResearchpeer-review

TY - GEN

T1 - A practical O(n log2 n) time algorithm for computing the triplet distance on binary trees

AU - Sand, Andreas

AU - Brodal, Gerth Stølting

AU - Fagerberg, Rolf

AU - Pedersen, Christian N. S.

AU - Mailund, Thomas

PY - 2013

Y1 - 2013

N2 - The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.

AB - The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all sub-sets of three leaves and counting how often the induced topologies of the tree are equal or different. We present an algorithm that computes the triplet distance between two rooted binary trees in time O (n log2 n). The algorithm is related to an algorithm for computing the quartet distance between two unrooted binary trees in time O (n log n). While the quartet distance algorithm has a very severe overhead in the asymptotic time complexity that makes it impractical compared to O (n2) time algorithms, we show through experiments that the triplet distance algorithm can be implemented to give a competitive wall-time running time.

KW - Algorithms

KW - Computational Biology/methods

KW - Computer Simulation

KW - Phylogeny

KW - Software

U2 - 10.1186/1471-2105-14-S2-S18

DO - 10.1186/1471-2105-14-S2-S18

M3 - Conference article

C2 - 23368759

VL - 14

JO - B M C Bioinformatics

JF - B M C Bioinformatics

SN - 1471-2105

IS - Suppl. 2

M1 - S18

ER -