{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T18:50:11Z","timestamp":1779907811750,"version":"3.53.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T00:00:00Z","timestamp":1637280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Phylogenetic trees are leaf-labelled trees used to model the evolution of species. Here we explore the practical impact of kernelization (i.e. data reduction) on the NP-hard problem of computing the TBR distance between two unrooted binary phylogenetic trees. This problem is better-known in the literature as the maximum agreement forest problem, where the goal is to partition the two trees into a minimum number of common, non-overlapping subtrees. We have implemented two well-known reduction rules, the subtree and chain reduction, and five more recent, theoretically stronger reduction rules, and compare the reduction achieved with and without the stronger rules. We find that the new rules yield smaller reduced instances and thus have clear practical added value. In many cases they also cause the TBR distance to decrease in a controlled fashion, which can further facilitate solving the problem in practice. Next, we compare the achieved reduction to the known worst-case theoretical bounds of<jats:inline-formula><jats:alternatives><jats:tex-math>$$15k-9$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>15<\/mml:mn><mml:mi>k<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>9<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:tex-math>$$11k-9$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>11<\/mml:mn><mml:mi>k<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>9<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>respectively, on the number of leaves of the two reduced trees, where<jats:italic>k<\/jats:italic>is the TBR distance, observing in both cases a far larger reduction in practice. As a by-product of our experimental framework we obtain a number of new insights into the actual computation of TBR distance. We find, for example, that very strong lower bounds on TBR distance can be obtained efficiently by randomly sampling certain carefully constructed partitions of the leaf labels, and identify instances which seem particularly challenging to solve exactly. The reduction rules have been implemented within our new solver<jats:italic>Tubro<\/jats:italic>which combines kernelization with an Integer Linear Programming (ILP) approach. Tubro also incorporates a number of additional features, such as a cluster reduction and a practical upper-bounding heuristic, and it can leverage combinatorial insights emerging from the proofs of correctness of the reduction rules to simplify the ILP.<\/jats:p>","DOI":"10.1007\/s10479-021-04352-1","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T07:03:05Z","timestamp":1637305385000},"page":"425-451","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Reflections on kernelizing and computing unrooted agreement forests"],"prefix":"10.1007","volume":"309","author":[{"given":"Rim","family":"van Wersch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simone","family":"Linz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7248-8197","authenticated-orcid":false,"given":"Georgios","family":"Stamoulis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,11,19]]},"reference":[{"issue":"1","key":"4352_CR1","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10479-006-0045-4","volume":"146","author":"J Alber","year":"2006","unstructured":"Alber, J., Betzler, N., & Niedermeier, R. (2006). Experiments on data reduction for optimal domination in networks. Annals of Operations Research, 146(1), 105\u2013117.","journal-title":"Annals of Operations Research"},{"key":"4352_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"B Allen","year":"2001","unstructured":"Allen, B., & Steel, M. (2001). Subtree transfer operations and their induced metrics on evolutionary trees. Annals of Combinatorics, 5, 1\u201315.","journal-title":"Annals of Combinatorics"},{"issue":"1","key":"4352_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-018-0410-4","volume":"23","author":"R Atkins","year":"2019","unstructured":"Atkins, R., & McDiarmid, C. (2019). Extremal distances for subtree transfer operations in binary trees. Annals of Combinatorics, 23(1), 1\u201326.","journal-title":"Annals of Combinatorics"},{"issue":"1\u20132","key":"4352_CR4","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00285-016-1023-3","volume":"74","author":"M Bordewich","year":"2017","unstructured":"Bordewich, M., Scornavacca, C., Tokac, N., & Weller, M. (2017). On the fixed parameter tractability of agreement-based phylogenetic distances. Journal of Mathematical Biology, 74(1\u20132), 239\u2013257.","journal-title":"Journal of Mathematical Biology"},{"key":"4352_CR5","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1016\/j.tcs.2014.10.031","volume":"562","author":"J Chen","year":"2015","unstructured":"Chen, J., Fan, J.-H., & Sze, S.-H. (2015). Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees. Theoretical Computer Science, 562, 496\u2013512.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4352_CR6","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V. (1979). A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3), 233\u2013235.","journal-title":"Mathematics of Operations Research"},{"key":"4352_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms (1st ed.). Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"4352_CR8","doi-asserted-by":"crossref","unstructured":"Downey, R., & Fellows, M. (2013). Fundamentals of parameterized complexity (Vol. 4). Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"4352_CR9","doi-asserted-by":"publisher","unstructured":"Fellows, M., Jaffke, L., Kir\u00e1ly, A.I., Rosamond, F., & Weller, M. (2018). What is known about vertex cover kernelization? In H. J. B\u00f6ckenhauer, D. Komm, & W. Unger (Eds.), Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated (pp.330\u2013356). Cham: Springer International Publishing. https:\/\/doi.org\/10.1007\/978-3-319-98355-4_19.","DOI":"10.1007\/978-3-319-98355-4_19"},{"key":"4352_CR10","unstructured":"Felsenstein, J. (2004). Inferring phylogenies. Sinauer Associates."},{"key":"4352_CR11","doi-asserted-by":"crossref","unstructured":"Ferizovic, D., Hespe, D., Lamm, S., Mnich, M., Schulz, C., & Strash, D. (2020). Engineering kernelization for maximum cut. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 27\u201341). SIAM.","DOI":"10.1137\/1.9781611976007.3"},{"issue":"1","key":"4352_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00026-015-0298-1","volume":"20","author":"M Fischer","year":"2016","unstructured":"Fischer, M., & Kelk, S. (2016). On the maximum parsimony distance between phylogenetic trees. Annals of Combinatorics, 20(1), 87\u2013113.","journal-title":"Annals of Combinatorics"},{"issue":"4","key":"4352_CR13","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch, W. M. (1971). Toward defining the course of evolution: Minimum change for a specific tree topology. Systematic Biology, 20(4), 406\u2013416.","journal-title":"Systematic Biology"},{"key":"4352_CR14","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., & Zehavi, M. (2019). Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press.","DOI":"10.1017\/9781107415157"},{"key":"4352_CR15","doi-asserted-by":"crossref","unstructured":"Harding, E. (1971). The probabilities of rooted tree-shapes generated by random bifurcation. Advances in Applied Probability, 3(1), 44\u201377.","DOI":"10.2307\/1426329"},{"issue":"1\u20133","key":"4352_CR16","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0166-218X(96)00062-5","volume":"71","author":"J Hein","year":"1996","unstructured":"Hein, J., Jiang, T., Wang, L., & Zhang, K. (1996). On the complexity of comparing evolutionary trees. Discrete Applied Mathematics, 71(1\u20133), 153\u2013169.","journal-title":"Discrete Applied Mathematics"},{"key":"4352_CR17","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Noe, A., Schulz, C. (2020). Shared-memory branch-and-reduce for multiterminal cuts. In 2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 42\u201355). SIAM.","DOI":"10.1137\/1.9781611976007.4"},{"key":"4352_CR18","doi-asserted-by":"publisher","first-page":"EBO-S419","DOI":"10.4137\/EBO.S419","volume":"4","author":"G Hickey","year":"2008","unstructured":"Hickey, G., Dehne, F., Rau-Chaplin, A., & Blouin, C. (2008). SPR distance computation for unrooted trees. Evolutionary Bioinformatics, 4, EBO-S419.","journal-title":"Evolutionary Bioinformatics"},{"key":"4352_CR19","unstructured":"Huson, D., Rupp, R., & Scornavacca, C. (2011). Phylogenetic networks: Concepts, algorithms and applications. Cambridge University Press."},{"issue":"4","key":"4352_CR20","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00026-017-0361-1","volume":"21","author":"S Kelk","year":"2017","unstructured":"Kelk, S., & Fischer, M. (2017). On the complexity of computing mp distance between binary phylogenetic trees. Annals of Combinatorics, 21(4), 573\u2013604.","journal-title":"Annals of Combinatorics"},{"key":"4352_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.07.010","volume":"646","author":"S Kelk","year":"2016","unstructured":"Kelk, S., Fischer, M., Moulton, V., & Wu, T. (2016). Reduction rules for the maximum parsimony distance on phylogenetic trees. Theoretical Computer Science, 646, 1\u201315.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4352_CR22","doi-asserted-by":"publisher","first-page":"1556","DOI":"10.1137\/18M122724X","volume":"33","author":"S Kelk","year":"2019","unstructured":"Kelk, S., & Linz, S. (2019). A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees. SIAM Journal on Discrete Mathematics, 33(3), 1556\u20131574.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"4352_CR23","doi-asserted-by":"crossref","unstructured":"Kelk, S., & Linz, S. (2020). New reduction rules for the tree bisection and reconnection distance. Annals of Combinatorics, 24(3), 475\u2013502.","DOI":"10.1007\/s00026-020-00502-7"},{"key":"4352_CR24","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.aam.2016.10.003","volume":"84","author":"S Kelk","year":"2017","unstructured":"Kelk, S., & Stamoulis, G. (2017). A note on convex characters, fibonacci numbers and exponential-time algorithms. Advances in Applied Mathematics, 84, 34\u201346.","journal-title":"Advances in Applied Mathematics"},{"issue":"2","key":"4352_CR25","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1093\/sysbio\/syu085","volume":"64","author":"M Kuhner","year":"2015","unstructured":"Kuhner, M., & Yamato, J. (2015). Practical performance of tree comparison metrics. Systematic Biology, 64(2), 205\u2013214.","journal-title":"Systematic Biology"},{"key":"4352_CR26","unstructured":"Li, Z., Zeh, N. (2017). Computing maximum agreement forests without cluster partitioning is folly. In 25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"4352_CR27","unstructured":"LLC Gurobi\u00a0Optimization. (2020). Gurobi optimizer reference manual."},{"key":"4352_CR28","doi-asserted-by":"publisher","first-page":"3521","DOI":"10.1007\/s00453-020-00736-0","volume":"82","author":"G Mertzios","year":"2020","unstructured":"Mertzios, G., Nichterlein, A., & Niedermeier, R. (2020). The power of linear-time data reduction for maximum matching. Algorithmica, 82, 3521\u20133565.","journal-title":"Algorithmica"},{"key":"4352_CR29","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.aam.2015.02.002","volume":"66","author":"V Moulton","year":"2015","unstructured":"Moulton, V., & Wu, T. (2015). A parsimony-based metric for phylogenetic trees. Advances in Applied Mathematics, 66, 22\u201345.","journal-title":"Advances in Applied Mathematics"},{"issue":"5","key":"4352_CR30","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1093\/sysbio\/syy013","volume":"67","author":"E Richards","year":"2018","unstructured":"Richards, E., Brown, J., Barley, A., Chong, R., & Thomson, R. (2018). Variation across mitochondrial gene trees provides evidence for systematic error: How much gene tree variation is biological? Systematic Biology, 67(5), 847\u2013860.","journal-title":"Systematic Biology"},{"key":"4352_CR31","doi-asserted-by":"crossref","unstructured":"Semple, C., & Steel, M. (2003). Phylogenetics. Oxford University Press.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"issue":"1","key":"4352_CR32","first-page":"e83","volume":"66","author":"K St John","year":"2017","unstructured":"St John, K. (2017). The shape of phylogenetic treespace. Systematic Biology, 66(1), e83.","journal-title":"Systematic Biology"},{"issue":"6","key":"4352_CR33","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1016\/j.jcss.2016.03.006","volume":"82","author":"L van Iersel","year":"2016","unstructured":"van Iersel, L., Kelk, S., & Scornavacca, C. (2016). Kernelizations for the hybridization number problem on multiple nonbinary trees. Journal of Computer and System Sciences, 82(6), 1075\u20131089.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"4352_CR34","doi-asserted-by":"publisher","first-page":"1431","DOI":"10.1137\/110845045","volume":"42","author":"C Whidden","year":"2013","unstructured":"Whidden, C., Beiko, R. G., & Zeh, N. (2013). Fixed-parameter algorithms for maximum agreement forests. SIAM Journal on Computing, 42(4), 1431\u20131466.","journal-title":"SIAM Journal on Computing"},{"key":"4352_CR35","doi-asserted-by":"crossref","unstructured":"Whidden, C., & Matsen, F. (2018). Calculating the unrooted subtree prune-and-regraft distance. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, 16(3), 898\u2013911.","DOI":"10.1109\/TCBB.2018.2802911"},{"issue":"4","key":"4352_CR36","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1093\/sysbio\/syu023","volume":"63","author":"C Whidden","year":"2014","unstructured":"Whidden, C., Zeh, N., & Beiko, R. G. (2014). Supertrees based on the subtree prune-and-regraft distance. Systematic Biology, 63(4), 566\u2013581.","journal-title":"Systematic Biology"},{"issue":"2","key":"4352_CR37","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btn606","volume":"25","author":"Y Wu","year":"2009","unstructured":"Wu, Y. (2009). A practical method for exact computation of subtree prune and regraft distance. Bioinformatics, 25(2), 190\u2013196.","journal-title":"Bioinformatics"},{"issue":"1\u20132","key":"4352_CR38","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10479-017-2456-9","volume":"276","author":"R Yoshida","year":"2019","unstructured":"Yoshida, R., Fukumizu, K., & Vogiatzis, C. (2019). Multilocus phylogenetic analysis with gene tree clustering. Annals of Operations Research, 276(1\u20132), 293\u2013313.","journal-title":"Annals of Operations Research"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04352-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04352-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04352-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T21:42:18Z","timestamp":1699825338000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04352-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,19]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["4352"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04352-1","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,19]]},"assertion":[{"value":"30 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}