2017/05/30 by Gawrychowski, Paweł, Landau, Gad M., Sung, Wing-Kin +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1705.10548
A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in phylogenetic tree reconstruction. It also finds applications in predicting a species tree from a set of gene trees. This paper focuses on two of the most well-known and widely used oconsensus tree methods: the greedy consensus tree and the frequency difference consensus tree. Given k conflicting trees each with n leaves, the previous fastest algorithms for these problems were O(k n2) for the greedy consensus tree [J. ACM 2016] and O(min \ k n2, k2n\) for the frequency difference consensus tree [ACM TCBB 2016]. We improve these running times to O(k n1.5) and O(k n) respectively.