2026/06/18 by Jesper Jansson, Wing-Kin Sung, Seyed Ali Tabatabaee +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Genomics and Phylogenetic Studies #Genome Rearrangement Algorithms #Algorithms and Data Compression
paper · doi:10.1016/j.jcss.2026.103831
A consensus tree is a phylogenetic tree that summarizes the evolutionary relationships inferred from a collection of phylogenetic trees with the same set of leaf labels. Among the many types of consensus trees that have been proposed in the last fifty years, the frequency difference consensus tree is one of the more finely resolved types that retains a large amount of information. This article presents a new deterministic algorithm for constructing the frequency difference consensus tree. Given k phylogenetic trees with identical sets of n leaf labels, it runs in O ( k n log n ) time, improving the best previously known solution. Furthermore, we demonstrate that the implementation of our algorithm is faster in practice than the prior implementations for the same problem.