Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees

DOI10.4230/LIPICS.ESA.2017.21MaRDI QIDQ5111707zbMATH OpenOpenAlexFDO

Authors Gerth Stølting Brodal, Konstantinos Mampentzidis

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1706.10284

zbMATH Keywords

phylogenetic treetriplet distancecache-oblivious algorithmtree comparison

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05) Analysis of algorithms (68W40) Data structures (68P05)

Abstract: We study the problem of computing the triplet distance between two rooted unordered trees with $n$ labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically best algorithm is an $mathrmO(nlogn)$ time algorithm by Brodal et al. (SODA 2013). Recently Jansson and Rajaby proposed a new algorithm that, while slower in theory, requiring $mathrmO(nlo{g}^{3}n)$ time, in practice it outperforms the theoretically faster $mathrmO(nlogn)$ algorithm. Both algorithms do not scale to external memory. We present two cache oblivious algorithms that combine the best of both worlds. The first algorithm is for the case when the two input trees are binary trees and the second a generalized algorithm for two input trees of arbitrary degree. Analyzed in the RAM model, both algorithms require $mathrmO(nlogn)$ time, and in the cache oblivious model $mathrmO(fracnBlo{g}_{2}fracnM)$ I/Os. Their relative simplicity and the fact that they scale to external memory makes them achieve the best practical performance. We note that these are the first algorithms that scale to external memory, both in theory and practice, for this problem.

Recommendations

• Cache oblivious algorithms for computing the triplet distance between trees
• Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree
• An efficient algorithm for the rooted triplet distance between galled trees
• Distance Approximating Trees: Complexity and Algorithms
• Fast algorithms for the rooted triplet distance between caterpillars
• Computing the rooted triplet distance between galled trees by counting triangles
• Computing the rooted triplet distance between galled trees by counting triangles
• A fast algorithm for constructing trees from distance matrices

Cites work

• scientific article; zbMATH DE number 3484087 (Why is no real title available?)
• An efficient algorithm for the rooted triplet distance between galled trees
• Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
• Cache-oblivious algorithms
• Comparing and aggregating partially resolved trees
• Comparison of phylogenetic trees
• Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree
• Inferring evolutionary trees with strong combinatorial evidence
• On the Scalability of Computing Triplet and Quartet Distances

Cited in

(8)

• A cubic-time algorithm for computing the trinet distance between level-1 networks
• Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
• Cache oblivious algorithms for computing the triplet distance between trees
• An efficient algorithm for the rooted triplet distance between galled trees
• On the Scalability of Computing Triplet and Quartet Distances
• Computing the rooted triplet distance between phylogenetic networks
• Fast algorithms for the rooted triplet distance between caterpillars
• scientific article; zbMATH DE number 7564377 (Why is no real title available?)

Describes a project that uses

Uses Software

• tqDist

This page was built for publication: Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111707)