...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >COSPEDTree: COuplet Supertree by Equivalence Partitioning of Taxa Set and DAG Formation
【24h】

COSPEDTree: COuplet Supertree by Equivalence Partitioning of Taxa Set and DAG Formation

机译：COSPEDTree：通过分类单元和DAG形成的等价划分的Couplet超级树

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 ) 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.
机译：从一组具有重叠分类单元集的系统发育树中，一棵超级树显示了所有输入分类单元之间的进化关系。关键是要解决各个分类单元子集之间与输入树有关的矛盾关系。 NP难题的表述采用局部搜索启发式方法来减少树的搜索空间，或者解决与固定或可变大小的子树级别分解有关的冲突。不同的近似技术会产生性能差异很大的超级树。此外，大多数算法都涉及很高的计算复杂度，因此不适合用于大型生物数据集。当前的研究提出了COSPEDTree，这是一种用于构建超级树的新方法。该技术通过分析每个源树的对联（分类对）关系来解决源树冲突。随后，单个分类单元对通过单个关系解析。为了优先解决各个分类单元对之间的共有关系以解决它们，采用贪婪评分为分类单元对之间的共有关系分配较高的得分值。解决单个分类单元对的选定关系集随后用于构建有向无环图（DAG）。 DAG的顶点表示从同一物种事件推断出的分类单元子集。因此，COSPEDTree也可以生成非二进制超树。在此DAG上进行深度优先遍历将产生最终的超级树。根据分支不相似（例如FP，FN和RF）的性能指标，COSPEDTree生成的大多数保守且解析度很高的超树。具体来说，与参考方法相比，RF指标大多较低，而FP值仅与严格的保守（或）方法相比较低。 COSPEDTree在最坏情况下的时间和空间复杂度分别为立方和二次，与参考方法相比具有更好的可比性。这样的高性能和低计算成本使OSPEDTree可以应用于大规模生物数据集。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号