{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:47:58Z","timestamp":1779896878493,"version":"3.53.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"name":"NSERC\/FRQNT NOVA program","award":["327657"],"award-info":[{"award-number":["327657"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"DOI":"10.1186\/s13015-025-00283-9","type":"journal-article","created":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:52:28Z","timestamp":1759333948000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Finding maximum common contractions between phylogenetic networks"],"prefix":"10.1186","volume":"20","author":[{"given":"Bertrand","family":"Marchand","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nadia","family":"Tahiri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shohreh Golpaigani","family":"Fard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olivier","family":"Tremblay-Savard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manuel","family":"Lafond","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,10,1]]},"reference":[{"issue":"13","key":"283_CR1","doi-asserted-by":"publisher","first-page":"4962","DOI":"10.1073\/pnas.1116871109","volume":"109","author":"SS Abby","year":"2012","unstructured":"Abby SS, Tannier E, Gouy M, Daubin V. Lateral gene transfer as a support for the tree of life. Proc Natl Acad Sci. 2012;109(13):4962\u20137.","journal-title":"Proc Natl Acad Sci"},{"issue":"1","key":"283_CR2","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1146\/annurev.micro.55.1.709","volume":"55","author":"EV Koonin","year":"2001","unstructured":"Koonin EV, Makarova KS, Aravind L. Horizontal gene transfer in prokaryotes: quantification and classification. Annu Rev Microbiol. 2001;55(1):709\u201342.","journal-title":"Annu Rev Microbiol"},{"issue":"13","key":"283_CR3","doi-asserted-by":"publisher","first-page":"7043","DOI":"10.1073\/pnas.97.13.7043","volume":"97","author":"NC Ellstrand","year":"2000","unstructured":"Ellstrand NC, Schierenbeck KA. Hybridization as a stimulus for the evolution of invasiveness in plants? Proc Natl Acad Sci. 2000;97(13):7043\u201350.","journal-title":"Proc Natl Acad Sci"},{"key":"283_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic networks: concepts, algorithms and applications","author":"DH Huson","year":"2010","unstructured":"Huson DH, Rupp R, Scornavacca C. Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press; 2010."},{"issue":"1","key":"283_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1093\/oxfordjournals.molbev.a026036","volume":"16","author":"H-J Bandelt","year":"1999","unstructured":"Bandelt H-J, Forster P, R\u00f6hl A. Median-joining networks for inferring intraspecific phylogenies. Mol Biol Evol. 1999;16(1):37\u201348.","journal-title":"Mol Biol Evol"},{"issue":"W1","key":"283_CR6","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1093\/nar\/gks485","volume":"40","author":"A Boc","year":"2012","unstructured":"Boc A, Diallo AB, Makarenkov V. T-rex: a web server for inferring, validating and visualizing phylogenetic trees and networks. Nucleic Acids Res. 2012;40(W1):573\u20139.","journal-title":"Nucleic Acids Res"},{"issue":"8","key":"283_CR7","doi-asserted-by":"publisher","first-page":"1005071","DOI":"10.1371\/journal.pcbi.1005071","volume":"12","author":"PG C\u00e1mara","year":"2016","unstructured":"C\u00e1mara PG, Levine AJ, Rabadan R. Inference of ancestral recombination graphs through topological data analysis. PLoS Comput Biol. 2016;12(8):1005071.","journal-title":"PLoS Comput Biol"},{"issue":"01","key":"283_CR8","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0219720004000521","volume":"2","author":"D Gusfield","year":"2004","unstructured":"Gusfield D, Eddhu S, Langley C. Optimal, efficient reconstruction of phylogenetic networks with constrained recombination. J Bioinform Comput Biol. 2004;2(01):173\u2013213.","journal-title":"J Bioinform Comput Biol"},{"issue":"3","key":"283_CR9","doi-asserted-by":"publisher","first-page":"1005896","DOI":"10.1371\/journal.pgen.1005896","volume":"12","author":"C Sol\u00eds-Lemus","year":"2016","unstructured":"Sol\u00eds-Lemus C, An\u00e9 C. Inferring phylogenetic networks with maximum pseudolikelihood under incomplete lineage sorting. PLoS Genet. 2016;12(3):1005896.","journal-title":"PLoS Genet"},{"issue":"17","key":"283_CR10","doi-asserted-by":"publisher","first-page":"9241","DOI":"10.1073\/pnas.2004999117","volume":"117","author":"P Forster","year":"2020","unstructured":"Forster P, Forster L, Renfrew C, Forster M. Phylogenetic network analysis of sars-cov-2 genomes. Proc Natl Acad Sci. 2020;117(17):9241\u20133.","journal-title":"Proc Natl Acad Sci"},{"issue":"23","key":"283_CR11","doi-asserted-by":"publisher","first-page":"12518","DOI":"10.1073\/pnas.2007062117","volume":"117","author":"SJ S\u00e1nchez-Pacheco","year":"2020","unstructured":"S\u00e1nchez-Pacheco SJ, Kong S, Pulido-Santacruz P, Murphy RW, Kubatko L. Median-joining network analysis of sars-cov-2 genomes is neither phylogenetic nor evolutionary. Proc Natl Acad Sci. 2020;117(23):12518\u20139.","journal-title":"Proc Natl Acad Sci"},{"issue":"23","key":"283_CR12","doi-asserted-by":"publisher","first-page":"12524","DOI":"10.1073\/pnas.2007433117","volume":"117","author":"P Forster","year":"2020","unstructured":"Forster P, Forster L, Renfrew C, Forster M. Reply to explaining phylogenetic network analysis of sars-cov-2 genomes. Proc Natl Acad Sci USA. 2020;117(23):12524.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"23","key":"283_CR13","doi-asserted-by":"publisher","first-page":"12522","DOI":"10.1073\/pnas.2007295117","volume":"117","author":"C Mavian","year":"2020","unstructured":"Mavian C, Pond SK, Marini S, Magalis BR, Vandamme A-M, Dellicour S, Scarpino SV, Houldcroft C, Villabona-Arenas J, Paisie TK, et al. Sampling bias and incorrect rooting make phylogenetic network tracing of sars-cov-2 infections unreliable. Proc Natl Acad Sci. 2020;117(23):12522\u20133.","journal-title":"Proc Natl Acad Sci"},{"issue":"1\u20132","key":"283_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"DF Robinson","year":"1981","unstructured":"Robinson DF, Foulds LR. Comparison of phylogenetic trees. Math Biosci. 1981;53(1\u20132):131\u201347.","journal-title":"Math Biosci"},{"key":"283_CR15","volume":"1","author":"G Cardona","year":"2014","unstructured":"Cardona G, Llabr\u00e9s M, Rossell\u00f3 F, Valiente G, et al. The comparison of tree-sibling time consistent phylogenetic networks is graph isomorphism-complete. Sci World J. 2014;1: 254279.","journal-title":"Sci World J"},{"issue":"1","key":"283_CR16","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/TCBB.2008.70","volume":"6","author":"G Cardona","year":"2008","unstructured":"Cardona G, Llabr\u00e9s M, Rossell\u00f3 F, Valiente G. Metrics for phylogenetic networks I: generalizations of the Robinson-Foulds metric. IEEE\/ACM Trans Comput Biol Bioinf. 2008;6(1):46\u201361.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"283_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1109\/TCBB.2004.10","volume":"1","author":"BM Moret","year":"2004","unstructured":"Moret BM, Nakhleh L, Warnow T, Linder CR, Tholse A, Padolina A, Sun J, Timme R. Phylogenetic networks: modeling, reconstructibility, and accuracy. IEEE\/ACM Trans Comput Biol Bioinf. 2004;1(1):13\u201323.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"2","key":"283_CR18","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.mbs.2007.11.003","volume":"211","author":"G Cardona","year":"2008","unstructured":"Cardona G, Rossell\u00f3 F, Valiente G. Tripartitions do not always discriminate phylogenetic networks. Math Biosci. 2008;211(2):356\u201370.","journal-title":"Math Biosci"},{"key":"283_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2021.108537","volume":"332","author":"A Bai","year":"2021","unstructured":"Bai A, Erd\u0151s PL, Semple C, Steel M. Defining phylogenetic networks using ancestral profiles. Math Biosci. 2021;332: 108537.","journal-title":"Math Biosci"},{"key":"283_CR20","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2024.3361390","author":"G Cardona","year":"2024","unstructured":"Cardona G, Pons JC, Ribas G, Mart\u0131nez Coronado T. Comparison of orchard networks using their extended $$\\mu $$-representation. IEEE\/ACM Trans Comput Biol Bioinform. 2024. https:\/\/doi.org\/10.1109\/TCBB.2024.3361390.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"3","key":"283_CR21","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1109\/TCBB.2008.127","volume":"6","author":"G Cardona","year":"2008","unstructured":"Cardona G, Llabr\u00e9s M, Rossell\u00f3 F, Valiente G. Metrics for phylogenetic networks ii: nodal and triplets metrics. IEEE\/ACM Trans Comput Biol Bioinf. 2008;6(3):454\u201369.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"8","key":"283_CR22","doi-asserted-by":"publisher","first-page":"1005611","DOI":"10.1371\/journal.pcbi.1005611","volume":"13","author":"P Gambette","year":"2017","unstructured":"Gambette P, Van Iersel L, Jones M, Lafond M, Pardi F, Scornavacca C. Rearrangement moves on rooted phylogenetic networks. PLoS Comput Biol. 2017;13(8):1005611.","journal-title":"PLoS Comput Biol"},{"key":"283_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jtbi.2017.03.032","volume":"423","author":"M Bordewich","year":"2017","unstructured":"Bordewich M, Linz S, Semple C. Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. J Theor Biol. 2017;423:1\u201312.","journal-title":"J Theor Biol"},{"issue":"3","key":"283_CR24","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1109\/TCBB.2022.3162991","volume":"20","author":"K Landry","year":"2022","unstructured":"Landry K, Teodocio A, Lafond M, Tremblay-Savard O. Defining phylogenetic network distances using cherry operations. IEEE\/ACM Trans Comput Biol Bioinf. 2022;20(3):1654\u201366.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"283_CR25","doi-asserted-by":"crossref","unstructured":"Landry K, Tremblay-Savard O, Lafond M. A fixed-parameter tractable algorithm for finding agreement cherry-reduced subnetworks in level-1 orchard networks. J Comput Biol. 2023.","DOI":"10.1007\/978-3-031-36911-7_12"},{"key":"283_CR26","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. 2005;8:409\u201323.","journal-title":"Ann Comb"},{"issue":"22","key":"283_CR27","first-page":"21","volume":"23","author":"B DasGupta","year":"1998","unstructured":"DasGupta B, He X, Jiang T, Li M, Tromp J, Zhang L. On computing the nearest neighbor interchange distance. Computing. 1998;23(22):21\u20136.","journal-title":"Computing"},{"key":"283_CR28","unstructured":"Klawitter J. Spaces of phylogenetic networks. PhD thesis, ResearchSpace@ Auckland. 2020."},{"issue":"1","key":"283_CR29","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2004.12.012","volume":"335","author":"C Choy","year":"2005","unstructured":"Choy C, Jansson J, Sadakane K, Sung W-K. Computing the maximum agreement of phylogenetic networks. Theoret Comput Sci. 2005;335(1):93\u2013107.","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"283_CR30","doi-asserted-by":"publisher","first-page":"211","DOI":"10.21136\/CPM.1990.108363","volume":"115","author":"B Zelinka","year":"1990","unstructured":"Zelinka B. Contraction distance between isomorphism classes of graphs. \u010casopis pro p\u011bstov\u00e1n\u00ed matematiky. 1990;115(2):211\u20136.","journal-title":"\u010casopis pro p\u011bstov\u00e1n\u00ed matematiky"},{"issue":"1","key":"283_CR31","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jgt.3190110111","volume":"11","author":"AE Brouwer","year":"1987","unstructured":"Brouwer AE, Veldman HJ. Contractibility and np-completeness. J Graph Theory. 1987;11(1):71\u20139.","journal-title":"J Graph Theory"},{"issue":"3","key":"283_CR32","first-page":"178","volume":"51","author":"A Levin","year":"2008","unstructured":"Levin A, Paulusma D, Woeginger GJ. The computational complexity of graph contractions I: polynomially solvable and np-complete cases. Netw Int J. 2008;51(3):178\u201389.","journal-title":"Netw Int J"},{"key":"283_CR33","doi-asserted-by":"crossref","unstructured":"Kami\u0144ski M, Paulusma D, Thilikos DM. Contractions of planar graphs in polynomial time. In: Algorithms\u2013ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part I 18, 2010;pp. 122\u2013133. Springer.","DOI":"10.1007\/978-3-642-15775-2_11"},{"issue":"7","key":"283_CR34","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/s00236-014-0204-z","volume":"51","author":"R Belmonte","year":"2014","unstructured":"Belmonte R, Golovach PA, Hof P, Paulusma D. Parameterized complexity of three edge contraction problems with degree constraints. Acta Informatica. 2014;51(7):473\u201397.","journal-title":"Acta Informatica"},{"issue":"1\u20133","key":"283_CR35","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","volume":"108","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek J, Thomas R. On the complexity of finding iso-and other morphisms for partial k-trees. Discret Math. 1992;108(1\u20133):343\u201364.","journal-title":"Discret Math"},{"key":"283_CR36","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.ejc.2017.07.012","volume":"68","author":"N Kriege","year":"2018","unstructured":"Kriege N, Kurpicz F, Mutzel P. On maximum common subgraph problems in series-parallel graphs. Eur J Comb. 2018;68:79\u201395.","journal-title":"Eur J Comb"},{"issue":"02","key":"283_CR37","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0129054120500069","volume":"31","author":"T Akutsu","year":"2020","unstructured":"Akutsu T, Melkman AA, Tamura T. Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree. Int J Found Comput Sci. 2020;31(02):253\u201373.","journal-title":"Int J Found Comput Sci"},{"key":"283_CR38","volume-title":"Graph Theory","author":"R Diestel","year":"2016","unstructured":"Diestel R. Graph Theory. Springer; 2016."},{"issue":"1","key":"283_CR39","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks EM. Isomorphism of graphs of bounded valence can be tested in polynomial time. J Comput Syst Sci. 1982;25(1):42\u201365.","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"283_CR40","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s12064-023-00398-w","volume":"142","author":"M Hellmuth","year":"2023","unstructured":"Hellmuth M, Schaller D, Stadler PF. Clustering systems of phylogenetic networks. Theory Biosci. 2023;142(4):301\u201358.","journal-title":"Theory Biosci"},{"key":"283_CR41","unstructured":"Garey MR, Johnson DS. Computers and Intractability vol. 174. freeman San Francisco. 1979."},{"key":"283_CR42","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2020.02.010","volume":"815","author":"A Darmann","year":"2020","unstructured":"Darmann A, D\u00f6cker J. On a simple hard variant of not-all-equal 3-sat. Theoret Comput Sci. 2020;815:147\u201352.","journal-title":"Theoret Comput Sci"},{"key":"283_CR43","unstructured":"Antony D, Cao Y, Pal S, Sandeep R. Switching classes: characterization and computation. 2024. arXiv preprint arXiv:2403.04263"},{"issue":"1","key":"283_CR44","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.mbs.2009.06.007","volume":"221","author":"F Rossell\u00f3","year":"2009","unstructured":"Rossell\u00f3 F, Valiente G. All that glisters is not galled. Math Biosci. 2009;221(1):54\u20139.","journal-title":"Math Biosci"},{"key":"283_CR45","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.tcs.2021.01.033","volume":"860","author":"A Agrawal","year":"2021","unstructured":"Agrawal A, Kanesh L, Saurabh S, Tale P. Paths to trees and cacti. Theoret Comput Sci. 2021;860:98\u2013116.","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"283_CR46","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/s13015-022-00213-z","volume":"17","author":"B Marchand","year":"2022","unstructured":"Marchand B, Ponty Y, Bulteau L. Tree diet: reducing the treewidth to unlock fpt algorithms in RNA bioinformatics. Algorithms Mol Biol. 2022;17(1):8.","journal-title":"Algorithms Mol Biol"},{"key":"283_CR47","doi-asserted-by":"crossref","unstructured":"Berry V, Scornavacca C, Weller M. Scanning phylogenetic networks is np-hard. In: SOFSEM 2020: Theory and Practice of Computer Science: 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20\u201324, 2020, Proceedings 46, 2020;pp. 519\u2013530. Springer.","DOI":"10.1007\/978-3-030-38919-2_42"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00283-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00283-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00283-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:52:31Z","timestamp":1759333951000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-025-00283-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,1]]},"references-count":47,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["283"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00283-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,1]]},"assertion":[{"value":"31 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no Conflict of interest nor Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"18"}}