The quartet distance is a way of measuring the distance between two phylogenetic tree

Phylogenetic tree

A phylogenetic tree or evolutionary tree is a branching diagram or "tree" showing the inferred evolutionary relationships among various biological species or other entities based upon similarities and differences in their physical and/or genetic characteristics...

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 time, where is the number of leaves in the trees.

For binary trees, better algorithms have been found to compute the distance in

• time
• time

and

• time

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.