×

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
PDFBibTeX XMLCite
Full Text: DOI arXiv

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(3), 458-466 (2007) · doi:10.1109/tcbb.2007.1019
[2] 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 · doi:10.1016/j.dam.2006.08.008
[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) · doi:10.1109/TCBB.2011.137
[5] Collins, J., Linz, S., Semple, C.: Quantifying hybridization in realistic time. J. Comput. Biol. 18(10), 1305-1318 (2011) · doi:10.1089/cmb.2009.0166
[6] Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999) · Zbl 0961.68533 · doi:10.1007/978-1-4612-0515-9
[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 · doi:10.1007/978-3-642-02441-2_26
[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(1), 79-101 (2008) · doi:10.1093/comjnl/bxm049
[12] Gusfield, D., Bansal, V., Bafna, V., Song, Y.: A decomposition theory for phylogenetic networks and incompatible characters. J. Comput. Biol. 14(10), 1247-1272 (2007) · doi:10.1089/cmb.2006.0137
[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(6-7), 806-830 (2007) · Zbl 1259.92077 · doi:10.1016/j.dam.2005.05.044
[14] Huson, D.H., Scornavacca, C.: A survey of combinatorial methods for phylogenetic networks. Genome Biol. Evol. 3, 23-35 (2011) · doi:10.1093/gbe/evq077
[15] Huson, D.H., Rupp, R., Berry, V., Gambette, P., Paul, C.: Computing galled networks from real data. Bioinformatics 25(12), i85-i93 (2009) · doi:10.1093/bioinformatics/btp217
[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 · doi:10.1007/11415770_20
[18] Jansson, J., Sung, W.-K.: Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theor. Comput. Sci. 363(1), 60-68 (2006) · Zbl 1110.68032 · doi:10.1016/j.tcs.2006.06.022
[19] 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 · doi:10.1137/S0097539704446529
[20] Kelk, S., Scornavacca, C., van Iersel, L.: On the elusiveness of clusters. IEEE/ACM Trans. Comput. Biol. Bioinform. 9, 517-534 (2012) · doi:10.1109/TCBB.2011.128
[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 · doi:10.1093/acprof:oso/9780198566076.001.0001
[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] van Iersel, L., Kelk, S.: Constructing the simplest possible phylogenetic network from triplets. Algorithmica 60, 207-235 (2011) · Zbl 1215.92052 · doi:10.1007/s00453-009-9333-0
[28] 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 · doi:10.1016/j.jtbi.2010.10.032
[29] van 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(4), 667-681 (2009) · doi:10.1109/TCBB.2009.22
[30] van 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(2), 597-623 (2009) · doi:10.1142/S0219720009004308
[31] van 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). Special issue: Proceedings of Intelligent Systems for Molecular Biology 2010 (ISMB2010), 10th-13th September (2010) · doi:10.1093/bioinformatics/btq202
[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 · doi:10.1007/978-3-642-04241-6_32
[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). Special issue: Proceedings of Intelligent Systems for Molecular Biology 2010 (ISMB2010), 10th-13th September (2010) · doi:10.1093/bioinformatics/btq198
[35] Wu, Y., Gusfield, D.: A new recombination lower bound and the minimum perfect phylogenetic forest problem. J. Comb. Optim. 16(3), 229-247 (2008) · Zbl 1260.92094 · doi:10.1007/s10878-007-9129-6
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.