Quartet Distance

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 $O(N^4)$ time, where $N$ is the number of leaves in the trees.

For binary trees, better algorithms have been found to compute the distance in
* $O(N^2)$ time
* $O(N \log^2 N)$ time
and
* $O(N \log N)$ time

Gerth Stølting Brodal ''et al.'' found an algorithm that takes $O(D N \log N)$ time to compute the quartet distance between two multifurcating trees when $D$ is the maximum degree of the trees, which i
accessible
in C, perl, and the R packag
Quartet

References

{{DEFAULTSORT:Quartet Distance
Computational phylogenetics
Bioinformatics algorithms