A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees

被引：0
作者：
Feng SHI [1 ]
Jianxin WANG [1 ]
Yufei YANG [1 ]
Qilong FENG [1 ]
Weilong LI [1 ]
Jianer CHEN [1 ,2 ]
机构：
[1] School of Information Science and Engineering, Central South University
[2] Department of Computer Science and Engineering, Texas A&M University, College Station
来源：
ScienceChina(InformationSciences) | 2016年 / 59卷 / 01期
基金：
高等学校博士学科点专项科研基金; 中国国家自然科学基金;
关键词：
computational biology; multifurcating phylogenetic tree; maximum agreement forest; TBR distance; fixed-parameter algorithm;
D O I：
暂无
中图分类号：
TP301.6 [算法理论];
学科分类号：
081202 ;
摘要：
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 Tand Twith the same leaf-label set L, and a parameter k, either construct an agreement forest of at most k trees for Tand T, 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(4~kn~5) for the problem.
引用
收藏
页码：66 / 79
页数：14
相关论文
共 29 条
  • [1] A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees
    Shi, Feng
    Wang, Jianxin
    Yang, Yufei
    Feng, Qilong
    Li, Weilong
    Chen, Jianer
    SCIENCE CHINA-INFORMATION SCIENCES, 2016, 59 (01) : 1 - 14
  • [2] A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees多叉树最大一致森林问题参数算法研究
    Feng Shi
    Jianxin Wang
    Yufei Yang
    Qilong Feng
    Weilong Li
    Jianer Chen
    Science China Information Sciences, 2016, 59 : 1 - 14
  • [3] A parameterized algorithm for the Maximum Agreement Forest problem on multiple rooted multifurcating trees
    Shi, Feng
    Chen, Jianer
    Feng, Qilong
    Wang, Jianxin
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 97 : 28 - 44
  • [4] Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees
    Chen, Jianer
    Fan, Jia-Hao
    Sze, Sing-Hoi
    THEORETICAL COMPUTER SCIENCE, 2015, 562 : 496 - 512
  • [5] FIXED-PARAMETER ALGORITHMS FOR FINDING AGREEMENT SUPERTREES
    Fernandez-Baca, David
    Guillemot, Sylvain
    Shutters, Brad
    Vakati, Sudheer
    SIAM JOURNAL ON COMPUTING, 2015, 44 (02) : 384 - 410
  • [6] Algorithms for parameterized maximum agreement forest problem on multiple trees
    Shi, Feng
    Wang, Jianxin
    Chen, Jianer
    Feng, Qilong
    Guo, Jiong
    THEORETICAL COMPUTER SCIENCE, 2014, 554 : 207 - 216
  • [7] A fixed-parameter algorithm for the vertex cover P3 problem
    Tu, Jianhua
    INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 96 - 99
  • [8] Fixed-parameter tractability for the Tree Assembly problem
    Shi, Feng
    You, Jie
    Zhang, Zhen
    Liu, Jingyi
    Wang, Jianxin
    THEORETICAL COMPUTER SCIENCE, 2021, 886 : 3 - 12
  • [9] Improved Fixed-Parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network
    Shi, Feng
    Li, Hangcheng
    Rong, Guozhen
    Zhang, Zhen
    Wang, Jianxin
    IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2022, 19 (06) : 3539 - 3552
  • [10] A fixed-parameter algorithm for minimum quartet inconsistency
    Gramm, J
    Niedermeier, R
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) : 723 - 741
123