Paper Info
Title
COSPEDTree: COuplet Supertree by Equivalence Partitioning of Taxa Set and DAG Formation
Abstract
From a set of phylogenetic trees with overlapping taxa set, a supertree exhibits evolutionary relationships among all input taxa. The key is to resolve the contradictory relationships with respect to input trees, between individual taxa subsets. Formulation of this NP hard problem employs either local search heuristics to reduce tree search space, or resolves the conflicts with respect to fixed or varying size subtree level decompositions. Different approximation techniques produce supertrees with considerable performance variations. Moreover, the majority of the algorithms involve high computational complexity, thus not suitable for use on large biological data sets. Current study presents COSPEDTree, a novel method for supertree construction. The technique resolves source tree conflicts by analyzing couplet (taxa pair) relationships for each source trees. Subsequently, individual taxa pairs are resolved with a single relation. To prioritize the consensus relations among individual taxa pairs for resolving them, greedy scoring is employed to assign higher score values for the consensus relations among a taxa pair. Selected set of relations resolving individual taxa pairs is subsequently used to construct a directed acyclic graph (DAG). Vertices of DAG represents a taxa subset inferred from the same speciation event. Thus, COSPEDTree can generate non-binary supertrees as well. Depth first traversal on this DAG yields final supertree. According to the performance metrics on branch dissimilarities (such as FP, FN and RF), COSPEDTree produces mostly conservative, well resolved supertrees. Specifically, RF metrics are mostly lower compared to the reference approaches, and FP values are lower apart from only strictly conservative (or veto) approaches. COSPEDTree has worst case time and space complexities of cubic and quadratic order, respectively, better or comparable to the reference approaches. Such high performance and low computational costs enable - OSPEDTree to be applied on large scale biological data sets.
Year
DOI
Venue
2015
10.1109/TCBB.2014.2366778
Computational Biology and Bioinformatics, IEEE/ACM Transactions  
Keywords
Field
DocType
directed acyclic graph (dag),phylogenetics,supertrees,computational biology,phylogeny,materials requirements planning,measurement
Biological data,Phylogenetic tree,Depth-first search,Tree (data structure),Algorithm,Supertree,Directed acyclic graph,Local search (optimization),Bioinformatics,Mathematics,Computational complexity theory
Journal
Volume
Issue
ISSN
12
3
1545-5963
Citations 
PageRank 
References 
2
0.38
16
Authors
2
Name
Order
Citations
PageRank
Sourya Bhattacharyya1174.35
Jayanta Mukherjee237856.06