Least Common Ancestor Based Method for Efficiently Constructing Rooted Supertrees

M. A. Hai Zahid, Ankush Mittal, R. C. Joshi

Department of Electronics and Computer Engineering, IIT-Roorkee

Roorkee, Uttaranchal, INDIA

http://www.iitr.ernet.in

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.  

Key words: phylogenetic tree, phylogenetic supertrees, optimality criteria, least common ancestor, and compatibility.