{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T06:31:46Z","timestamp":1786689106155,"version":"build-2736575974"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T00:00:00Z","timestamp":1783468800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T00:00:00Z","timestamp":1783468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"JSPS KAKENHI","award":["22H03550\/23K24807"],"award-info":[{"award-number":["22H03550\/23K24807"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1007\/s00453-026-01400-9","type":"journal-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T06:05:55Z","timestamp":1783490755000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["MUL-Tree Pruning for Consistency and Compatibility"],"prefix":"10.1007","volume":"88","author":[{"given":"Christopher","family":"Hampson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel J.","family":"Harvey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jesper","family":"Jansson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zara","family":"Lim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"issue":"3","key":"1400_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"AV Aho","year":"1981","unstructured":"Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput. 10(3), 405\u2013421 (1981)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1400_CR2","doi-asserted-by":"publisher","first-page":"1656","DOI":"10.1137\/S0097539794269461","volume":"26","author":"A Amir","year":"1997","unstructured":"Amir, A., Keselman, D.: Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms. SIAM J. Comput. 26(6), 1656\u20131669 (1997)","journal-title":"SIAM J. Comput."},{"key":"1400_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, M.S.: Linear-time algorithms for some phylogenetic tree completion problems under Robinson-Foulds distance. In RECOMB International conference on Comparative Genomics, pages 209\u2013226. Springer, 2018","DOI":"10.1007\/978-3-030-00834-5_12"},{"key":"1400_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, M.S., Burleigh, J.G., Eulenstein, O., Fern\u00e1ndez-Baca, D.: Robinson-Foulds supertrees. Algorithms for Molecular Biology 5(1), 1\u201312 (2010)","DOI":"10.1186\/1748-7188-5-18"},{"issue":"4","key":"1400_CR5","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","volume":"8","author":"M Bordewich","year":"2005","unstructured":"Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8(4), 409\u2013423 (2005)","journal-title":"Ann. Comb."},{"key":"1400_CR6","unstructured":"Bryant, D.: A classification of consensus methods for phylogenetics. In: M.\u00a0F. Janowitz, F.-J. Lapointe, F.\u00a0R. McMorris, B.\u00a0Mirkin, and F.\u00a0S. Roberts, (eds), Bioconsensus, Vol.\u00a061 DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 163\u2013184. American Mathematical Society (2003)"},{"key":"1400_CR7","doi-asserted-by":"crossref","unstructured":"Cole, R., Farach-Colton, M., Hariharan, R., Przytycka, T., Thorup, M.: An $${O}(n\\log n)$$ Algorithm for the maximum agreement subtree problem for binary trees. SIAM J. Comput. 30(5), 1385\u20131404 (2000)","DOI":"10.1137\/S0097539796313477"},{"key":"1400_CR8","doi-asserted-by":"crossref","unstructured":"Cui, Y., Jansson, J., Sung, W.-K.: Polynomial-time algorithms for building a consensus MUL-Tree. J. Comput. Biol. 19(9), 1073\u20131088 (2012)","DOI":"10.1089\/cmb.2012.0008"},{"issue":"8","key":"1400_CR9","doi-asserted-by":"publisher","first-page":"2453","DOI":"10.1007\/s00453-017-0330-4","volume":"80","author":"Y Deng","year":"2018","unstructured":"Deng, Y., Fern\u00e1ndez-Baca, D.: Fast compatibility testing for rooted phylogenetic trees. Algorithmica 80(8), 2453\u20132477 (2018)","journal-title":"Algorithmica"},{"issue":"2","key":"1400_CR10","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1089\/cmb.2006.13.522","volume":"13","author":"Z Ding","year":"2006","unstructured":"Ding, Z., Filkov, V., Gusfield, D.: A linear-time algorithm for the perfect phylogeny haplotyping (PPH) problem. J. Comput. Biol. 13(2), 522\u2013553 (2006)","journal-title":"J. Comput. Biol."},{"key":"1400_CR11","volume-title":"Inferring Phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer Associates Inc, Sunderland, Massachusetts (2004)"},{"issue":"1","key":"1400_CR12","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01908078","volume":"2","author":"CR Finden","year":"1985","unstructured":"Finden, C.R., Gordon, A.D.: Obtaining common pruned trees. J. Classif. 2(1), 255\u2013276 (1985)","journal-title":"J. Classif."},{"issue":"4","key":"1400_CR13","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1109\/TCBB.2006.57","volume":"3","author":"G Ganapathy","year":"2006","unstructured":"Ganapathy, G., Goodson, B., Jansen, R., Le, H., Ramachandran, V., Warnow, T.: Pattern identification in biogeography. IEEE\/ACM Trans. Comput. Biol. Bioinf. 3(4), 334\u2013346 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"1400_CR14","doi-asserted-by":"crossref","unstructured":"Huber, K.T., Moulton, 871 V.: Phylogenetic networks from multi-labelled trees. J. Math. Biol. 52(5), 613\u2013632 (2006)","DOI":"10.1007\/s00285-005-0365-z"},{"key":"1400_CR15","doi-asserted-by":"crossref","unstructured":"Huber, K.T., Moulton, V., Steel, M., Wu, T.: Folding and unfolding phylogenetic trees and networks. J. Math. Biol. 73(6), 1761\u20131780 (2016)","DOI":"10.1007\/s00285-016-0993-5"},{"key":"1400_CR16","doi-asserted-by":"crossref","unstructured":"Jansson, J., Shen, C., Sung, W.-K.: Improved algorithms for constructing consensus trees. J. ACM 63(3), (2016). (Article 28)","DOI":"10.1145\/2925985"},{"key":"1400_CR17","unstructured":"Nelson, G.J., Platnick, N.I.: Systematics and Biogeography: Cladistics and Vicariance, Columbia University Press (1981)"},{"issue":"1","key":"1400_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2148-9-216","volume":"9","author":"M Lott","year":"2009","unstructured":"Lott, M., Spillner, A., Huber, K.T., Petri, A., Oxelman, B., Moulton, V.: Inferring polyploid phylogenies from multiply-labeled gene trees. BMC Evol. Biol. 9(1), 1\u201311 (2009)","journal-title":"BMC Evol. Biol."},{"key":"1400_CR19","doi-asserted-by":"crossref","unstructured":"Gascon, M., Dondi, R., El-Mabrouk, N.: Complexity and Algorithms for MUL-Tree Pruning. In: Flocchini P., Moura L., (eds.) Combinatorial Algorithms: 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021), pp. 324\u2013339, Cham, (2021). Springer International Publishing","DOI":"10.1007\/978-3-030-79987-8_23"},{"issue":"1","key":"1400_CR20","first-page":"1","volume":"45","author":"N Minaka","year":"1990","unstructured":"Minaka, N.: Cladograms and reticulated graphs: A proposal for graphic representation of cladistic structures. Bull. Biogeogr. Soc. Jpn 45(1), 1\u201310 (1990)","journal-title":"Bull. Biogeogr. Soc. Jpn"},{"key":"1400_CR21","doi-asserted-by":"crossref","unstructured":"Page, R.D.M.: Parasites, phylogeny and cospeciation. Int. J. Parasitol. 23(4), 499\u2013506 (1993)","DOI":"10.1016\/0020-7519(93)90039-2"},{"key":"1400_CR22","doi-asserted-by":"crossref","unstructured":"Page, R.D.M.: Maps between trees and cladistic analysis of historical associations among genes, organisms, and areas. Syst. Biol. 43(1), 58\u201377 (1994)","DOI":"10.1093\/sysbio\/43.1.58"},{"key":"1400_CR23","doi-asserted-by":"crossref","unstructured":"Pe\u2019er, I., Pupko, T., Shamir, R., Sharan, R.: Incomplete directed perfect phylogeny. SIAM J. Comput. 33(3), 590\u2013607 (2004)","DOI":"10.1137\/S0097539702406510"},{"key":"1400_CR24","doi-asserted-by":"crossref","unstructured":"Robinson, D.F., Foulds, L.R.: Comparison of phylogenetic trees. Math. Biosci. 53(1\u20132), 131\u2013147 (1981)","DOI":"10.1016\/0025-5564(81)90043-2"},{"issue":"3","key":"1400_CR25","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1016\/j.ic.2010.11.022","volume":"209","author":"C Scornavacca","year":"2011","unstructured":"Scornavacca, C., Berry, V., Ranwez, V.: Building species trees from larger parts of phylogenomic databases. Inf. Comput. 209(3), 590\u2013605 (2011)","journal-title":"Inf. Comput."},{"issue":"1","key":"1400_CR26","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. J. Classification 9(1), 91\u2013116 (1992)","journal-title":"J. Classification"},{"key":"1400_CR27","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M Steel","year":"1993","unstructured":"Steel, M., Warnow, T.: Kaikoura tree theorems: Computing the maximum agreement subtree. Inf. Process. Lett. 48, 77\u201382 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1400_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-15-127","volume":"15","author":"L van Iersel","year":"2014","unstructured":"van Iersel, L., Kelk, S., Leki\u0107, N., Scornavacca, C.: A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees. BMC Bioinformatics 15(1), 1\u201312 (2014)","journal-title":"BMC Bioinformatics"},{"key":"1400_CR29","doi-asserted-by":"crossref","unstructured":"Whidden, C., Zeh, N., Beiko, R.G.: Supertrees based on the subtree prune-and-regraft distance. Syst. Biol. 63(4), 566\u2013581 (2014)","DOI":"10.1093\/sysbio\/syu023"},{"issue":"2","key":"1400_CR30","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btn606","volume":"25","author":"Y Wu","year":"2009","unstructured":"Wu, Y.: A practical method for exact computation of subtree prune and regraft distance. Bioinformatics 25(2), 190\u2013196 (2009)","journal-title":"Bioinformatics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01400-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01400-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01400-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T06:10:51Z","timestamp":1786687851000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01400-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,8]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["1400"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01400-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,8]]},"assertion":[{"value":"30 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"58"}}