Computing the All-Pairs Quartet Distance on a set of Evolutionary Trees

Martin Stissing, Thomas Mailund, Christian Nørgaard Storm Pedersen, Gerth Stølting Brodal, and Rolf Fagerberg

In Proc. 5th Asia Pacific Bioinformatics Conference, Advances in Bioinformatics & Computational Biology, pages 91-100. Imperial College Press, 2007.

Abstract

We present two algorithms for calculating the quartet distance between all pairs of trees in a set of binary evolutionary trees on a common set of species. The algorithms exploit common substructure among the trees to speed up the pairwise distance calculations thus performing significantly better on large sets of trees compared to performing distinct pairwise distance calculations, as we illustrate experimentally, where we see a speedup factor of around 130 in the best case.

Copyright notice

Copyright © 2007 by Imperial College Press

Online version

apbc07apq.pdf (418 Kb)

DOI

10.1142/9781860947995_0012

BIBT_EX entry

@incollection{apbc07apq,
  author = "Martin Stissing and Thomas Mailund and Christian Nørgaard Storm Pedersen and Gerth Stølting Brodal and Rolf Fagerberg",
  booktitle = "Proc. 5th Asia Pacific Bioinformatics Conference",
  doi = "10.1142/9781860947995_0012",
  isbn = "978-1-86094-783-4",
  pages = "91-100",
  publisher = "Imperial College Press",
  series = "Advances in Bioinformatics \& Computational Biology",
  title = "Computing the All-Pairs Quartet Distance on a set of Evolutionary Trees",
  year = "2007"
}