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

详细信息    查看全文

• 作者：Feng Shi ; Jianxin Wang ; Yufei Yang ; Qilong Feng…
• 关键词：computational biology ; multifurcating phylogenetic tree ; maximum agreement forest ; TBR distance ; fixed ; parameter algorithm
• 刊名：SCIENCE CHINA Information Sciences
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：59
• 期：1
• 页码：1-14
• 全文大小：335 KB
• 参考文献：1.Hillis D M. Predictive evolution. Science, 1999, 286: 1866–1867CrossRef
  2.Ding Z, Filkov V, Gusfield D. A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem. In: Proceedings of 9th Annual International Conference of Research in Computational Molecular Biology (RECOMB 2005), Cambridge, 2005. 585–600
  3.Warnow T, Ringe D, Taylor A. Reconstructing the evolutionary history of natural languages. In: Proceedings of 7th ACM-SIAM Symposium on Discrete Algorithms (SODA 1996), Atlanta, 1996. 314–322
  4.Robinson D F, Foulds L R. Comparison of phylogenetic trees. Math Biosci, 1981, 53: 131–147MathSciNet CrossRef MATH
  5.Li M, Tromp J, Zhang L. On the nearest neighbour interchange distance between evolutionary trees. J Theor Biol, 1996, 182: 463–467CrossRef
  6.Das Gupta B, He X, Jiang T, et al. On distances between phylogenetic trees. In: Proceedings of 8th ACM-SIAM Symposium of Discrete Algorithms (SODA 1997), New Orleans, 1997. 427–436
  7.Swofford D, Olsen G, Waddell P, et al Phylogenetic inference. In: Hillis D, Moritz C, Mable B, eds. Molecular Systematics. 2nd ed. Sunderland: Sinauer Associates, 1996. 407–513
  8.Hein J, Jiang T, Wang L, et al. On the complexity of comparing evolutionary trees. Discrete Appl Math, 1996, 71: 153–169MathSciNet CrossRef MATH
  9.Allen B L, Steel M. Subtree transfer operations and their induced metrics on evolutionary trees. Ann Comb, 2001, 5: 1–15MathSciNet CrossRef MATH
  10.Bordewich M, Semple C. On the computational complexity of the rooted subtree prune and regraft distance. Ann Comb, 2005, 8: 409–423MathSciNet CrossRef MATH
  11.Hickey G, Dehne F, Rau-Chaplin A, et al. SPR distance computation for unrooted trees. Evol Bioinform Online, 2008, 4: 17
  12.Baroni M, Grnewald S, Moulton V, et al. Bounding the number of hybridisation events for a consistent evolutionary history. J Math Biol, 2005, 51: 171–182MathSciNet CrossRef MATH
  13.Chen J E, Feng Q L. On unknown small subsets and implicit measures: new techniques for parameterized algorithms. J Comput Sci Technol, 2014, 29: 870–878MathSciNet CrossRef
  14.Feng Q L, Wang J X, Li S H, et al. Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems. J Comb Optim, 2015, 29: 125–140MathSciNet CrossRef MATH
  15.Feng Q L, Wang J X, Chen J E. Matching and weighted P2-Packing: algorithms and kernels. Theor Comput Sci, 2014, 522: 85–94MathSciNet CrossRef MATH
  16.Feng Q L, Wang J X, Xu C, et al. Improved parameterized algorithms for minimum link-length rectilinear spanning path problem. Theor Comput Sci, 2014, 560: 158–171MathSciNet CrossRef MATH
  17.Wang J X, Tan P Q, Yao J Y, et al. On the minimum link-length rectilinear spanning path problem: complexity and algorithms. IEEE Trans Comput, 2014, 63: 3092–3100MathSciNet CrossRef
  18.Wang J X, Li W J, Li S H, et al. On the parameterized vertex cover problem for graphs with perfect matching. Sci China Inf Sci, 2014, 57: 072107MathSciNet MATH
  19.Downy R, Fellows M. Parameterized Complexity. New York: Springer-Verlag, 1999CrossRef
  20.Hallett M, Mccartin C. A faster FPT algorithm for the maximum agreement forest problem. Theory Comput Syst, 2007, 41: 539–550MathSciNet CrossRef MATH
  21.Whidden C, Zeh N. A Unifying View on Approximation and FPT of Agreement Forests. Berlin/Heidelberg: Springer, 2009CrossRef
  22.Linz S, Semple C. Hybridization in nonbinary trees. IEEE/ACM Trans Comput Biol Bioinform, 2009, 6: 30–45CrossRef
  23.Whidden C, Beiko R G, Zeh N. Fixed-parameter and approximation algorithms for maximum agreement forests. arXiv preprint, arXiv:1108.2664, 2011MATH
  24.Paun O, Lehnebach C, Johansson J T, et al. Phylogenetic relationships and biogeography of Ranunculus and allied genera (Ranunculaceae) in the Mediterranean region and in the European alpine system. Taxon, 2005, 54: 911–932CrossRef
  25.Willyard A, Wallace L E, Wagner W L, et al. Estimating the species tree for Hawaiian Schiedea (Caryophyllaceae) from multiple loci in the presence of reticulate evolution. Mol Phylogenet Evol, 2011, 60: 29–48CrossRef
  26.Maddison W. Reconstructing character evolution on polytomous cladograms. Cladistics, 1989, 5: 365–377CrossRef
  27.Whelan S, Money D. The prevalence of multifurcations in tree-space and their implications for tree-search. Mol Biol Evol, 2010, 27: 2674–2677CrossRef
  28.Beiko R G, Hamilton N. Phylogenetic identification of lateral genetic transfer events. BMC Evol Biol, 2006, 6: 15CrossRef
  29.Rodrigues E M, Sagot M F, Wakabayashi Y. The maximum agreement forest problem: approximation algorithms and computational experiments. Theor Comput Sci, 2007, 374: 91–110MathSciNet CrossRef MATH
  30.Buneman P. The recovery of trees from measures of issimilarity. In: Hodson F, Kendall D, Tauta P, eds. Mathematics in the Archaeological and Historical Sciences. Edinburgh: Edinburgh University Press, 1971. 387–395
  31.Chen J E, Fan J H, Sze S H. Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees. Theor Comput Sci, 2015, 562: 496–512MathSciNet CrossRef MATH
  32.Shi F, Wang J, Chen J E, et al. Algorithms for parameterized maximum agreement forest problem on multiple trees. Theor Comput Sci, 2014, 554: 207–216MathSciNet CrossRef MATH
  
• 作者单位：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, Changsha, 410083, China
  2. Department of Computer Science and Engineering, Texas A&M University, College Station, Texas, 77843-3112, USA
  
• 刊物类别：Computer Science
• 刊物主题：Chinese Library of Science
  Information Systems and Communication Service
  
• 出版者：Science China Press, co-published with Springer
• ISSN：1869-1919

文摘

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 T ₁ and T ₂ with the same leaf-label set L, and a parameter k, either construct an agreement forest of at most k trees for T ₁ and 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 k n 5) for the problem.