×

zbMATH — the first resource for mathematics

Kernelizations for the hybridization number problem on multiple nonbinary trees. (English) Zbl 1342.68170
Summary: Given a finite set \(X\), a collection \(\mathcal{T}\) of rooted phylogenetic trees on \(X\) and an integer \(k\), the Hybridization Number problem asks if there exists a phylogenetic network on \(X\) that displays all trees from \(\mathcal{T}\) and has reticulation number at most \(k\). We show two kernelization algorithms for Hybridization Number, with kernel sizes \(4 k(5 k)^t\) and \(20 k^2({\Delta}^+ - 1)\) respectively, with \(t\) the number of input trees and \({\Delta}^+\) their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an \(n^{f(k)} t\)-time algorithm, with \(n = | X |\) and \(f\) some computable function of \(k\).

MSC:
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
92D15 Problems related to evolution
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albrecht, B.; Scornavacca, C.; Cenci, A.; Huson, D. H., Fast computation of minimum hybridization networks, Bioinformatics, 28, 2, 191-197, (2012)
[2] Bapteste, E.; van Iersel, L.; Janke, A.; Kelchner, S.; Kelk, S.; McInerney, J. O.; Morrison, D. A.; Nakhleh, L.; Steel, M.; Stougie, L.; Whitfield, J., Networks: expanding evolutionary thinking, Trends Genet., 29, 8, 439-441, (2013)
[3] Baroni, M.; Grünewald, S.; Moulton, V.; Semple, C., Bounding the number of hybridisation events for a consistent evolutionary history, Math. Biol., 51, 171-182, (2005) · Zbl 1068.92034
[4] Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hermelin, D., On problems without polynomial kernels, J. Comput. Syst. Sci., 75, 8, 423-434, (2009) · Zbl 1192.68288
[5] Bordewich, M.; Semple, C., Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Appl. Math., 155, 8, 914-928, (2007) · Zbl 1111.92041
[6] Bordewich, M.; Semple, C., Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable, IEEE/ACM Trans. Comput. Biol. Bioinform., 4, 3, 458-466, (2007)
[7] Chen, Z.-Z.; Wang, L., Algorithms for reticulate networks of multiple phylogenetic trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 2, 372-384, (2012)
[8] Chen, Z.-Z.; Wang, L., An ultrafast tool for minimum reticulate networks, J. Comput. Biol., 20, 1, 38-41, (2013)
[9] Downey, R. G.; Fellows, M. R., Parameterized complexity, (1999), Springer-Verlag · Zbl 0914.68076
[10] Hein, J., Reconstructing evolution of sequences subject to recombination using parsimony, Math. Biosci., 98, 2, 185-200, (1990) · Zbl 0692.92014
[11] Huson, D. H.; Rupp, R.; Scornavacca, C., Phylogenetic networks: concepts, algorithms and applications, (2011), Cambridge University Press
[12] van Iersel, L., Algorithms, haplotypes and phylogenetic networks, (2009), PhD thesis
[13] van Iersel, L.; Kelk, S.; Lekić, N.; Stougie, L., Approximation algorithms for nonbinary agreement forests, SIAM J. Discrete Math., 28, 1, 49-66, (2014) · Zbl 1311.68193
[14] van Iersel, L.; Kelk, S.; Lekić, N.; Whidden, C.; Zeh, N., Hybridization number on three trees, (2014)
[15] van Iersel, L.; Linz, S., A quadratic kernel for computing the hybridization number of multiple trees, Inf. Process. Lett., 113, 9, 318-323, (2013) · Zbl 1287.68060
[16] Jansson, J.; Nguyen, N. B.; Sung, W.-K., Algorithms for combining rooted triplets into a galled phylogenetic network, SIAM J. Comput., 35, 5, 1098-1121, (2006) · Zbl 1100.68081
[17] Kelk, S.; van Iersel, L.; Lekić, N.; Linz, S.; Scornavacca, C.; Stougie, L., 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, 4, 1635-1656, (2012) · Zbl 1263.68174
[18] Kelk, S.; Scornavacca, C., Towards the fixed parameter tractability of constructing minimal phylogenetic networks from arbitrary sets of nonbinary trees, (2012)
[19] Kelk, S.; Scornavacca, C., Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Algorithmica, 68, 886-915, (2014) · Zbl 1350.92036
[20] Linz, S.; Semple, C., Hybridization in non-binary trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 6, 1, 30-45, (2009)
[21] Maddison, W., Gene trees in species trees, Syst. Biol., 46, 3, 523-536, (1997)
[22] McDiarmid, C.; Semple, C.; Welsh, D., Counting phylogenetic networks, Ann. Comb., 19, 1, 205-224, (2015) · Zbl 1310.05120
[23] Morrison, D., Introduction to phylogenetic networks, (2011), RJR Productions Uppsala
[24] Nakhleh, L.; Ringe, D.; Warnow, T., Perfect phylogenetic networks: a new methodology for reconstructing the evolutionary history of natural languages, Language, 81, 2, 382-420, (2005)
[25] Piovesan, T.; Kelk, S., A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 10, 1, 18-25, (2013)
[26] Semple, C.; Steel, M., Phylogenetics, (2003), Oxford University Press · Zbl 1043.92026
[27] Song, Y. S.; Hein, J., Parsimonious reconstruction of sequence evolution and haplotyde blocks: finding the minimum number of recombination events, Algorithms Bioinform. (WABI 2003), 2812, 287-302, (2003)
[28] Whidden, C.; Beiko, R. G.; Zeh, N., Fixed-parameter algorithms for maximum agreement forests, SIAM J. Comput., 42, 4, 1431-1466, (2013) · Zbl 1311.68079
[29] Wu, Y., Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees, Bioinformatics, 26, i140-i148, (2010)
[30] Wu, Y., An algorithm for constructing parsimonious hybridization networks with multiple phylogenetic trees, J. Comput. Biol., 20, 10, 792-804, (2013)
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.