A practical O(<em>n</em> log<sup>2</sup> <em>n</em>) time algorithm for computing the triplet distance on binary trees - Danish National Research Database-Den Danske Forskningsdatabase

^{1} Department of Computer Science, Science and Technology, Aarhus University^{2} Bioinformatics Research Centre (BiRC), Science and Technology, Aarhus University^{3} Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University^{4} 4 Department of Mathematics and Computer Science, University of Southern Denmark^{5} Department of Computer Science, Science and Technology, Aarhus University^{6} Bioinformatics Research Centre (BiRC), Science and Technology, Aarhus University

DOI:

10.1186/1471-2105-14-S2-S18

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.

Type:

Conference paper

Language:

English

Published in:

B M C Bioinformatics, 2013, Vol 14, Issue Suppl 2

Keywords:

Triplet distance; Binary tree

Main Research Area:

Science/technology

Publication Status:

Published

Review type:

Peer Review

Conference:

The Asia Pacific Bioinformatics ConferenceAsia-Pacific Bioinformatics Conference, 2013