tqDist: A Library for Computing the Quartet and Triplet Distances Between Binary or General Trees

Andreas Sand, Morten Kragelund Holt, Jens Johansen, Gerth Stølting Brodal, Thomas Mailund, and Christian Nørgaard Storm Pedersen

In Bioinformatics, 2014.

Abstract

Summary: tqDist is a software package for computing the triplet and quartet distances between general rooted or unrooted trees, respectively. The program is based on algorithms with running time O(nlog n) for the triplet distance calculation and O(d nlog n) for the quartet distance calculation, where n is the number of leaves in the trees and d is the degree of the tree with minimum degree. These are currently the fastest algorithms both in theory and in practice.

Availability and implementation: tqDist can be installed on Windows, Linux and Mac OS X. Doing this will install a set of command-line tools together with a Python module and an R package for scripting in Python or R. The software package is freely available under the GNU LGPL licence at http://birc.au.dk/software/tqDist.

Copyright notice

Copyright © 2014 by Oxford University Press. All rights reserved.

Online version

bioinformatics14.pdf (419 Kb)

DOI

10.1093/bioinformatics/btu157

BIBTEX entry

@article{bioinformatics14,
  author = "Andreas Sand and Morten Kragelund Holt and Jens Johansen and Gerth St{\o}lting Brodal and Thomas Mailund and Christian N{\o}rgaard Storm Pedersen",
  doi = "10.1093/bioinformatics/btu157",
  issn = "1460-2059",
  journal = "Bioinformatics",
  title = "tqDist: A Library for Computing the Quartet and Triplet Distances Between Binary or General Trees",
  year = "2014"
}