Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree

Gerth Stølting Brodal, Rolf Fagerberg, Thomas Mailund, Christian Nørgaard Storm Pedersen, Andreas Sand

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisKonferenceartikelForskningpeer review

670 Downloads (Pure)

Abstract

The triplet and quartet distances are distance measures to compare two rooted and two unrooted trees, respectively. The leaves of the two trees should have the same set of n labels. The distances are defined by enumerating all subsets of three labels (triplets) and four labels (quartets), respectively, and counting how often the induced topologies in the two input trees are different. In this paper we present efficient algorithms for computing these distances. We show how to compute the triplet distance in time O(n log n) and the quartet distance in time O(dn log n), where d is the maximal degree of any node in the two trees. Within the same time bounds, our framework also allows us to compute the parameterized triplet and quartet distances, where a parameter is introduced to weight resolved (binary) topologies against unresolved (non-binary) topologies. The previous best algorithm for computing the triplet and parameterized triplet distances have O(n^2) running time, while the previous best algorithms for computing the quartet distance include an O(d^9 n log n) time algorithm and an O(n^2.688) time algorithm, where the latter can also compute the parameterized quartet distance. Since d ≤ n, our algorithms improve on all these algorithms.
OriginalsprogEngelsk
TidsskriftThe Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings
Vol/bind24
Sider (fra-til)1814-1832
Antal sider19
ISSN1071-9040
StatusUdgivet - 2013
BegivenhedACM-SIAM Symposium on Discrete Algorithms - New Orleans, USA
Varighed: 6 jan. 20138 jan. 2013
Konferencens nummer: 24

Konference

KonferenceACM-SIAM Symposium on Discrete Algorithms
Nummer24
Land/OmrådeUSA
ByNew Orleans
Periode06/01/201308/01/2013

Emneord

  • triplet distance
  • quartet distance

Fingeraftryk

Dyk ned i forskningsemnerne om 'Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree'. Sammen danner de et unikt fingeraftryk.

Citationsformater