×

zbMATH — the first resource for mathematics

A quadratic kernel for computing the hybridization number of multiple trees. (English) Zbl 1287.68060
Summary: It has recently been shown that the NP-hard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixed-parameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixed-parameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel.

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
92C42 Systems biology, networks
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] Baroni, M.; Grünewald, S.; Moulton, V.; Semple, C., Bounding the number of hybridisation events for a consistent evolutionary history, J. Math. Biol., 51, 171-182, (2005) · Zbl 1068.92034
[3] Bonet, M. L.; St. John, K., On the complexity of uspr distance, IEEE/ACM Trans. Comput. Biol. Bioinf., 7, 3, 572-576, (2010)
[4] Bordewich, M.; Semple, C., On the computational complexity of the rooted subtree prune and regraft distance, Ann. Comb., 8, 4, 409-423, (2005) · Zbl 1059.05035
[5] Bordewich, M.; Semple, C., Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable, IEEE/ACM Trans. Comput. Biol. Bioinf., 4, 458-466, (2007)
[6] 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
[7] Chen, Z. Z.; Wang, L., Algorithms for reticulate networks of multiple phylogenetic trees, IEEE/ACM Trans. Comput. Biol. Bioinf., 9, 2, 1545-5963, (2012)
[8] Chen, Z. Z.; Wang, L., An ultrafast tool for minimum reticulate networks, J. Comput. Biol., 20, 1, 38-41, (2013)
[9] Collins, J.; Linz, S.; Semple, C., Quantifying hybridization in realistic time, J. Comput. Biol., 18, 1305-1318, (2011)
[10] van Iersel, L. J.J.; Kelk, S. M., When two trees go to war, J. Theor. Biol., 269, 1, 245-255, (2011) · Zbl 1307.92304
[11] Kanj, I. A.; Nakhleh, L.; Than, C.; Xia, G., Seeing the trees and their branches in the network is hard, Theor. Comput. Sci., 401, 153-164, (2008) · Zbl 1147.68059
[12] Kelk, S.; van Iersel, L.; Lekic, 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
[13] Kelk, S. M.; Scornavacca, C.; van Iersel, L. J.J., On the elusiveness of clusters, IEEE/ACM Trans. Comput. Biol. Bioinf., 9, 2, 517-534, (2012)
[14] S. Linz, Reticulation in evolution, PhD thesis, Heinrich-Heine Universität, Düsseldorf, Germany, 2008.
[15] Linz, S.; Semple, C., Hybridization in nonbinary trees, IEEE/ACM Trans. Comput. Biol. Bioinf., 6, 1, 30-45, (2009)
[16] Whidden, C.; Beiko, R. G.; Zeh, N., Fixed-parameter and approximation algorithms for maximum agreement forests, (2011) · Zbl 1311.68079
[17] Wu, Y., Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees, Proceedings of Intelligent Systems for Molecular Biology, 2010 (ISMB2010), 10th-13th September, 2010, Bioinformatics, 26, i140-i148, (2010), (special issue)
[18] Y. Wu, W. Jiayin, Fast computation of the exact hybridization number of two phylogenetic trees, in: Bioinformatics Research and Applications (ISBRA), vol. 6053, 2010, pp. 203-214.
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.