logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 1: 012102(2016) https://doi.org/10.1007/s11432-015-5355-1

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

More info
  • ReceivedOct 8, 2014
  • AcceptedApr 7, 2015
  • PublishedDec 21, 2015

Abstract

There is no abstract available for this article.


Funded by

national Natural Science Foundation of China(61420106009)

national Natural Science Foundation of China(61370172)

national Natural Science Foundation of China(61472449)

national Natural Science Foundation of China(61232001)

Research Fund for the Doctoral Program of Higher Education of China(20130162130001)


Acknowledgment

Acknowledgments

This work was supported by national Natural Science Foundation of China (Grant Nos. 61232001, 61472449, 61370172, 61420106009), and Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20130162130001).


References

[1] Hillis D M. Science, 1999, 286: 1866-1867 CrossRef Google Scholar

[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. Google Scholar

[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. Google Scholar

[4] Robinson D F, Foulds L R. Math Biosci, 1981, 53: 131-147 CrossRef Google Scholar

[5] Li M, Tromp J, Zhang L. J Theor Biol, 1996, 182: 463-467 CrossRef Google Scholar

[6] DasGupta 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. Google Scholar

[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. Google Scholar

[8] Hein J, Jiang T, Wang L, et al. Discrete Appl Math, 1996, 71: 153-169 CrossRef Google Scholar

[9] Allen B L, Steel M. Ann Comb, 2001, 5: 1-15 CrossRef Google Scholar

[10] Bordewich M, Semple C. Ann Comb, 2005, 8: 409-423 CrossRef Google Scholar

[11] Hickey G, Dehne F, Rau-Chaplin A, et al. Evol Bioinform Online, 2008, 4: 17-423 Google Scholar

[12] Baroni M, Grünewald S, Moulton V, et al. J Math Biol, 2005, 51: 171-182 CrossRef Google Scholar

[13] Chen J E, Feng Q L. J Comput Sci Technol, 2014, 29: 870-878 CrossRef Google Scholar

[14] Feng Q L, Wang J X, Li S H, et al. J Comb Optim, 2015, 29: 125-140 CrossRef Google Scholar

[15] Feng Q L, Wang J X, Chen J E. Theor Comput Sci, 2014, 522: 85-94 CrossRef Google Scholar

[16] Feng Q L, Wang J X, Xu C, et al. Theor Comput Sci, 2014, 560: 158-171 CrossRef Google Scholar

[17] Wang J X, Tan P Q, Yao J Y, et al. IEEE Trans Comput, 2014, 63: 3092-3100 CrossRef Google Scholar

[18] Wang J X, Li W J, Li S H, et al. Sci China Inf Sci, 2014, 57: 072107-3100 Google Scholar

[19] Downy R, Fellows M. Parameterized Complexity. New York: Springer-Verlag, 1999. Google Scholar

[20] Hallett M, Mccartin C. Theory Comput Syst, 2007, 41: 539-550 CrossRef Google Scholar

[21] Whidden C, Zeh N. A Unifying View on Approximation and FPT of Agreement Forests. Berlin/Heidelberg: Springer, 2009. Google Scholar

[22] Linz S, Semple C. IEEE/ACM Trans Comput Biol Bioinform, 2009, 6: 30-45 CrossRef Google Scholar

[23] Whidden C, Beiko R G, Zeh N. Fixed-parameter and approximation algorithms for maximum agreement forests. arXiv preprint, arXiv:1108.2664, 2011. Google Scholar

[24] Paun O, Lehnebach C, Johansson J T, et al. Taxon, 2005, 54: 911-932 CrossRef Google Scholar

[25] Willyard A, Wallace L E, Wagner W L, et al. Mol Phylogenet Evol, 2011, 60: 29-48 CrossRef Google Scholar

[26] Maddison W. Cladistics, 1989, 5: 365-377 CrossRef Google Scholar

[27] Whelan S, Money D. Mol Biol Evol, 2010, 27: 2674-2677 CrossRef Google Scholar

[28] Beiko R G, Hamilton N. BMC Evol Biol, 2006, 6: 15-2677 CrossRef Google Scholar

[29] Rodrigues E M, Sagot M F, Wakabayashi Y. Theor Comput Sci, 2007, 374: 91-110 CrossRef Google Scholar

[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. Google Scholar

[31] Chen J E, Fan J H, Sze S H. Theor Comput Sci, 2015, 562: 496-512 CrossRef Google Scholar

[32] Shi F, Wang J, Chen J E, et al. Theor Comput Sci, 2014, 554: 207-216 CrossRef Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1