A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees多叉树最大一致森林问题参数算法研究

被引：0
作者：
Feng Shi
Jianxin Wang
Yufei Yang
Qilong Feng
Weilong Li
Jianer Chen
机构：
[1] Central South University,School of Information Science and Engineering
[2] Texas A&M University,Department of Computer Science and Engineering
[3] College Station,undefined
来源：
Science China Information Sciences | 2016年 / 59卷
关键词：
computational biology; multifurcating phylogenetic tree; maximum agreement forest; TBR distance; fixed-parameter algorithm; 012102; 计算生物学; 多叉系统发生树; 最大一致森林; TBR距离; 固定参数算法;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The Maximum Agreement Forest (MAF) problem on two given phylogenetic trees is an important NP-hard problem in the field of computational biology. In this paper, we study the parameterized version of the MAF problem: given two unrooted (multifurcating) phylogenetic trees T1 and T2 with the same leaf-label set L, and a parameter k, either construct an agreement forest of at most k trees for T1 and T2, or report that no such a forest exists. Whether there is a fixed-parameter tractable algorithm for this problem was posed as an open problem several times in the literature. In this paper, we resolve this open problem by presenting a parameterized algorithm of running time O(4kn5) for the problem.
引用
收藏
页码：1 / 14
页数：13
相关论文
共 60 条
  • [1] Hillis D M(1999)Predictive evolution Science 286 1866-1867
  • [2] Robinson D F(1981)Comparison of phylogenetic trees Math Biosci 53 131-147
  • [3] Foulds L R(1996)On the nearest neighbour interchange distance between evolutionary trees J Theor Biol 182 463-467
  • [4] Li M(1996)On the complexity of comparing evolutionary trees Discrete Appl Math 71 153-169
  • [5] Tromp J(2001)Subtree transfer operations and their induced metrics on evolutionary trees Ann Comb 5 1-15
  • [6] Zhang L(2005)On the computational complexity of the rooted subtree prune and regraft distance Ann Comb 8 409-423
  • [7] Hein J(2008)SPR distance computation for unrooted trees Evol Bioinform Online 4 17-182
  • [8] Jiang T(2005)Bounding the number of hybridisation events for a consistent evolutionary history J Math Biol 51 171-878
  • [9] Wang L(2014)On unknown small subsets and implicit measures: new techniques for parameterized algorithms J Comput Sci Technol 29 870-140
  • [10] Allen B L(2015)Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems J Comb Optim 29 125-94
123456