### Abstract

Original language | English |
---|---|

Article number | S18 |

Journal | B M C Bioinformatics |

Volume | 14 |

Issue number | Suppl. 2 |

Number of pages | 9 |

ISSN | 1471-2105 |

DOIs | |

Publication status | Published - 2013 |

Event | Eleventh Asia Pacific Bioinformatics Conference - Vancouver, Canada Duration: 21. Jan 2013 → 24. Jan 2013 |

### Conference

Conference | Eleventh Asia Pacific Bioinformatics Conference |
---|---|

Country | Canada |

City | Vancouver |

Period | 21/01/2013 → 24/01/2013 |

### Fingerprint

### Keywords

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

### Cite this

*O*(

*n*log

^{2}

*n*) time algorithm for computing the triplet distance on binary trees.

*B M C Bioinformatics*,

*14*(Suppl. 2), [S18]. https://doi.org/10.1186/1471-2105-14-S2-S18

}

*O*(

*n*log

^{2}

*n*) time algorithm for computing the triplet distance on binary trees',

*B M C Bioinformatics*, vol. 14, no. Suppl. 2, S18. https://doi.org/10.1186/1471-2105-14-S2-S18

**A practical O(n log^{2} 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.

Research output: Contribution to journal › Conference article › Research › peer-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 -

*O*(

*n*log

^{2}

*n*) time algorithm for computing the triplet distance on binary trees. B M C Bioinformatics. 2013;14(Suppl. 2). S18. https://doi.org/10.1186/1471-2105-14-S2-S18