{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T23:15:33Z","timestamp":1779405333897,"version":"3.53.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032268907","type":"print"},{"value":"9783032268914","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,5,22]],"date-time":"2026-05-22T00:00:00Z","timestamp":1779408000000},"content-version":"vor","delay-in-days":141,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a tree topology and an assignment of character states to its leaves, the Small Parsimony Problem (SPP) consists\u00a0in assigning character states to the internal nodes in a way maximizing a certain parsimony or probabilistic criterion. In the genome rearrangement field, tree leaves are permutations of gene sets,\u00a0and the problem is to infer permutations at internal nodes minimizing\u00a0a rearrangement distance. Almost all genome rearrangement models\u00a0lead to intractable problems for the SPP. Considering only the numerical profiles on a phylogeny, the Count package (Cs\u0171r\u00f6s,\u00a02010) can be used to predict the size of gene families on internal\u00a0nodes under a parsimony or probabilistic model. Here, we present\u00a0a tractable version of the SPP: given a tree topology leaf-labeled\u00a0by unordered gene sets, infer gene sets at internal nodes in a\u00a0way minimizing the number of gain and loss episodes on the edges of\u00a0the tree, while having a single gain point for each gene (i.e.\u00a0under Dollo\u2019s law). We show that the entire solution space is covered\u00a0by testing four possible cases on each internal node\u2019s content, leading to a linear-time dynamic programming algorithm for obtaining\u00a0an optimal solution. We apply our\n                    <jats:italic>InOutParsimony<\/jats:italic>\n                    software\u00a0to clusters of orthologous mitochondrial protein-coding\u00a0genes (MitoCOGs) in both the mitochondrial and nuclear genomes of 11\u00a0land plant species. The results are discussed considering\u00a0the Endosymbiotic Gene Transfer events shaping the mitochondria\u00a0and nucleus contents and compared with Count\u2019s returned numerical profiles.\n                  <\/jats:p>","DOI":"10.1007\/978-3-032-26891-4_10","type":"book-chapter","created":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T22:21:05Z","timestamp":1779402065000},"page":"180-210","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Gene Repertoire Evolution Minimizing Episodes of\u00a0Gains and\u00a0Losses"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8654-8375","authenticated-orcid":false,"given":"Mathieu","family":"Gascon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4561-683X","authenticated-orcid":false,"given":"Matt\u00e9o","family":"Delabre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5385-1015","authenticated-orcid":false,"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,22]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.7155\/jgaa.00175","volume":"13","author":"S Angibaud","year":"2009","unstructured":"Angibaud, S., Fertin, G., Rusu, I., Th\u00e9venin, A., Vialette, S.: On the approximability of comparing genomes with duplicates. J. Graph Algorithms Appl. 13(1), 19\u201353 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Anselmetti, Y., Delabre, M., El-Mabrouk, N.: Reconciliation with segmental duplication, transfer, loss and gain. In: Jin, L., Durand, D. (eds.) Comparative Genomics, pp. 124\u2013145. Cham (2022)","DOI":"10.1007\/978-3-031-06220-9_8"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Anselmetti, Y., El-Mabrouk, N., Lafond, M., Ouangraoua, A.: Gene tree and species tree reconciliation with endosymbiotic gene transfer. Bioinformatics 37(SI-1), i120\u2013i132 (2021)","DOI":"10.1093\/bioinformatics\/btab328"},{"issue":"4","key":"10_CR4","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1109\/TCBB.2007.1069","volume":"4","author":"G Blin","year":"2007","unstructured":"Blin, G., Chauve, C., Fertin, G., Rizzi, R., Vialette, S.: Comparing genomes with duplications: a computational complexity point of view. IEEE\/ACM Trans. Comput. Biol. Bioinf. 4(4), 523\u2013534 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Bohnenkamper, L., Stoye, J., Doerr, D.: Reconstructing rearrangement phylogenies of natural genomes. Algorithms Mol. Biol. 20(10) (2025)","DOI":"10.1186\/s13015-025-00279-5"},{"issue":"1","key":"10_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","volume":"15","author":"A Caprara","year":"2003","unstructured":"Caprara, A.: The reversal median problem. INFORMS J. Comput. 15(1), 93\u2013113 (2003)","journal-title":"INFORMS J. Comput."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Cs\u0171r\u00f6s, M.: Ancestral reconstruction by asymmetric Wagner parsimony over continuous characters and squared parsimony over distributions. In: Proceedings of the Sixth RECOMB Comparative Genomics Satellite Workshop. LNB, vol.\u00a05267, pp. 72\u201386 (2008)","DOI":"10.1007\/978-3-540-87989-3_6"},{"issue":"15","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1910","DOI":"10.1093\/bioinformatics\/btq315","volume":"26","author":"M Cs\u0171r\u00f6s","year":"2010","unstructured":"Cs\u0171r\u00f6s, M.: Count: evolutionary analysis of phylogenetic profiles with parsimony and likelihood. Bioinformatics 26(15), 1910\u20132 (2010)","journal-title":"Bioinformatics"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tpb.2022.03.003","volume":"145","author":"M Cs\u0171r\u00f6s","year":"2022","unstructured":"Cs\u0171r\u00f6s, M.: Gain-loss-duplication models for copy number evolution on a phylogeny: exact algorithms for computing the likelihood and its gradient. Theor. Popul. Biol. 145, 80\u201394 (2022)","journal-title":"Theor. Popul. Biol."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Cs\u0171r\u00f6s, M., Mikl\u00f3s, I.: A probabilistic model for gene content evolution with duplication, loss, and horizontal transfer. In: Proceedings of the Tenth Annual International Conference on Research in Computational Molecular Biology (RECOMB). LeNB, vol. 14899, pp. 206\u2013220 (2006)","DOI":"10.1007\/11732990_18"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Delabre, M., El-Mabrouk, N.: Synesth: comprehensive syntenic reconciliation with unsampled lineages. Algorithms 17(5) (2024)","DOI":"10.3390\/a17050186"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, D., Chauve, C.: Small parsimony for natural genomes in the DCJ-indel model. J. Bioinf. Comput. Biol. 19(6) (2021)","DOI":"10.1142\/S0219720021400096"},{"issue":"5","key":"10_CR13","doi-asserted-by":"publisher","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","volume":"8","author":"P Feijao","year":"2011","unstructured":"Feijao, P., Meidanis, J.: SCJ: a breakpoint-like distance that simplifies several rearrangement problems. IEEE\/ACM Trans. Comput. Biol. Bioinf. 8(5), 1318\u20131329 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"4","key":"10_CR14","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch, W.M.: Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20(4), 406\u2013416 (1971)","journal-title":"Syst. Zool."},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Gascon, M., Delabre, M., El-Mabrouk, N.: FullSynesth: syntenic reconciliation of a set of consistent gene trees. Theory Comput. Syst. 70(8) (2026)","DOI":"10.1007\/s00224-025-10259-2"},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"132","DOI":"10.2307\/2412519","volume":"28","author":"M Goodman","year":"1979","unstructured":"Goodman, M., Czelusniak, J., Moore, G.W., Romero-Herrera, A.E., Matsuda, G.: Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst. Zool. 28, 132\u2013163 (1979)","journal-title":"Syst. Zool."},{"issue":"11","key":"10_CR17","first-page":"1","volume":"14","author":"S Kannan","year":"2014","unstructured":"Kannan, S., Rogozin, I., Koonin, E.: MitoCOGs: clusters of orthologous genes from mitochondria and implications for the evolution of eukaryotes. BMC Evol. Biol. 14(11), 1\u201316 (2014)","journal-title":"BMC Evol. Biol."},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/cmb.2013.0004","volume":"21","author":"J Kov\u00e1c","year":"2014","unstructured":"Kov\u00e1c, J.: On the complexity of rearrangement problems under the breakpoint distance. J. Comput. Biol. 21(1), 1\u201315 (2014)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"10_CR19","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1109\/TCBB.2017.2661761","volume":"16","author":"N Luhmann","year":"2019","unstructured":"Luhmann, N., Lafond, M., Th\u00e9venin, A., Ouangraoua, A., Wittler, R., Chauve, C.: The SCJ small parsimony problem for weighted gene adjacencies. IEEE\/ACM Trans. Comput. Biol. Bioinf. 16(4), 1364\u20131373 (2019)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"10_CR20","unstructured":"Pe\u2019er, I., Shamir, R.: The median problems for breakpoints are NP-complete. In: Proceedings of the Electronic Colloquium on Computational Complexity. ECCC 1998, vol.\u00a05 (1998)"},{"issue":"2","key":"10_CR21","first-page":"158","volume":"24","author":"D Sankoff","year":"1971","unstructured":"Sankoff, D.: Minimal parsimony is not enough. Syst. Zool. 24(2), 158\u2013164 (1971)","journal-title":"Syst. Zool."},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Tannier, E., E., C.Z., Sankoff, D.: Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics 10, 120 (2009)","DOI":"10.1186\/1471-2105-10-120"}],"container-title":["Lecture Notes in Computer Science","Comparative Genomics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-26891-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T22:21:10Z","timestamp":1779402070000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-26891-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032268907","9783032268914"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-26891-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"22 May 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors\u00a0have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"RECOMB-CG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"RECOMB International Workshop on Comparative Genomics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Thessaloniki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 May 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rcg2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb-cg.org","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}