Figure 1.
Difference in procedure between the original UniFrac and the new Fast UniFrac (for clarity, only the unweighted UniFrac algorithm is shown here, but similar principles apply to weighted UniFrac). In the original procedure, (A) environments are stored as sets in a tree object, (B) the tree is pruned to include only the branches leading to wanted environments, (C) the sets of environments are compared using set algorithms, states are assigned to each internal node, and (D) the result is calculated by another tree traversal. In the new procedure, (E) the environments are stored as an array of tip × environment counts, (F) selected environments are chosen by slicing this array, (G) internal states are calculated using array operations on slices of the array, and (H) the products of the incidence array and the branch lengths of nodes leading to either or both of the environments are summed, allowing calculation of the UniFrac value. The array-based approach allows substantial gains in efficiency.