Least Common Ancestor Based Method for Efficiently Constructing Rooted Supertrees

Phylogenetic supertree is a collection of different phylogenetic trees combined into a single tree forming a tree of life. The smaller overlapping phylogenetic trees are combined in such a way that no branching information is lost. This problem is important for several biological applications. Yet the solution is difficult as exponentially large number of supertrees exists for a given set of trees and the optimal tree has to be selected based upon some optimality criteria. In this paper, we propose a polynomial time algorithm for combining phylogenetic trees, which makes use of least common ancestor information as optimality criterion. The algorithm satisfies the desirable properties of a phylogenetic supertree method as mentioned in literature, and constructs a single phylogenetic supertree even for incompatible input trees which is difficult to solve. Experimental results and comparisons with other works show the superiority of our algorithm.