.png){kind=icon}
返回
Improved Fixed-Parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network
.png){kind=icon}
PRE
AI
DOI：10.1109/TCBB.2021.3111660.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 structurerestricted. There is almost no algorithm for its unrooted version except the recent fixed-parameter algorithm with runtime O(4(k)n(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 Oo2:594kn2THORN in the paper. Additionally, we experimentally show its effectiveness on biological data and simulated data.
Keyword:
Phylogeny
Vegetation
Runtime
Uncertainty
Computational modeling
Time complexity
Sorting
Phylogenetic tree
phylogenetic network
unrooted tree containment problem
fixed-parameter algorithm
期刊
I
IF:
3.4
论文数:
3.3K
被引数:
6.4K
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容