• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE/ACM transactions on computational biology and bioinformatics >Improved Fixed-Parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network
【24h】

Improved Fixed-Parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network

机译：Improved Fixed-Parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network

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

摘要

Phylogenetic trees are unable to represent the evolutionary process for a collection of species if reticulation events happened, and a generalized model named phylogenetic network was introduced consequently. However, the representation of the evolutionary process for one gene is actually a phylogenetic tree that is “contained” in the phylogenetic network for the considered species containing the gene. Thus a fundamental computational problem named Tree Containment problem arises, which asks whether a phylogenetic tree is contained in a phylogenetic network. The previous research on the problem mainly focused on its rooted version of which the considered tree and network are rooted, and several algorithms were proposed when the considered network is binary or structure-restricted. There is almost no algorithm for its unrooted version except the recent fixed-parameter algorithm with runtime $O(4^kn^2)$ , where $k$ and $n$ are the reticulation number and size of the considered unrooted binary phylogenetic network $N$ , respectively. As the runtime is a little expensive when considering big values of $k$ , we aim to improve it and successfully propose a fixed-parameter algorithm with runtime $O(2.594^kn^2)$ in the paper. Additionally, we experimentally show its effectiveness on biological data and simulated data.

著录项

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号