Homological integration: Difference between revisions
Jump to navigation
Jump to search
en>CaroleHenson m clean up using AWB |
en>Daniele.tampieri m Added detail to a reference. |
||
| Line 1: | Line 1: | ||
The '''quartet distance''' is a way of measuring the distance between two [[phylogenetic tree]]s. It is defined as the number of subsets of four leaves that are not related by the same topology in both trees. | |||
==Computing the quartet distance== | |||
The most straightforward computation of the quartet distance would require <math>O(N^4)</math> time, where <math>N</math> is the number of leaves in the trees. | |||
For binary trees, better algorithms have been found to compute the distance in | |||
* <math>O(N^2)</math> time<ref>{{citejournal | |||
|last=Bryant | |||
|first=D. | |||
|coauthors=J. Tsang, P. E. Kearney, and M. Li. | |||
|title=Computing the quartet distance between evolutionary trees | |||
|journal=Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms | |||
|pages=285–286 | |||
|publisher=ACM Press | |||
|location=[[New York City|N.Y.]] | |||
|date=11 Jan 2000 | |||
|url=http://monod.uwaterloo.ca/papers/00Distance.ps}}</ref> | |||
* <math>O(N \log^2 N)</math> time<ref>{{citebook | |||
|last=Brodal|first=Gerth Stølting | |||
|coauthor=Rolf Fagerberg and Christian N.S. Pedersen | |||
|chapter=Computing the Quartet Distance Between Evolutionary Trees in Time <math>N log^2 N</math> | |||
|title=Algorithmica | |||
|year=2001 | |||
|pages=731–742 | |||
|publisher=Springer-Verlag}}</ref> | |||
and | |||
* <math>O(N \log N)</math> time<ref>{{citejournal | |||
|last=Brodal | |||
|first=Gerth Stølting | |||
|coauthors=Rolf Fagerberg and Christian Nørgaard Storm Pedersen | |||
|journal=Algorithmica, Special issue on ISAAC 2001 | |||
|issue=2 | |||
|pages=377–395 | |||
|title=Computing the Quartet Distance Between Evolutionary Trees in Time <math>O(n\log n)</math> | |||
|volume=38 | |||
|year=2003}}</ref> | |||
Christiansen et al. found an algorithm that takes <math>O(N^2D^2)</math> time to compute the quartet distance between two multifurcating trees when <math>D</math> is the maximum degree of the trees.<ref>{{citejournal | |||
|last=Christiansen | |||
|first=C | |||
|coauthors=T Mailund, CNS Pedersen, M Randers | |||
|journal=Proceedings of Workshop on Algorithms in Bioinformatics (WABI) | |||
|volume=3692 | |||
|publisher=Springer-Verlag | |||
|year=2005 | |||
|title=Computing the Quartet Distance Between Trees of Arbitrary Degree | |||
|pages=77–88}}</ref> | |||
==References== | |||
<references/> | |||
{{DEFAULTSORT:Quartet Distance}} | |||
[[Category:Computational phylogenetics]] | |||
[[Category:Bioinformatics algorithms]] | |||
Revision as of 16:44, 13 July 2013
The quartet distance is a way of measuring the distance between two phylogenetic trees. It is defined as the number of subsets of four leaves that are not related by the same topology in both trees.
Computing the quartet distance
The most straightforward computation of the quartet distance would require time, where is the number of leaves in the trees.
For binary trees, better algorithms have been found to compute the distance in
and
- time[3]
Christiansen et al. found an algorithm that takes time to compute the quartet distance between two multifurcating trees when is the maximum degree of the trees.[4]