摘要
<p>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(min{k(2)n, kn(2)}+ kn lg(2)n)<br /> -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 lg(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.</p>
