Faster Algorithms for Constructing Frequency Difference Consensus Trees

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.