{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:42:08Z","timestamp":1743046928002,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031721991"},{"type":"electronic","value":"9783031722004"}],"license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"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":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present <jats:italic>FullSynesth<\/jats:italic>, a tree reconciliation algorithm predicting the evolution of a set of homologous genomic regions or <jats:italic>syntenies<\/jats:italic>, inside a species tree. The considered evolutionary model involves <jats:italic>segmental events<\/jats:italic> (i.e. acting\u00a0on 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\u00a0and a set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>G<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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\u00a0and syntenies given a species tree. The problem is NP-hard for the\u00a0DL distance. FullSynesth is based on <jats:italic>Synesth<\/jats:italic> explicating\u00a0the evolution of a set of syntenies given a single <jats:italic>synteny tree<\/jats:italic>, which can be obtained from <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>G<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula> by selecting\u00a0an \u201coptimal\u201d supertree. Rather than trying each supertree in turn, FullSynesth is based on a two-in-one approach simultaneously building and reconciling a <jats:italic>synteny supertree<\/jats:italic>. The running time of this algorithm is exponential in the number of gene\u00a0trees rather than in the size 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\u00a0the algorithm is available at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"http:\/\/www.iro.umontreal.ca\/%7emabrouk\/\">http:\/\/www.iro.umontreal.ca\/~mabrouk\/<\/jats:ext-link>.<\/jats:p>","DOI":"10.1007\/978-3-031-72200-4_10","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"127-142","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Simultaneously Building and\u00a0Reconciling a\u00a0Synteny Tree"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8654-8375","authenticated-orcid":false,"given":"Mathieu","family":"Gascon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4561-683X","authenticated-orcid":false,"given":"Matt\u00e9o","family":"Delabre","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5385-1015","authenticated-orcid":false,"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"key":"10_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."},{"key":"10_CR2","doi-asserted-by":"crossref","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)","DOI":"10.1093\/bioinformatics\/bts225"},{"key":"10_CR3","doi-asserted-by":"crossref","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)","DOI":"10.1109\/TCBB.2010.14"},{"key":"10_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":"10_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":"10_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"},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1038\/s41579-019-0299-x","volume":"18","author":"KS Makarova","year":"2020","unstructured":"Makarova, K.S., et al.: Evolutionary classification of CRISPR-Cas systems: a burst of class 2 and derived variants. Nat. Rev. Microbiol. 18(2), 67\u201383 (2020)","journal-title":"Nat. Rev. Microbiol."},{"issue":"5","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1312","DOI":"10.1093\/gbe\/evx069","volume":"9","author":"W Duchemin","year":"2017","unstructured":"Duchemin, W., et al.: 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":"10_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":"10_CR10","doi-asserted-by":"publisher","first-page":"03","DOI":"10.1186\/s13015-019-0139-6","volume":"14","author":"R Dondi","year":"2019","unstructured":"Dondi, R., Lafond, M., Scornavacca, C.: Reconciling multiple genes trees via segmental duplications and losses. Algorithms Molecular Biol. 14(1), 03 (2019)","journal-title":"Algorithms Molecular Biol."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Paszek, J., Gorecki, P.: Efficient algorithms for genomic duplication models. IEEE\/ACM Trans Comput. Biol. Bioinform. (2017)","DOI":"10.1109\/TCBB.2017.2706679"},{"key":"10_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., et al.: Evolution through segmental duplications and losses: a super-reconciliation approach. Algorithms Molecular Biol. 15, 12 (2020)","journal-title":"Algorithms Molecular Biol."},{"key":"10_CR13","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, Cham, pp. 124\u2013145 (2022)","DOI":"10.1007\/978-3-031-06220-9_8"},{"key":"10_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"},{"key":"10_CR15","doi-asserted-by":"crossref","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)","DOI":"10.1137\/0210030"},{"key":"10_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":"10_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":"10_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":"10_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":"10_CR20","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."},{"key":"10_CR21","doi-asserted-by":"crossref","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)","DOI":"10.1109\/TCBB.2010.74"},{"key":"10_CR22","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. Theoret. Comput. Sci. 530, 66\u201379 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"10_CR23","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 Molecular Biol. 5(1), 18 (2010)","journal-title":"Algorithms Molecular Biol."},{"key":"10_CR24","unstructured":"Bayzid, M.S., Mirarab, S., Warnow, T.: Inferring optimal species trees under gene duplication and loss. Pac Symp. Biocomput. 250\u2013261 (2013)"},{"issue":"4","key":"10_CR25","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":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72200-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:03:32Z","timestamp":1726686212000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors declare no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Vallarta","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/computo.fismat.umich.mx\/spire2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}