Abstract
Reticulate events play an important role in determining evolutionary relationships. The problem of computing the minimum number of such events to explain discordance between two phylogenetic trees is a hard computational problem. In practice, exact solvers struggle to solve instances with reticulation number larger than 40. For such instances, one has to resort to heuristics and approximation algorithms. Here we present the algorithm CycleKiller which is the first approximation algorithm that can produce solutions verifiably close to optimality for instances with hundreds or even thousands of reticulations. Theoretically, the algorithm is an exponential-time 2-approximation (or 4-approximation in its fastest mode). However, using simulations we demonstrate that in practice the algorithm runs quickly for large and difficult instances, producing solutions within one percent of optimality. An implementation of this algorithm, which extends the theoretical work of [14], has been made publicly available.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Albrecht, B., Scornavacca, C., Cenci, A., Huson, D.H.: Fast computation of minimum hybridization networks. Bioinformatics 28(2), 191–197 (2012)
Baroni, M., Grünewald, S., Moulton, V., Semple, C.: Bounding the number of hybridisation events for a consistent evolutionary history. Mathematical Biology 51, 171–182 (2005)
Bordewich, M., Linz, S., St. John, K., Semple, C.: A reduction algorithm for computing the hybridization number of two trees. Evolutionary Bioinformatics 3, 86–98 (2007)
Bordewich, M., Semple, C.: Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Applied Mathematics 155(8), 914–928 (2007)
Chen, Z.-Z., Wang, L.: Hybridnet: a tool for constructing hybridization networks. Bioinformatics 26(22), 2912–2913 (2010)
Chen, Z.-Z., Wang, L.: Algorithms for reticulate networks of multiple phylogenetic trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics 9(2), 372–384 (2012)
Collins, J., Linz, S., Semple, C.: Quantifying hybridization in realistic time. Journal of Computational Biology 18, 1305–1318 (2011)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)
Gascuel, O. (ed.): Mathematics of Evolution and Phylogeny. Oxford University Press, Inc. (2005)
Gascuel, O., Steel, M. (eds.): Reconstructing Evolution: New Mathematical and Computational Advances. Oxford University Press, USA (2007)
Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press (2011)
Huson, D.H., Scornavacca, C.: Dendroscope 3 - a program for computing and drawing rooted phylogenetic trees and networks (2011) (in preparation), Software, http://www.dendroscope.org
Huson, D.H., Scornavacca, C.: A survey of combinatorial methods for phylogenetic networks. Genome Biology and Evolution 3, 23–35 (2011)
Kelk, S.M., van Iersel, L.J.J., 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. Submitted, preliminary version arXiv:1112.5359v1 (math.CO)
Nakhleh, L.: Evolutionary phylogenetic networks: models and issues. In: The Problem Solving Handbook for Computational Biology and Bioinformatics. Springer (2009)
Rodrigues, E.M., Sagot, M.F., Wakabayashi, Y.: The maximum agreement forest problem: Approximation algorithms and computational experiments. Theoretical Computer Science 374(1-3), 91–110 (2007)
Whidden, C.: http://kiwi.cs.dal.ca/Software/RSPR
Whidden, C., Beiko, R.G., Zeh, N.: Fixed-parameter and approximation algorithms for maximum agreement forests. Submitted, preliminary version arXiv:1108.2664v1 (q-bio.PE)
Whidden, C., Beiko, R.G., Zeh, N.: Fast FPT Algorithms for Computing Rooted Agreement Forests: Theory and Experiments. In: Festa, P. (ed.) SEA 2010. LNCS, vol. 6049, pp. 141–153. Springer, Heidelberg (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Iersel, L., Kelk, S., Lekić, N., Scornavacca, C. (2012). A Practical Approximation Algorithm for Solving Massive Instances of Hybridization Number. In: Raphael, B., Tang, J. (eds) Algorithms in Bioinformatics. WABI 2012. Lecture Notes in Computer Science(), vol 7534. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33122-0_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-33122-0_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33121-3
Online ISBN: 978-3-642-33122-0
eBook Packages: Computer ScienceComputer Science (R0)