Activities per year
Abstract
The triplet distance is a distance measure that compares two rooted trees on the same set of leaves by enumerating all subsets 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 walltime running time.
Original language  English 

Journal  B M C Bioinformatics 
Volume  14 
Issue  Suppl 2 
Pages (fromto)  S18 
Number of pages  9 
ISSN  14712105 
DOIs  
Publication status  Published  2013 
Event  The Asia Pacific Bioinformatics Conference  Vancouver, Canada Duration: 21 Jan 2013 → 24 Jan 2013 Conference number: 11 
Conference
Conference  The Asia Pacific Bioinformatics Conference 

Number  11 
Country/Territory  Canada 
City  Vancouver 
Period  21/01/2013 → 24/01/2013 
Fingerprint
Dive into the research topics of 'A practical O(n log^{2} n) time algorithm for computing the triplet distance on binary trees'. Together they form a unique fingerprint.Activities
 1 Participation in or organisation af a conference

The Asia Pacific Bioinformatics Conference
Sand, A. (Participant)
20 Jan 2013 → 23 Jan 2013Activity: Participating in or organising an event types › Participation in or organisation af a conference