Algorithms for constructing multi-labeled phylogenetic trees from quartets with fewer leaf duplications

Abstract

A central problem in computational and evolutionary biology is the inference of phylogenetic tree from a set of triplets or quartets. Researchers try to construct phylogenetic tree by com¬bining many triplets or quartets into a single phylogenetic tree and this problem is known as supertree construction problem. The problem with supertree construction is that the con¬structed supertree does not always ensure the consistency of the entire input quartets from where it is designed and hence some important evolutionary information is lost. A possible solution of this problem is to construct Multi-labeled Phylogenetic Trees (MUL-trees) instead of supertree where all quartets are consistent. Let Q= {q1, q2, q3,..., qk} be a collection of quartets over a set of taxa S. A MUL-tree T over a set of quartets Q is a tree where more than one of its leaves can be labeled by a single taxon and each quartet qϵQare consistent with respect to the tree T. The problem of constructing a MUL-tree from a set of quartets is much more complex than that of standard phylogenetic trees. To the best of our knowledge, there is no study to construct MUL-trees from quartets to date. In this thesis, we have proposed two algorithms with three auxiliary techniques to construct MUL-trees from a set of quartets. We first have proposed a bipartition based divide and conquer approach (QMUL) with super-split analysis technique. But it cannot always guarantee the minimum number of duplications. To overcome the shortcoming of QMUL approach we finally proposed AQMUL (MUL-trees from Quartets with Advanced method) approach which is the modification of QMUL approach. We have conducted experiments on simulated datasets and real datasets to analyze the performance of our proposed algorithms. We have found that AQMUL is more efficient than QMUL to construct MUL-Trees in terms of average number of duplications.