{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:48:35Z","timestamp":1779896915319,"version":"3.53.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T00:00:00Z","timestamp":1770681600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003151","name":"Fonds de recherche du Qu\u00e9bec \u2013 Nature et technologies","doi-asserted-by":"publisher","award":["335135,335893"],"award-info":[{"award-number":["335135,335893"]}],"id":[{"id":"10.13039\/501100003151","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RN000743"],"award-info":[{"award-number":["RN000743"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We present\n                    <jats:italic>FullSynesth<\/jats:italic>\n                    , a tree reconciliation algorithm predicting the evolution of a set of homologous genomic regions or\n                    <jats:italic>syntenies<\/jats:italic>\n                    , inside a species tree. The considered evolutionary model involves\n                    <jats:italic>segmental events<\/jats:italic>\n                    (i.e. acting on multiple genes) including duplications (D), losses (L), synteny fissions and transfers possibly going through unsampled or extinct species. Formally, given a set of syntenies in a set of genomes and a set\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>G<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of consistent gene trees for the gene families composing the syntenies, the problem is to infer a most parsimonious evolutionary history explaining the observed gene trees and syntenies given a species tree. The problem is known to be NP-hard for the DL distance. FullSynesth is based on\n                    <jats:italic>Synesth<\/jats:italic>\n                    explicating the evolution of a set of syntenies given a single\n                    <jats:italic>synteny tree<\/jats:italic>\n                    , which can be obtained from\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>G<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    by selecting a given supertree. Rather than trying each supertree in turn, FullSynesth is based on a two-in-one approach simultaneously building and reconciling a\n                    <jats:italic>synteny supertree<\/jats:italic>\n                    . This algorithm runs in polynomial time for a fixed number of gene trees. We show on simulated datasets that FullSynesth significantly improves the running time of Synesth applied to each possible supertree. An implementation of the algorithm is available at:\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/UdeM-LBIT\/FullSynesth\" ext-link-type=\"uri\">https:\/\/github.com\/UdeM-LBIT\/FullSynesth<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1007\/s00224-025-10259-2","type":"journal-article","created":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T10:52:42Z","timestamp":1770720762000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees"],"prefix":"10.1007","volume":"70","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,2,10]]},"reference":[{"key":"10259_CR1","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":"12","key":"10259_CR2","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1093\/bioinformatics\/bts225","volume":"28","author":"MS Bansal","year":"2012","unstructured":"Bansal, M.S., Alm, E.J., Kellis, M.: Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics 28(12), 283\u2013291 (2012)","journal-title":"Bioinformatics"},{"issue":"2","key":"10259_CR3","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1109\/TCBB.2010.14","volume":"8","author":"A Tofigh","year":"2011","unstructured":"Tofigh, A., Hallett, M., Lagergren, J.: Simultaneous identification of duplications and lateral gene transfers. IEEE\/ACM Trans. Comput. BiolBioinform. 8(2), 517\u2013535 (2011)","journal-title":"IEEE\/ACM Trans. Comput. BiolBioinform."},{"key":"10259_CR4","doi-asserted-by":"publisher","first-page":"3214","DOI":"10.1093\/bioinformatics\/bty314","volume":"34","author":"MS Bansal","year":"2018","unstructured":"Bansal, M.S., Kellis, M., Kordi, M., Kundu, S.: RANGER-DTL 2.0: Rigorous reconstruction of gene-family evolution by duplication, transfer and loss. Bioinformatics 34, 3214\u20133216 (2018)","journal-title":"Bioinformatics"},{"key":"10259_CR5","doi-asserted-by":"crossref","unstructured":"Donati, B., Baudet, C., Sinaimeri, B., Crescenzi, P., Sagot, M.F.: EUCALYPT: Efficient tree reconciliation enumerator. Algorithms Mol. Biol. 10(3) (2015)","DOI":"10.1186\/s13015-014-0031-3"},{"issue":"13","key":"10259_CR6","doi-asserted-by":"publisher","first-page":"2056","DOI":"10.1093\/bioinformatics\/btw105","volume":"32","author":"E Jacox","year":"2016","unstructured":"Jacox, E., Chauve, C., Sz\u00f6ll\u0151si, G.J., Ponty, Y., Scornavacca, C.: ecceTERA: Comprehensive gene tree-species tree reconciliation using parsimony. Bioinformatics 32(13), 2056\u20132058 (2016)","journal-title":"Bioinformatics"},{"key":"10259_CR7","doi-asserted-by":"crossref","unstructured":"...Makarova, K.S., Wolf, Y.I., Iranzo, J., Shmakov, S.A., Alkhnbashi, O.S., Brouns, S.J.J., Charpentier, E., Cheng, D., Haft, D.H., Horvath, P., Moineau, S., Mojica, F.J.M., Scott, D., Shah, S.A., Siksnys, V., Terns, M.P., Venclovas, \u010c, White, M.F., Yakunin, A.F., Yan, W., Zhang, F., Garrett, R.A., Backofen, R., Oost, J.V.D., Barrangou, R., Koonin, E.V.: Evolutionary classification of CRISPR-Cas systems: A burst of class 2 and derived variants. Nat. Rev. Microbiol. 18(2), 67\u201383 (2020)","DOI":"10.1038\/s41579-019-0299-x"},{"issue":"5","key":"10259_CR8","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1093\/gbe\/evx069","volume":"9","author":"W Duchemin","year":"2017","unstructured":"Duchemin, W., Anselmetti, Y., Patterson, M., Ponty, Y., Berard, S., Chauve, C., Scornavacca, C., Daubin, V., Tannier, E.: DeCoSTAR: Reconstructing the ancestral organization of genes or genomes using reconciled phylogenies. Genome Biol. Evol. 9(5), 1312\u20131319 (2017)","journal-title":"Genome Biol. Evol."},{"key":"10259_CR9","volume-title":"Phylogeny of Dependencies and Dependencies of Phylogenies in Genes and Genomes","author":"W Duchemin","year":"2017","unstructured":"Duchemin, W.: Phylogeny of Dependencies and Dependencies of Phylogenies in Genes and Genomes. Universit\u00e9 de Lyon, Theses (2017)"},{"issue":"1","key":"10259_CR10","doi-asserted-by":"crossref","first-page":"03","DOI":"10.1186\/s13015-019-0137-8","volume":"14","author":"R Dondi","year":"2019","unstructured":"Dondi, R., Lafond, M., Scornavacca, C.: Reconciling multiple genes trees via segmental duplications and losses. Algorithm. Mole. Biol. 14(1), 03 (2019)","journal-title":"Algorithm. Mole. Biol."},{"key":"10259_CR11","doi-asserted-by":"crossref","unstructured":"Paszek, J.,\u00a0Gorecki, P.: Efficient algorithms for genomic duplication models. IEEE\/ACM Trans. Comput. Biol. Bioinform. (2017)","DOI":"10.1109\/TCBB.2017.2706679"},{"key":"10259_CR12","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/s13015-020-00171-4","volume":"15","author":"M Delabre","year":"2020","unstructured":"Delabre, M., El-Mabrouk, N., Huber, K.T., Lafond, M., Mouton, V., Noutahi, E., Castellanos, M.S.: Evolution through segmental duplications and losses: A super-reconciliation approach. Algorithm. Mole. Biol. 15, 12 (2020)","journal-title":"Algorithm. Mole. Biol."},{"key":"10259_CR13","doi-asserted-by":"crossref","unstructured":"Anselmetti, Y.,\u00a0Delabre, M.,\u00a0El-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":"10259_CR14","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"},{"issue":"3","key":"10259_CR15","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"AV Aho","year":"1981","unstructured":"Aho, A.V., Yehoshua, S., 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."},{"key":"10259_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01202270","volume":"12","author":"M Constantinescu","year":"1995","unstructured":"Constantinescu, M., Sankoff, D.: An efficient algorithm for supertrees. J. Classif. 12, 101\u2013112 (1995)","journal-title":"J. Classif."},{"key":"10259_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0166-218X(95)00074-2","volume":"69","author":"MP Ng","year":"1996","unstructured":"Ng, M.P., Wormald, N.C.: Reconstruction of rooted trees from subtrees. Discrete Appl. Math. 69, 19\u201331 (1996)","journal-title":"Discrete Appl. Math."},{"key":"10259_CR18","doi-asserted-by":"crossref","unstructured":"Lafond, M., Ouangraoua, A., El-Mabrouk, N.: Reconstructing a supergenetree minimizing reconciliation. BMC-Genomics 16, S4 (2015). Special issue of RECOMB-CG 2015","DOI":"10.1186\/1471-2105-16-S14-S4"},{"issue":"5","key":"10259_CR19","doi-asserted-by":"publisher","first-page":"1560","DOI":"10.1109\/TCBB.2017.2720581","volume":"15","author":"M Lafond","year":"2018","unstructured":"Lafond, M., Chauve, C., El-Mabrouk, N., Ouangraoua, A.: Gene tree construction and correction using supertree and reconciliation. IEEE\/ACM Trans. Comput. Biol. Bioinf. 15(5), 1560\u20131570 (2018)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"10259_CR20","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC \u201978, pp. 216\u2013226. Association for Computing Machinery, 1978","DOI":"10.1145\/800133.804350"},{"issue":"8","key":"10259_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.3390\/a14080231","volume":"14","author":"S Weiner","year":"2021","unstructured":"Weiner, S., Bansal, M.S.: Improved duplication-transfer-loss reconciliation with extinct and unsampled lineages. Algorithms 14(8), 231 (2021)","journal-title":"Algorithms"},{"key":"10259_CR22","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1137\/S0097539798343362","volume":"30","author":"B Ma","year":"2000","unstructured":"Ma, B., Li, M., Zhang, L.: From gene trees to species trees. SIAM J. Comput. 30, 729\u2013752 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10259_CR23","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1109\/TCBB.2010.74","volume":"8","author":"MS Bansal","year":"2011","unstructured":"Bansal, M.S., Shamir, R.: A note on the fixed parameter tractability of the gene-duplication problem. IEEE\/ACM Trans. Comput. Biol. Bioinform. 8(3), 848\u2013850 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"10259_CR24","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2014.02.025","volume":"530","author":"G Blin","year":"2014","unstructured":"Blin, G., Bonizzoni, P., Dondi, R., Rizzi, R., Sikora, F.: Complexity insights of the minimum duplication problem. Theor. Comput. Sci. 530, 66\u201379 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10259_CR25","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/1748-7188-5-18","volume":"5","author":"MS Bansal","year":"2010","unstructured":"Bansal, M.S., Burleigh, J.G., Eulenstein, O., Fern\u00e1ndez-Baca, D.: Robinson-foulds supertrees. Algorithms Mole. Biol. 5(1), 18 (2010)","journal-title":"Algorithms Mole. Biol."},{"key":"10259_CR26","doi-asserted-by":"crossref","unstructured":"Bayzid, M.S.,\u00a0Mirarab, S.,\u00a0Warnow, T.: Inferring optimal species trees under gene duplication and loss. Pac Symp Biocomput, pp. 250\u2013261 (2013)","DOI":"10.1142\/9789814447973_0025"},{"issue":"4","key":"10259_CR27","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1089\/cmb.2023.0309","volume":"31","author":"Y Wu","year":"2024","unstructured":"Wu, Y., Zhang, L.: Computing the bounds of the number of reticulations in a tree-child network that displays a set of trees. J. Comput. Biol. 31(4), 345\u2013359 (2024)","journal-title":"J. Comput. Biol."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10259-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10259-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10259-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:38Z","timestamp":1776760958000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10259-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,10]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10259"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10259-2","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-6247846\/v1","asserted-by":"object"}]},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,10]]},"assertion":[{"value":"17 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2026","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 competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"8"}}