×

zbMATH — the first resource for mathematics

Hybridization number on three rooted binary trees is EPT. (English) Zbl 1345.92101

MSC:
92D15 Problems related to evolution
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Bapteste, L. van Iersel, A. Janke, S. Kelchner, S. Kelk, J. O. McInerney, D. A. Morrison, L. Nakhleh, M. Steel, L. Stougie, and J. Whitfield, Networks: Expanding evolutionary thinking, Trends in Genetics, 29 (2013), pp. 439–441.
[2] M. Baroni, C. Semple, and M. Steel, A framework for representing reticulate evolution, Ann. Comb., 8 (2004), pp. 391–408. · Zbl 1059.05034
[3] M. Baroni, S. Grünewald, V. Moulton, and C. Semple, Bounding the number of hybridisation events for a consistent evolutionary history, Math. Biol., 51 (2005), pp. 171–182. · Zbl 1068.92034
[4] M. Bordewich and C. Semple, Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable, IEEE/ACM Trans. Comput. Biol. Bioinform., 4 (2007), pp. 458–466.
[5] M. Bordewich and C. Semple, Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Appl. Math., 155 (2007), pp. 914–928. · Zbl 1111.92041
[6] Z.-Z. Chen and L. Wang, An ultrafast tool for minimum reticulate networks, J. Comput. Biol., 20 (2013), pp. 38–41.
[7] R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, New York, 1999.
[8] J. Flum, M. Grohe, and M. Weyer, Bounded fixed-parameter tractability and nondeterministic bits, J. Comput. Syst. Sci., 72 (2006), pp. 34–71. · Zbl 1110.68050
[9] O. Gascuel and M. Steel, eds., Reconstructing Evolution: New Mathematical and Computational Advances, Oxford University Press, Oxford, 2007.
[10] D. H. Huson, R. Rupp, and C. Scornavacca, Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press, Cambridge, 2011.
[11] L. van Iersel and S. Kelk, Kernelizations for the hybridization number problem on multiple nonbinary trees, in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 8747, 2014, pp. 299–311. · Zbl 1342.68169
[12] L. van Iersel, S. Kelk, N. Lekić, and L. Stougie, Approximation algorithms for nonbinary agreement forests, SIAM J. Discrete Math., 28 (2014), pp. 49–66. · Zbl 1311.68193
[13] L. van Iersel and S. Linz, A quadratic kernel for computing the hybridization number of multiple trees, Inform. Process. Lett., 113 (2013), pp. 318–323. · Zbl 1287.68060
[14] S. Kelk and C. Scornavacca, Towards the Fixed Parameter Tractability of Constructing Minimal Phylogenetic Networks from Arbitrary Sets of Nonbinary Trees, arXiv:1207.7034, 2012.
[15] S. Kelk and C. Scornavacca, Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Algorithmica, 68 (2014), pp. 886–915. · Zbl 1350.92036
[16] S. Kelk, C. Scornavacca, and L. van Iersel, On the elusiveness of clusters, IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (2012), pp. 517–534.
[17] S. Kelk, L. van Iersel, N. Lekić, S. Linz, C. Scornavacca, and L. Stougie, Cycle killer... qu’est-ce que c’est? On the comparative approximability of hybridization number and directed feedback vertex set, SIAM J. Discrete Math., 26 (2012), pp. 1635–1656. · Zbl 1263.68174
[18] S. Linz and C. Semple, Hybridization in non-binary trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 6 (2009), pp. 30–45.
[19] D. Morrison, Introduction to Phylogenetic Networks, RJR Productions, Uppsala, 2011.
[20] R. Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford Lecture Ser. Math. Appl., Oxford University Press, Oxford, 2006. · Zbl 1095.68038
[21] T. Piovesan and S. Kelk, A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 10 (2013), pp. 18–25.
[22] C. Semple and M. Steel, A supertree method for rooted trees, Discrete Appl. Math., 105 (2000), pp. 147–158. · Zbl 0961.05015
[23] C. Whidden, R. G. Beiko, and N. Zeh, Fixed-parameter algorithms for maximum agreement forests, SIAM J. Comput., 42 (2013), pp. 1431–1466. · Zbl 1311.68079
[24] Y. Wu, An algorithm for constructing parsimonious hybridization networks with multiple phylogenetic trees, J. Comput. Biol., 20 (2013), pp. 792–804.
[25] Y. Yu, R. M. Barnett, and L. Nakhleh, Parsimonious inference of hybridization in the presence of incomplete lineage sorting, Syst. Biol., 62 (2013), pp. 738–751.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.