×

zbMATH — the first resource for mathematics

A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees. (English) Zbl 1400.92379
Summary: The Maximum Agreement Forest problem has been extensively studied in phylogenetics. Most previous work is on two binary phylogenetic trees. In this paper, we study a generalized version of the problem: the Maximum Agreement Forest problem on multiple rooted multifurcating phylogenetic trees, from the perspective of parameterized algorithms. By taking advantage of a new branch-and-bound strategy, a parameterized algorithm with running time \(O(2.42^k m^3 n^4)\) is presented for the problem, assuming that all polytomies in the multifurcating phylogenetic trees are hard.

MSC:
92D15 Problems related to evolution
05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
Software:
rSPR; SPRSupertrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Robinson, D.; Foulds, L., Comparison of phylogenetic trees, Math. Biosci., 53, 1-2, 131-147, (1981) · Zbl 0451.92006
[2] Li, M.; Tromp, J.; Zhang, L., On the nearest neighbour interchange distance between evolutionary trees, J. Theor. Biol., 182, 4, 463-467, (1996)
[3] Baroni, M.; Grunewald, S.; Moulton, V.; Semple, C., Bounding the number of hybridisation events for a consistent evolutionary history, J. Math. Biol., 51, 2, 171-182, (2005) · Zbl 1068.92034
[4] Buneman, P., The recovery of trees from measures of dissimilarity, (Kendall, D.; Tautu, P., Mathematics in the Archeological and Historical Sciences, (1971), Edinburgh University Press), 387-395
[5] Swofford, D. L.; Olsen, G. J.; Waddell, P. J.; Hillis, D. M., Phylogenetic inference, (Hillis, E.; Moritz, C.; Mable, B., Molecular Systematics, (1996)), 407-514
[6] Dudas, G.; Bedford, T.; Lycett, S.; Rambaut, A., Reassortment between influenza B lineages and the emergence of a coadapted PB1-PB2-HA gene complex, Mol. Biol. Evol., 32, 1, 162-172, (2014)
[7] Beiko, R. G.; Hamilton, N., Phylogenetic identification of lateral genetic transfer events, BMC Evol. Biol., 6, 1, 15, (2006)
[8] Whidden, C.; Zeh, N.; Beiko, R., Supertrees based on the subtree prune-and-regraft distance, Syst. Biol., 63, 4, 566-581, (2014)
[9] Whidden, C.; Frederick, A.; Matsen, I., Quantifying MCMC exploration of phylogenetic tree space, Syst. Biol., 64, 3, 472, (2015)
[10] Allen, B.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb., 5, 1, 1-15, (2001) · Zbl 0978.05023
[11] Bordewich, M.; McCartin, C.; Semple, C., A 3-approximation algorithm for the subtree distance between phylogenies, J. Discret. Algorithms, 6, 3, 458-471, (2008) · Zbl 1171.05317
[12] Hein, J.; Jiang, T.; Wang, L.; Zhang, K., On the complexity of comparing evolutionary trees, Discrete Appl. Math., 71, 153-169, (1996) · Zbl 0876.92020
[13] 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
[14] Felsenstein, J., Phylogenies and the comparative method, Am. Nat., 1-15, (1985)
[15] Grafen, A., The phylogenetic regression, Philos. Trans. R. Soc. Lond. B, Biol. Sci., 326, 1233, 119-157, (1989)
[16] Fehrer, J.; Gemeinholzer, B.; Chrtek, J.; Bräutigam, S., Incongruent plastid and nuclear DNA phylogenies reveal ancient intergeneric hybridization in pilosella hawkweeds (hieracium, cichorieae, asteraceae), Mol. Phylogenet. Evol., 42, 2, 347-361, (2007)
[17] Paun, O.; Lehnebach, C.; Johansson, J. T.; Lockhart, P.; Hörandl, E., Phylogenetic relationships and biogeography of ranunculus and allied genera (ranunculaceae) in the mediterranean region and in the European alpine system, Taxon, 54, 4, 911-932, (2005)
[18] Maddison, W., Reconstructing character evolution on polytomous cladograms, Cladistics, 5, 4, 365-377, (1989)
[19] Coyne, J. A.; Elwyn, S.; Kim, S. Y.; Llopart, A., Genetic studies of two sister species in the drosophila melanogaster subgroup, D. yakuba and D. santomea, Genet. Res., 84, 01, 11-26, (2004)
[20] Kliman, R. M.; Andolfatto, P.; Coyne, J. A.; Depaulis, F.; Kreitman, M.; Berry, A. J.; McCarter, J.; Wakeley, J.; Hey, J., The population genetics of the origin and divergence of the drosophila simulans complex species, Genetics, 156, 4, 1913-1931, (2000)
[21] Takahashi, K.; Terai, Y.; Nishida, M.; Okada, N., Phylogenetic relationships and ancient incomplete lineage sorting among cichlid fishes in lake tanganyika as revealed by analysis of the insertion of retroposons, Mol. Biol. Evol., 18, 11, 2057-2066, (2001)
[22] Whidden, C.; Beiko, R. G.; Zeh, N., Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees, Algorithmica, 74, 3, 1019-1054, (2016) · Zbl 1333.68297
[23] Chen, J.; Fan, J.-H.; Sze, S.-H., Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees, Theor. Comput. Sci., 562, 496-512, (2015) · Zbl 1303.68154
[24] Chen, Z.-Z.; Wang, L., Algorithms for reticulate networks of multiple phylogenetic trees, IEEE/ACM Trans. Comput. Biol. Bioinform., 9, 2, 372-384, (2012)
[25] 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
[26] Rodrigues, E. M.; Sagot, M.-F.; Wakabayashi, Y., Some approximation results for the maximum agreement forest problem, (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, (2001), Springer), 159-169 · Zbl 1001.92038
[27] Bonet, M. L.; John, K. S.; Mahindru, R.; Amenta, N., Approximating subtree distances between phylogenies, J. Comput. Biol., 13, 8, 1419-1434, (2006)
[28] Rodrigues, E. M.; Sagot, M.-F.; Wakabayashi, Y., The maximum agreement forest problem: approximation algorithms and computational experiments, Theor. Comput. Sci., 374, 1, 91-110, (2007) · Zbl 1164.68039
[29] Whidden, C.; Zeh, N., A unifying view on approximation and FPT of agreement forests, Algorithms Bioinf., 5724, 390-401, (2009)
[30] Shi, F.; Feng, Q.; You, J.; Wang, J., Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees, J. Comb. Optim., 32, 1, 111-143, (2016) · Zbl 1378.90085
[31] Schalekamp, F.; Zuylen, A. V.; Ster, S. V.D., A duality based 2-approximation algorithm for maximum agreement forest, (43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, (2016), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik), 70:1-70:14 · Zbl 1388.68312
[32] Chen, Z.-Z.; Machida, E.; Wang, L., An improved approximation algorithm for rspr distance, (International Computing and Combinatorics Conference, (2016), Springer), 468-479 · Zbl 06622052
[33] Chen, Z.-Z.; Harada, Y.; Wang, L., A new 2-approximation algorithm for rspr distance, (International Symposium on Bioinformatics Research and Applications, (2017), Springer), 128-139
[34] Van Iersel, L.; Kelk, S.; Lekic, N.; Stougie, L., Approximation algorithms for nonbinary agreement forests, SIAM J. Discrete Math., 28, 1, 49-66, (2014) · Zbl 1311.68193
[35] Chataigner, F., Approximating the maximum agreement forest on k trees, Inf. Process. Lett., 93, 5, 239-244, (2005) · Zbl 1173.68601
[36] Mukhopadhyay, A.; Bhabak, P., A 3-factor approximation algorithm for a minimum acyclic agreement forest on k rooted, binary phylogenetic trees, arXiv preprint
[37] Chen, J.; Shi, F.; Wang, J., Approximating maximum agreement forest on multiple binary trees, Algorithmica, 1-23, (2015)
[38] Downey, R. G.; Fellows, M. R., Parameterized complexity, (1999), Springer New York, U.S. · Zbl 0914.68076
[39] Hallett, M.; McCartin, C., A faster FPT algorithm for the maximum agreement forest problem, Theory Comput. Syst., 41, 3, 539-550, (2007) · Zbl 1148.68049
[40] 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
[41] Chen, Z.-Z.; Fan, Y.; Wang, L., Faster exact computation of rspr distance, J. Comb. Optim., 29, 3, 605-635, (2013) · Zbl 1322.90103
[42] Shi, F.; Wang, J.; Yang, Y.; Feng, Q.; Li, W.; Chen, J., A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees, Sci. China Inf. Sci., 59, 1, 1-14, (2016)
[43] Shi, F.; Wang, J.; Chen, J.; Feng, Q.; Guo, J., Algorithms for parameterized maximum agreement forest problem on multiple trees, Theor. Comput. Sci., 554, 207-216, (2014) · Zbl 1382.68181
[44] Chen, J.; Kanj, I. A.; Jia, W., Vertex cover: further observations and further improvements, J. Algorithms, 41, 280-301, (2001) · Zbl 1017.68087
[45] Shi, F.; Chen, J.; Feng, Q.; Wang, J., Parameterized algorithms for the maximum agreement forest problem on multiple rooted multifurcating trees, arXiv preprint
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.