Quartet distance

It is defined as the number of subsets of four leaves that are not related by the same topology in both trees.

The most straightforward computation of the quartet distance would require

For binary trees, better algorithms have been found to compute the distance in and Gerth Stølting Brodal 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,[5] which is accessible in C, perl, and the R package Quartet.