{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T15:49:01Z","timestamp":1779896941904,"version":"3.53.1"},"reference-count":22,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T00:00:00Z","timestamp":1714348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"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"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["335893"],"award-info":[{"award-number":["335893"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003151","name":"Fonds de recherche du Qu\u00e9bec\u2014Nature et technologies","doi-asserted-by":"publisher","award":["RN000743"],"award-info":[{"award-number":["RN000743"]}],"id":[{"id":"10.13039\/501100003151","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003151","name":"Fonds de recherche du Qu\u00e9bec\u2014Nature et technologies","doi-asserted-by":"publisher","award":["335893"],"award-info":[{"award-number":["335893"]}],"id":[{"id":"10.13039\/501100003151","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present Synesth, the most comprehensive and flexible tool for tree reconciliation that allows for events on syntenies (i.e., on sets of multiple genes), including duplications, transfers, fissions, and transient events going through unsampled species. This model allows for building histories that explicate the inconsistencies between a synteny tree and its associated species tree. We examine the combinatorial properties of this extended reconciliation model and study various associated parsimony problems. First, the infinite set of explicatory histories is reduced to a finite but exponential set of Pareto-optimal histories (in terms of counts of each event type), then to a polynomial set of Pareto-optimal event count vectors, and this eventually ends with minimum event cost histories given an event cost function. An inductive characterization of the solution space using different algebras for each granularity leads to efficient dynamic programming algorithms, ultimately ending with an O(mn) time complexity algorithm for computing the cost of a minimum-cost history (m and n: number of nodes in the input synteny and species trees). This time complexity matches that of the fastest known algorithms for classical gene reconciliation with transfers. We show how Synesth can be applied to infer Pareto-optimal evolutionary scenarios for CRISPR-Cas systems in a set of bacterial genomes.<\/jats:p>","DOI":"10.3390\/a17050186","type":"journal-article","created":{"date-parts":[[2024,4,29]],"date-time":"2024-04-29T10:33:36Z","timestamp":1714386816000},"page":"186","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Synesth: Comprehensive Syntenic Reconciliation with Unsampled Lineages"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4561-683X","authenticated-orcid":false,"given":"Matt\u00e9o","family":"Delabre","sequence":"first","affiliation":[{"name":"D\u00e9partement d\u2019Informatique et de Recherche Op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, 2920 Chemin de la Tour, Montr\u00e9al, QC H3T 1J4, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[{"name":"D\u00e9partement d\u2019Informatique et de Recherche Op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, 2920 Chemin de la Tour, Montr\u00e9al, QC H3T 1J4, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2024,4,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1093\/sysbio\/28.2.132","article-title":"Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences","volume":"28","author":"Goodman","year":"1979","journal-title":"Syst. Biol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"i283","DOI":"10.1093\/bioinformatics\/bts225","article-title":"Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss","volume":"28","author":"Bansal","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Donati, B., Baudet, C., Sinaimeri, B., Crescenzi, P., and Sagot, M.F. (2015). EUCALYPT: Efficient tree reconciliation enumerator. Algorithms Mol. Biol., 10.","DOI":"10.1186\/s13015-014-0031-3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1109\/TCBB.2010.14","article-title":"Simultaneous identification of duplications and lateral gene transfers","volume":"8","author":"Tofigh","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_5","unstructured":"El-Mabrouk, N., and Noutahi, E. (2019). Bioinformatics and Phylogenetics, Springer International Publishing."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1093\/gbe\/evx069","article-title":"DeCoSTAR: Reconstructing the ancestral organization of genes or genomes using reconciled phylogenies","volume":"9","author":"Duchemin","year":"2017","journal-title":"Genome Biol. Evol."},{"key":"ref_7","unstructured":"Duchemin, W. (2017). Phylogeny of Dependencies and Dependencies of Phylogenies in Genes and Genomes. [Ph.D. Thesis, Universit\u00e9 de Lyon]."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Dondi, R., Lafond, M., and Scornavacca, C. (2019). Reconciling multiple genes trees via segmental duplications and losses. Algorithms Mol. Biol., 14.","DOI":"10.1186\/s13015-019-0139-6"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1109\/TCBB.2017.2706679","article-title":"Efficient algorithms for genomic duplication models","volume":"15","author":"Paszek","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Delabre, M., El-Mabrouk, N., Huber, K.T., Lafond, M., Moulton, V., Noutahi, E., and Castellanos, M.S. (2020). Evolution through segmental duplications and losses: A super-reconciliation approach. Algorithms Mol. Biol., 15.","DOI":"10.1186\/s13015-020-00171-4"},{"key":"ref_11","unstructured":"Anselmetti, Y., Delabre, M., and El-Mabrouk, N. (2022). Comparative Genomics, Springer International Publishing."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"2056","DOI":"10.1093\/bioinformatics\/btw105","article-title":"ecceTERA: Comprehensive gene tree-species tree reconciliation using parsimony","volume":"32","author":"Jacox","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1093\/sysbio\/syt003","article-title":"Lateral gene transfer from the dead","volume":"62","author":"Tannier","year":"2013","journal-title":"Syst. Biol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Weiner, S., and Bansal, M.S. (2021). Improved duplication-transfer-loss reconciliation with extinct and unsampled lineages. Algorithms, 14.","DOI":"10.3390\/a14080231"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"i87","DOI":"10.1093\/bioinformatics\/btu289","article-title":"Pareto-optimal phylogenetic tree reconciliation","volume":"30","author":"Wu","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1038\/nature09649","article-title":"Rapid evolutionary innovation during an Archaean genetic expansion","volume":"469","author":"David","year":"2011","journal-title":"Nature"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Libeskind-Hadas, R. (2022). Tree reconciliation methods for host-symbiont cophylogenetic analyses. Life, 12.","DOI":"10.3390\/life12030443"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1186\/s13015-015-0051-7","article-title":"Pareto optimization in algebraic dynamic programming","volume":"10","author":"Saule","year":"2015","journal-title":"Algorithms Mol. Biol."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1038\/s41579-019-0299-x","article-title":"Evolutionary classification of CRISPR\u2013Cas systems: A burst of class 2 and derived variants","volume":"18","author":"Makarova","year":"2020","journal-title":"Nat. Rev. Microbiol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1126\/science.abe0511","article-title":"A rooted phylogeny resolves early bacterial evolution","volume":"372","author":"Coleman","year":"2021","journal-title":"Science"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Koonin, E.V., and Makarova, K.S. (2022). Evolutionary plasticity and functional versatility of CRISPR systems. PLoS Biol., 20.","DOI":"10.1371\/journal.pbio.3001481"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Scornavacca, C., and Weller, M. (2022). Treewidth-based algorithms for the small parsimony problem on networks. Algorithms Mol. Biol., 17.","DOI":"10.1186\/s13015-022-00216-w"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/186\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:36:20Z","timestamp":1760106980000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/5\/186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,29]]},"references-count":22,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2024,5]]}},"alternative-id":["a17050186"],"URL":"https:\/\/doi.org\/10.3390\/a17050186","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,29]]}}}