×

zbMATH — the first resource for mathematics

Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable. (English) Zbl 1350.92036
Summary: Here we show that, given a set of clusters \(\mathcal C\) on a set of taxa \(\mathcal X\), where \(|\mathcal X|=n\), it is possible to determine in time \(f(k)\cdot\mathrm{poly}(n)\) whether there exists a level-\(\leq k\) network (i.e. a network where each biconnected component has reticulation number at most \(k\)) that represents all the clusters in \(\mathcal C\) in the softwired sense, and if so to construct such a network. This extends a result from our paper with L. van Iersel [“On the elusiveness of clusters”, IEEE/ACM Trans. Comput. Biol. Bioinform. 9, No. 2, 517–534 (2012; doi:10.1109/TCBB.2011.128)] which showed that the problem is polynomial-time solvable for fixed \(k\). By defining “\(k\)-reticulation generators” analogous to “level-\(k\) generators”, we then extend this fixed parameter tractability result to the problem where \(k\) refers not to the level but to the reticulation number of the whole network.

MSC:
92D15 Problems related to evolution
05C05 Trees
68W05 Nonnumerical algorithms
68R10 Graph theory (including graph drawing) in computer science
Software:
rSPR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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)
[2] Bordewich, M.; Semple, C., Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Appl. Math., 155, 914-928, (2007) · Zbl 1111.92041
[3] Bordewich, M.; Linz, S.; John, K.St.; Semple, C., A reduction algorithm for computing the hybridization number of two trees, Evol. Bioinform., 3, 86-98, (2007)
[4] Chen, Z.-Z.; Wang, L., Algorithms for reticulate networks of multiple phylogenetic trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 372-384, (2012)
[5] Collins, J.; Linz, S.; Semple, C., Quantifying hybridization in realistic time, J. Comput. Biol., 18, 1305-1318, (2011)
[6] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)
[7] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
[8] Gambette, P.; Berry, V.; Paul, C., The structure of level-k phylogenetic networks, 289-300, (2009), Berlin · Zbl 1247.92018
[9] Gascuel, O. (ed.): Mathematics of Evolution and Phylogeny. Oxford University Press, Oxford (2005) · Zbl 1104.92332
[10] Gascuel, O., Steel, M. (eds.): Reconstructing Evolution: New Mathematical and Computational Advances. Oxford University Press, Oxford (2007) · Zbl 1116.92003
[11] Gramm, J.; Nickelsen, A.; Tantau, T., Fixed-parameter algorithms in phylogenetics, Comput. J., 51, 79-101, (2008)
[12] Gusfield, D.; Bansal, V.; Bafna, V.; Song, Y., A decomposition theory for phylogenetic networks and incompatible characters, J. Comput. Biol., 14, 1247-1272, (2007)
[13] Gusfield, D.; Hickerson, D.; Eddhu, S., An efficiently computed lower bound on the number of recombinations in phylognetic networks: theory and empirical study, Discrete Appl. Math., 155, 806-830, (2007) · Zbl 1259.92077
[14] Huson, D.H.; Scornavacca, C., A survey of combinatorial methods for phylogenetic networks, Genome Biol. Evol., 3, 23-35, (2011)
[15] Huson, D.H.; Rupp, R.; Berry, V.; Gambette, P.; Paul, C., Computing galled networks from real data, Bioinformatics, 25, i85-i93, (2009)
[16] Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, Cambridge (2011)
[17] Huynh, T.N.D.; Jansson, J.; Nguyen, N.B.; Sung, W.-K., Constructing a smallest refining galled phylogenetic network, No. 3500, 265-280, (2005) · Zbl 1119.92354
[18] Jansson, J.; Sung, W.-K., Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Theor. Comput. Sci., 363, 60-68, (2006) · Zbl 1110.68032
[19] Jansson, J.; Nguyen, N.B.; Sung, W.-K., Algorithms for combining rooted triplets into a galled phylogenetic network, SIAM J. Comput., 35, 1098-1121, (2006) · Zbl 1100.68081
[20] Kelk, S.; Scornavacca, C.; Iersel, L., On the elusiveness of clusters, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 517-534, (2012)
[21] Myers, S.R.; Griffiths, R.C., Bounds on the minimum number of recombination events in a sample history, Genetics, 163, 375-394, (2003)
[22] Nakhleh, L., Evolutionary phylogenetic networks: models and issues, (2009), Berlin
[23] Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006) · Zbl 1095.68038
[24] Semple, C., Hybridization networks, (2007), Oxford
[25] Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003) · Zbl 1043.92026
[26] To, T.-H.; Habib, M., Level-\(k\) phylogenetic networks are constructable from a dense triplet set in polynomial time, No. 5577, 275-288, (2009) · Zbl 1247.92019
[27] Iersel, L.; Kelk, S., Constructing the simplest possible phylogenetic network from triplets, Algorithmica, 60, 207-235, (2011) · Zbl 1215.92052
[28] Iersel, L.J.J.; Kelk, S.M., When two trees go to war, J. Theor. Biol., 269, 245-255, (2011) · Zbl 1307.92304
[29] Iersel, L.J.J.; Keijsper, J.C.M.; Kelk, S.M.; Stougie, L.; Hagen, F.; Boekhout, T., Constructing level-2 phylogenetic networks from triplets, IEEE/ACM Trans. Comput. Biol. Bioinform., 6, 667-681, (2009)
[30] Iersel, L.J.J.; Kelk, S.M.; Mnich, M., Uniqueness, intractability and exact algorithms: reflections on level-\(k\) phylogenetic networks, J. Bioinform. Comput. Biol., 7, 597-623, (2009)
[31] Iersel, L.J.J.; Kelk, S.M.; Rupp, R.; Huson, D.H., Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters, Bioinformatics, 26, i124-i131, (2010)
[32] Whidden, C.; Zeh, N.; Salzberg, S. (ed.); Warnow, T. (ed.), A unifying view on approximation and fpt of agreement forests, No. 5724, 390-402, (2009), Berlin
[33] Whidden, C., Beiko, R.G., Zeh, N.: Fixed-parameter and approximation algorithms for maximum agreement forests. arXiv:1108.2664v1 [q-bio.PE] · Zbl 1311.68079
[34] Wu, Y., Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees, Bioinformatics, 26, i140-i148, (2010)
[35] Wu, Y.; Gusfield, D., A new recombination lower bound and the minimum perfect phylogenetic forest problem, J. Comb. Optim., 16, 229-247, (2008) · Zbl 1260.92094
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.