A phylogenetic tree is a popular structure used by both biologists and computer scientists to infer evolutionary relationships among various species. In spite of its popularity, different methods, datasets, heuristics and so on used to generate these trees produce differently structured trees resulting in disagreement and conflicts. This motivated the idea of the so-called consensus tree, which is used “to reconcile structural differences and remove inconsistencies in a collection of trees,” according to the authors. However, depending on the application and other factors, there could be different ways to define a consensus tree. This paper presents algorithms for constructing consensus trees considering the three most widely used definitions thereof, namely, the majority rule consensus tree, the loose consensus tree, and the greedy consensus tree.
The main results of this paper can be summarized as follows. The authors have presented “fast deterministic algorithms for computing the majority rule consensus tree, the loose consensus tree, and a greedy consensus tree” given an input set S of trees with identical leaf label sets. The former two algorithms run in O(nk) time and the latter in O(n2k) time, where k is the number of trees in S and n is the number of leaves in a tree in the input set. All of the trees in the input set are assumed to have the same set of leaves.
Theoretically, the results presented here are significant. The first two algorithms are in fact optimal; hence, the authors now have the credit for solving two long-standing open problems in phylogenetics. But, possibly more importantly, the authors should be given credit because their results are not confined within theoretical boundaries:
- The authors have implemented their algorithms efficiently.
- They have described the modifications in their implementation that make their algorithms faster in practice, keeping the original running time and deterministic nature of the algorithms intact.
- They have experimented on simulated datasets of varying sizes and compared the running times to those of some freely available, widely used software. Their algorithms, as the authors show through their experimental results, “are competitive against the currently available software, even though our algorithms do not use any randomization.”
- Their implementations, as well as the source code, are available as a package called Fast Algorithms for Consensus Trees (FACT) with a web interface for use by others.
Finally, the authors discuss possible extensions of their work focusing on other definitions of consensus trees. The idea that their package, FACT, would continue to be extended with new results is encouraging and should be useful for bioinformatics researchers and practitioners.
