Faster Algorithms for Constructing Frequency Difference Consensus Trees
Biing-Feng Wang, Chih-Yu Li, Wen-Horng Sheu · IEEE Transactions on Computational Biology and Bioinformatics · 2025
Consensus trees have been widely used in evolutionary studies to combine phylogenetic information of individual gene trees. This paper studies one of the most well-known consensus tree methods: the frequency difference consensus tree. Jansson et al. [IEEE/ACM TCBB, 2018] had an $O( {\text{min}}\{ {{{k}^2}n,\ k{{n}^2}} \} + kn\ \mathrm{l}{{\mathrm{g}}^2}n )$-time algorithm for constructing the frequency difference consensus tree of k phylogenetic trees on the same set of n taxa. Later, Gawrychowski et al. [ICALP, 2018] gave an improved upper bound of $O( {kn\ \mathrm{l}{{\mathrm{g}}^2}\ n} )$. This paper further reduces the upper bound to O(kn lg n). In addition, this paper presents a simple $O( {{{k}^2}n} )$-time algorithm. It is the fastest when k = O(lg n). Especially, when k = O(1), linear time is achieved.