Paper Info
Title
Couplet supertree by equivalence partitioning of taxa set and DAG formation
Abstract
From a given set of phylogenetic trees with overlapping taxa sets, a supertree describes evolutionary relationships among the union of their constituent taxa sets. Individual taxa subsets, however, can exhibit conflicting evolutionary relationships for different input trees. Strict consensus supertrees do not include any taxa subset exhibiting conflicts, thus can be non-plenary1. Plenary supertrees, on the other hand, aims to satisfy maximum agreement property, by resolving conflicts with the consensus (most frequent) relation (with respect to the input trees) between corresponding taxa subset. However, satisfying such property is NP hard. Existing studies propose various approximations based on matrix or graph representation, or using subtree level decomposition, for supertree construction. Most of these approaches involve high computational complexity. Further, accuracy of most of these methods need to be improved for application in large biological datasets. Current study presents a supertree construction method, named COSPEDTree, by analyzing couplet (taxa pair) relationships and their conflicts (contradictions) with respect to the source trees. To the best of our knowledge, such couplet based supertree construction is not proposed before. To prioritize the consensus relations for resolving individual taxa pairs, a greedy scoring method is suggested. Selected relations between individual taxa pairs are used to model a Directed Acyclic Graph (DAG), which subsequently generates the final supertree. Performance of COSPEDTree, in terms of lower values of branch dissimilarities between the derived supertree and the candidate source trees, are mostly better or comparable with existing methods. COSPEDTree involves worst case time and space complexities of cubic and quadratic orders, respectively, both of which are best among reference approaches. So, it can be used for large biological datasets. It is hosted in http://telemedik.iitkgp.ernet.in/COSPEDTree_BCB.zip.
Year
DOI
Venue
2014
10.1145/2649387.2649388
BCB
Keywords
Field
DocType
efficiency,algorithms,directed acyclic graph,trees,biology and genetics,graph algorithms,algorithm design and analysis,theory,phylogenetics,supertree
Equivalence partitioning,Combinatorics,Phylogenetic tree,Tree (data structure),Directed acyclic graph,Supertree,Bioinformatics,Taxon,Mathematics,Graph (abstract data type),Computational complexity theory
Conference
Citations 
PageRank 
References 
2
0.37
19
Authors
2
Name
Order
Citations
PageRank
Sourya Bhattacharyya1174.35
Jayanta Mukhopadhyay27226.05