{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:58:59Z","timestamp":1760234339890,"version":"build-2065373602"},"reference-count":144,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T00:00:00Z","timestamp":1620691200000},"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":["XXX"],"award-info":[{"award-number":["XXX"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Syntenies are genomic segments of consecutive genes identified by a certain conservation in gene content and order. The notion of conservation may vary from one definition to another, the more constrained requiring identical gene contents and gene orders, while more relaxed definitions just require a certain similarity in gene content, and not necessarily in the same order. Regardless of the way they are identified, the goal is to characterize homologous genomic regions, i.e., regions deriving from a common ancestral region, reflecting a certain gene co-evolution that can enlighten important functional properties. In addition of being able to identify them, it is also necessary to infer the evolutionary history that has led from the ancestral segment to the extant ones. In this field, most algorithmic studies address the problem of inferring rearrangement scenarios explaining the disruption in gene order between segments with the same gene content, some of them extending the evolutionary model to gene insertion and deletion. However, syntenies also evolve through other events modifying their content in genes, such as duplications, losses or horizontal gene transfers, i.e., the movement of genes from one species to another. Although the reconciliation approach between a gene tree and a species tree addresses the problem of inferring such events for single-gene families, little effort has been dedicated to the generalization to segmental events and to syntenies. This paper reviews some of the main algorithmic methods for inferring ancestral syntenies and focus on those integrating both gene orders and gene trees.<\/jats:p>","DOI":"10.3390\/a14050152","type":"journal-article","created":{"date-parts":[[2021,5,11]],"date-time":"2021-05-11T22:53:40Z","timestamp":1620773620000},"page":"152","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Predicting the Evolution of Syntenies\u2014An Algorithmic Review"],"prefix":"10.3390","volume":"14","author":[{"given":"Nadia","family":"El-Mabrouk","sequence":"first","affiliation":[{"name":"D\u00e9partement d\u2019Informatique et de Recherche Op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, CP 6128 succ Centre-Ville, Montreal, QC H3C 3J7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,11]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1643","DOI":"10.1093\/molbev\/msv029","article-title":"Evolution of tRNA Repertoires in Bacillus Inferred with OrthoAlign","volume":"32","author":"Benzaid","year":"2015","journal-title":"Mol. Biol. Evol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"132","DOI":"10.2307\/2412519","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. Zool."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2148-8-184","article-title":"Early vertebrate chromosome duplications and the evolution of the neuropeptide Y receptor gene regions","volume":"8","author":"Larsson","year":"2008","journal-title":"BMC Evol. Biol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2148-7-239","article-title":"An insight into the phylogenetic history of HOX linked gene families in vertebrates","volume":"7","author":"Abbasi","year":"2007","journal-title":"BMC Evol. Biol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"36","DOI":"10.3389\/fevo.2016.00036","article-title":"Evolution of Homeobox Gene Clusters in Animals:The Giga-Cluster and Primary vs. Secondary Clustering","volume":"4","author":"Ferrier","year":"2016","journal-title":"Front. Ecol. Evol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1038\/nrg1723","article-title":"The genesis and evolution of Homeobox gene clusters","volume":"6","year":"2005","journal-title":"Nat. Rev. Genet."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.ympev.2014.09.009","article-title":"Phylogenetic investigation of human FGFR-bearing paralogons favors piecemeal duplication theory of vertebrate genome evolution","volume":"81","author":"Ajmal","year":"2014","journal-title":"Mol. Phylogenet. Evol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.ympev.2015.08.019","article-title":"Phylogenomic analysis reveals ancient segmental duplications in the human genome","volume":"94","author":"Hafeez","year":"2016","journal-title":"Mol. Phylogenet. Evol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"15487","DOI":"10.1073\/pnas.0805590105","article-title":"Evolution of vertebrate opioid receptors","volume":"105","author":"Dreborg","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.2741\/3306","article-title":"The evolution of vertebrate opioid receptors","volume":"14","author":"Stevens","year":"2009","journal-title":"Front. Biosci. J. Virtual Libr."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Sundstrom, G., Dreborg, S., and Larhammar, D. (2010). Concomitant Duplications of Opioid Peptide and Receptor Genes before the Origin of Jawed Vertebrates. PLoS ONE, 5.","DOI":"10.1371\/journal.pone.0010512"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ympev.2017.02.015","article-title":"An insight into the evolutionary history of human MHC paralogon","volume":"110","author":"Naz","year":"2017","journal-title":"Mol. Phylogenet. Evol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/PL00006499","article-title":"Phylogenies of developmentally important proteins do not support the hypothesis of two rounds of genome duplication early in vertebrate history","volume":"48","author":"Hughes","year":"1999","journal-title":"J. Mol. Evol."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1458","DOI":"10.1093\/bioinformatics\/btt150","article-title":"MCScanX-transposed: Detecting transposed gene duplications based on multiple colinearity scans","volume":"29","author":"Wang","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0168-9525(01)02241-7","article-title":"Transcription unit conservation in the three domains of life: A perspective from Escherichia coli","volume":"17","author":"Trevino","year":"2001","journal-title":"Trends Genet."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/s00239-004-0198-1","article-title":"The Origin and Evolution of Operons: The Piecewise Building of the Proteobacterial Histidine Operon","volume":"60","author":"Fani","year":"2005","journal-title":"J. Mol. Evol."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"El-Mabrouk, N., and Noutahi, E. (2019). Bioinformatics and Phylogenetics, Seminal Contributions of Bernard Moret, Springer. Computational Biology, Chapter Gene Family Evolution: An Algorithmic Framework.","DOI":"10.1007\/978-3-030-10837-3_5"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Anselmetti, Y., Luhmann, N., B\u00e9rard, S., E, E.T., and Chauve, C. (2017). Comparative Genomics. Methods in Molecular Biology, Humana Press. Chapter Comparative Methods for Reconstructing Ancient Genome Organization.","DOI":"10.1007\/978-1-4939-7463-4_13"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-13-S19-S4","article-title":"A flexible ancestral genome reconstruction method based on gapped adjacencies","volume":"13","author":"Gagnon","year":"2012","journal-title":"BMC Bioinform."},{"key":"ref_20","first-page":"397","article-title":"Methods in Molecular Biology","volume":"Volume 855","author":"Sankoff","year":"2012","journal-title":"Evolutionary Genomics: Statistical and Computational Methods"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Chauve, C., El-Mabrouk, N., Gueguen, L., Semeria, M., and Tannier, E. (2013). Models and Algorithms for Genome Evolution, Springer. Computational Biology, Chapter Duplication, Rearrangement and Reconciliation: A Follow-Up 13 Years Later.","DOI":"10.1007\/978-1-4471-5298-9_4"},{"key":"ref_22","unstructured":"Grouchy, J., Ebling, F., and Henderson, I. (1972). Human Genetics, Excerpta Medica."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1038\/70486","article-title":"Incorrect use of the term synteny","volume":"23","author":"Passarge","year":"1999","journal-title":"Nat. Genet."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1186\/gb-2000-1-6-research0011","article-title":"Evidence for symmetric chromosomal inversions around the replication origin in bacteria","volume":"1","author":"Eisen","year":"2000","journal-title":"Genome Biol."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1073\/pnas.81.3.814","article-title":"Lengths of chromosomal segments conserved since divegence of man and mouse","volume":"81","author":"Nadeau","year":"1984","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1093\/gbe\/evaa063","article-title":"An Annotated Chromosome-Level Reference Genome of the Red-Eared Slider Turtle","volume":"12","author":"Simison","year":"2020","journal-title":"Genome Biol. Evol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2747","DOI":"10.1093\/molbev\/msaa114","article-title":"Phylogenetic Reconstruction Based on Synteny Block and Gene Adjacencies","volume":"37","author":"Drillon","year":"2020","journal-title":"Mol. Biol. Evol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"17626","DOI":"10.1073\/pnas.0605426103","article-title":"Recurrent duplication-driven transpositionof DNA during hominoid evolution","volume":"103","author":"Johnson","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1803","DOI":"10.3389\/fpls.2017.01803","article-title":"Conservation and Dispersion of Genes Conferring Resistance to Tomato Begomoviruses between Tomato and Pepper Genomes","volume":"8","author":"Mangal","year":"2017","journal-title":"Front. Plant Sci."},{"key":"ref_30","unstructured":"Mandoiu, I., and Zelikovsky, A. (2008). Formal models of gene clusters. Bioinformatics Algorithms: Techniques and Applications, Wiley. Chapter 8."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1340","DOI":"10.1089\/cmb.2006.13.1340","article-title":"On the similarity of sets of permutations and its applications to genome comparison","volume":"13","author":"Bergeron","year":"2003","journal-title":"J. Comput. Biol."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/3-540-48194-X_19","article-title":"Finding all common intervals of k permutations. Lecture Notes in Computer Science","volume":"Volume 2089","author":"Amir","year":"2001","journal-title":"Combinatorial Pattern Matching"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/s004539910014","article-title":"Fast algorithms to enumerate all common intervals of two permutations","volume":"26","author":"Uno","year":"2000","journal-title":"Algorithmica"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1089\/cmb.2005.12.1289","article-title":"Gene proximity analysis across whole genomes via PQ trees","volume":"12","author":"Landau","year":"2005","journal-title":"J. Comput. Biol."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1007\/3-540-45784-4_36","article-title":"The algorithmic of gene teams","volume":"Volume 2452","author":"Gusfield","year":"2002","journal-title":"Workshop on Algorithms in Bioinformatics"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1089\/cmb.2010.0099","article-title":"Natural Parameter Values for Generalized Gene Adjacency","volume":"17","author":"Yang","year":"2010","journal-title":"J. Comput. Biol."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1109\/TCBB.2008.121","article-title":"Generalized Gene Adjacencies, Graph Bandwidth, and Clusters in Yeast Evolution","volume":"6","author":"Zhu","year":"2009","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1101\/gr.757503","article-title":"Genome rearrangements in mammalian evolution: Lessons from human and mouse genomic sequences","volume":"13","author":"Pevzner","year":"2003","journal-title":"Genome Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"2509","DOI":"10.1093\/bioinformatics\/btq465","article-title":"DRIMM-Synteny: Decomposing genomes into evolutionary conserved segments","volume":"26","author":"Pham","year":"2010","journal-title":"Bioinformatics"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1089\/106652701753216503","article-title":"A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study","volume":"8","author":"Bader","year":"2001","journal-title":"J. Comput. Biol."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/978-3-540-27801-6_29","article-title":"Reversal Distance without Hurdles and Fortresses","volume":"Volume 3109","author":"Sahinalp","year":"2004","journal-title":"Combinatorial Pattern Matching"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1016\/S0022-0000(02)00011-9","article-title":"Efficient algorithms for multichromosomal genome rearrangements","volume":"65","author":"Tesler","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","article-title":"SCJ: A breakpoint-like distance that simplifies several rearrangement problem","volume":"8","author":"Feijao","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","article-title":"Efficient sorting of genomic permutations by translocation, inversion and block interchange","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/110851390","article-title":"Sorting by transpositions is difficult","volume":"26","author":"Bulteau","year":"2012","journal-title":"SIAM J. Discret. Math."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Silva, L., Kowada, L., Rocco, N., and Walter, M. (2021). An Algebraic 1.375-Approximation Algorithm for the Transposition Distance Problem, Elsevier. Submitted.","DOI":"10.1186\/s13015-022-00205-z"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Sankoff, D. (1975). Minimal mutation trees of sequences. SIAM J. Appl. Math., 28.","DOI":"10.1137\/0128004"},{"key":"ref_48","unstructured":"Pe\u2019er, I., and Shamir, R. (1998). The median problems for breakpoints are NP-complete. BMC Bioinform., 5, Available online: https:\/\/www.researchgate.net\/profile\/Ron-Shamir\/publication\/220138763_The_median_problems_for_breakpoints_are_NP-complete\/links\/02bfe50e41b4bbed55000000\/The-median-problems-for-breakpoints-are-NP-complete.pdf."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","article-title":"Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals)","volume":"48","author":"Hannenhalli","year":"1999","journal-title":"J. ACM"},{"key":"ref_50","first-page":"26","article-title":"Genome-Scale Evolution: Reconstructing Gene Orders in the Ancestral Species","volume":"12","author":"Bourque","year":"2002","journal-title":"Genome Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1101\/gr.082784.108","article-title":"Breakpoint graphs and ancestral genome reconstructions","volume":"19","author":"Alekseyev","year":"2009","journal-title":"Genome Res."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Xu, A., and Moret, B. (2011). GASTS: Parsimony Scoring under Rearrangements. Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-642-23038-7_29"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Zheng, C., and Sankoff, D. (2011). On the PATHGROUPS approach to rapid small phylogeny. BMC Bioinform., 12.","DOI":"10.1186\/1471-2105-12-S1-S4"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Kovac, J., Brejova, B., and Vinar, T. (2011). A practical algorithm for ancestral rearrangement reconstruction. International Workshop on Algorithms in Bioinformatics, Springer.","DOI":"10.1007\/978-3-642-23038-7_15"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Shao, M., and Lin, Y. (2012). Approximating the edit distance for genomes with duplicate genes under DCJ, insertion and deletion. BMC Bioinform., 13.","DOI":"10.1186\/1471-2105-13-S19-S13"},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Willing, E., Zaccaria, S., Braga, M., and Stoye, J. (2013). On the inversion-indel distance. BMC Bioinform., 14.","DOI":"10.1186\/1471-2105-14-S15-S3"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1089\/cmb.2011.0118","article-title":"Double cut and join with insertions and deletions","volume":"18","author":"Braga","year":"2011","journal-title":"J. Comput. Biol."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-8-6","article-title":"DCJ-indel sorting revisited","volume":"8","author":"Compeau","year":"2013","journal-title":"Algorithms Mol. Biol."},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1089\/cmb.2015.0160","article-title":"Reconstruction of Ancestral Genomes in Presence of Gene Gain and Loss","volume":"23","author":"Avdeyev","year":"2016","journal-title":"J. Comput. Biol."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-017-1944-x","article-title":"Chromosome structures: Reduction of certain problems with unequal gene content and gene paralogs to integer linear programming","volume":"18","author":"Lyubetsky","year":"2017","journal-title":"BMC Bioinform."},{"key":"ref_61","unstructured":"Istrail, S., Pevzner, P., and Waterman, M. (2009). Combinatorics of Genome Rearrangements, The MIT Press."},{"key":"ref_62","doi-asserted-by":"crossref","unstructured":"Bryant, D. (2000). Comparative Genomics, Kluwer Academic. Chapter the Complexity of Calculating Exemplar Distances.","DOI":"10.1007\/978-94-011-4309-7_19"},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Bulteau, L., and Jiang, M. (2013). Inapproximability of (1,2)-exemplar distance. IEEE\/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers and Association for Computing Machinery.","DOI":"10.1109\/TCBB.2012.144"},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","article-title":"Genome rearrangement with gene families","volume":"15","author":"Sankoff","year":"1999","journal-title":"Bioinformatics"},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1007\/s10878-015-9940-4","article-title":"Exemplar or matching: Modeling DCJ problems with unequal content genome data","volume":"32","author":"Yin","year":"2016","journal-title":"J. Comb. Optim."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(96)00268-X","article-title":"Block edit models for approximate string matching","volume":"181","author":"Lorespi","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"ref_67","first-page":"97","article-title":"Aligning and Labeling Genomes Under the Duplication-Loss Model","volume":"Volume 7921","author":"Dondi","year":"2013","journal-title":"Computability in Europe (CiE)"},{"key":"ref_68","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1089\/cmb.2012.0292","article-title":"Ancestral Genome Organization: An Alignment Approach","volume":"20","author":"Holloway","year":"2013","journal-title":"J. Comput. Biol."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1089\/cmb.2013.0057","article-title":"The Duplication-Loss Small Phylogeny Problem: From Cherries to Trees","volume":"20","author":"Andreotti","year":"2013","journal-title":"J. Comput. Biol."},{"key":"ref_70","unstructured":"Benzaid, B., Dondi, R., and El-Mabrouk, N. (2019, January 26\u201329). Duplication-Loss Genome Alignment: Complexity and Algorithm. Proceedings of the 13th International Conference, LATA 2019, Petersburg, Russia."},{"key":"ref_71","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.2020.0434","article-title":"Computing the Rearrangement Distance of Natural Genomes","volume":"28","author":"Bohnenkamper","year":"2021","journal-title":"J. Comput. Biol."},{"key":"ref_72","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1089\/cmb.2014.0096","article-title":"An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes","volume":"22","author":"Shao","year":"2015","journal-title":"J. Comput. Biol."},{"key":"ref_73","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-017-0095-y","article-title":"Approximating the DCJ distance of balanced genomes in linear time","volume":"12","author":"Rubert","year":"2017","journal-title":"Algorithms Mol. Biol."},{"key":"ref_74","doi-asserted-by":"crossref","first-page":"14254","DOI":"10.1073\/pnas.0805217105","article-title":"The infinite sites model of genome evolution","volume":"105","author":"Ma","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_75","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-15-206","article-title":"A unifying model of genome evolution under parsimony","volume":"15","author":"Paten","year":"2014","journal-title":"BMC Bioinform."},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1080\/10635150390235520","article-title":"A simple, fast and accurate algorithm to estimate large phylogenies by maximum likelihood","volume":"52","author":"Guindon","year":"2003","journal-title":"Syst. Biol."},{"key":"ref_77","doi-asserted-by":"crossref","first-page":"2688","DOI":"10.1093\/bioinformatics\/btl446","article-title":"RAxML-VI-HPC: Maximum likelihood-based phylogenetic analysis with thousands of taxa and mixed models","volume":"22","author":"Stamatakis","year":"2006","journal-title":"Bioinformatics"},{"key":"ref_78","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1093\/bioinformatics\/btg180","article-title":"MrBayes3: Bayesian phylogenetic inference under mixed models","volume":"19","author":"Ronquist","year":"2003","journal-title":"Bioinformatics"},{"key":"ref_79","doi-asserted-by":"crossref","unstructured":"Schreiber, F., Patricio, M., Muffato, M., Pignatelli, M., and Bateman, A. (2013). TreeFam v9: A new website, more species and orthology-on-the-fly. Nucleic Acids Res.","DOI":"10.1093\/nar\/gkt1055"},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1101\/gr.141978.112","article-title":"Genome-scale coestimation of species and gene trees","volume":"23","author":"Boussau","year":"2013","journal-title":"Genome Res."},{"key":"ref_81","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1093\/sysbio\/syt054","article-title":"Efficient exploration of the space of reconciled gene trees","volume":"62","author":"Rosikiewicz","year":"2013","journal-title":"Syst. Biol."},{"key":"ref_82","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1101\/gr.073585.107","article-title":"EnsemblCompara gene trees: Complete, duplication-aware phylogenetic trees in vertebrates","volume":"19","author":"Vilella","year":"2009","journal-title":"Genome Res."},{"key":"ref_83","doi-asserted-by":"crossref","first-page":"D556","DOI":"10.1093\/nar\/gkq1109","article-title":"PhylomeDB v3.0: An expanding repository of genome-wide collections of trees, alignments and phylogeny-based orthology and paralogy predictions","volume":"39","author":"Pryszcz","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"D377","DOI":"10.1093\/nar\/gks1118","article-title":"PANTHER in 2013: Modeling the evolution of gene function, and other gene attributes, in the context of phylogenetic trees","volume":"41","author":"Mi","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"ref_85","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1089\/106652700750050871","article-title":"Notung: Dating Gene Duplications using Gene Family Trees","volume":"7","author":"Chen","year":"2000","journal-title":"J. Comput. Biol."},{"key":"ref_86","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1089\/cmb.1997.4.177","article-title":"On a Mirkin-Muchnik-Smith conjecture for comparing molecular phylogenies","volume":"4","author":"Zhang","year":"1997","journal-title":"J. Comput. Biol."},{"key":"ref_87","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1093\/bioinformatics\/17.9.821","article-title":"A simple algorithm to infer gene duplication and speciiation events on a gene tree","volume":"17","author":"Zmasek","year":"2001","journal-title":"Bioinformatics"},{"key":"ref_88","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1093\/bioinformatics\/bts374","article-title":"Evolution of gene neighborhoods within reconciled phylogenies","volume":"28","author":"Gallien","year":"2012","journal-title":"Bioinformatics"},{"key":"ref_89","doi-asserted-by":"crossref","unstructured":"Noutahi, E., Semeria, M., Lafond, M., Seguin, J., Boussau, B., Gueguen, L., El-Mabrouk, N., and Tannier, E. (2016). Efficient Gene Tree Correction Guided by Genome Evolution. PLoS ONE, 11.","DOI":"10.1371\/journal.pone.0159559"},{"key":"ref_90","doi-asserted-by":"crossref","unstructured":"Patterson, M., Szollosi, G., Daubin, V., and Tannier, E. (2013). Lateral gene transfer, rearrangement, reconciliation. BMC Bioinform., 14.","DOI":"10.1186\/1471-2105-14-S15-S4"},{"key":"ref_91","doi-asserted-by":"crossref","unstructured":"Anselmetti, Y., Berry, V., Chauve, C., Chateau, A., Tannier, E., and B\u00e9rard, S. (2015). Ancestral gene synteny reconstruction improves extant species scaffolding. BMC Genom., 16.","DOI":"10.1186\/1471-2164-16-S10-S11"},{"key":"ref_92","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":"W","year":"2017","journal-title":"Genome Biol. Evol."},{"key":"ref_93","unstructured":"Duchemin, W. (2017). Phylogeny of Dependencies and Dependencies of Phylogenies in Genes and Genomes. [Ph.D. Thesis, Universit\u00e9 de Lyon]."},{"key":"ref_94","doi-asserted-by":"crossref","unstructured":"Delabre, M., El-Mabrouk, N., Huber, K., Lafond, M., Mouton, V., Noutahi, E., and Castellanos, M. (2018). Reconstructing the History of Syntenies Through Super-Reconciliation. RECOMB-CG, Springer.","DOI":"10.1007\/978-3-030-00834-5_10"},{"key":"ref_95","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1186\/s13015-020-00171-4","article-title":"Evolution through segmental duplications and losses: A super-Reconciliation approach","volume":"15","author":"Delabre","year":"2020","journal-title":"Algorithms Mol. Biol."},{"key":"ref_96","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","article-title":"Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions","volume":"10","author":"Aho","year":"1981","journal-title":"SIAM J. Comput."},{"key":"ref_97","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01202270","article-title":"An efficient algorithm for supertrees","volume":"12","author":"Constantinescu","year":"1995","journal-title":"J. Classif."},{"key":"ref_98","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0166-218X(95)00074-2","article-title":"Reconstruction of rooted trees from subtrees","volume":"69","author":"Ng","year":"1996","journal-title":"Discret. Appl. Math."},{"key":"ref_99","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/S0166-218X(02)00250-0","article-title":"Reconstructing minimal rooted trees","volume":"127","author":"Semple","year":"2003","journal-title":"Discret. Appl. Math."},{"key":"ref_100","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1090\/dimacs\/061\/11","article-title":"A classification of consensus methods for phylogenetics","volume":"61","author":"Bryant","year":"2003","journal-title":"DIMACS Ser. Discret. Math. Theor. Comput. Sci."},{"key":"ref_101","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.tcs.2018.08.006","article-title":"The complexity of comparing multiply-labelled trees by extending phylogenetic-tree metrics","volume":"760","author":"Lafond","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_102","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1137\/100811489","article-title":"The complexity of inferring a minimally resolved phylogenetic supertree","volume":"41","author":"Jansson","year":"2012","journal-title":"SIAM J. Comput."},{"key":"ref_103","doi-asserted-by":"crossref","unstructured":"Huber, K., Moulton, V., and Spillner, A. (2012, January 16). Computing a consensus of multilabeled trees. Proceedings of the 14th Workshop on Algorithm Engineering and Experiments (ALENEX 2012), Kyoto, Japan.","DOI":"10.1137\/1.9781611972924.9"},{"key":"ref_104","doi-asserted-by":"crossref","unstructured":"Lott, M., Spillner, A., and Huber, K. (2009). Inferring polyploid phylogenies from multiply-labeled gene trees. BMC Evol. Biol., 9.","DOI":"10.1186\/1471-2148-9-216"},{"key":"ref_105","doi-asserted-by":"crossref","unstructured":"Gascon, M., Dondi, R., and El-Mabrouk, N. (2021, January 5\u20137). Complexity and algorithm for MUL-tree pruning. Proceedings of the IWOCA 2021\u201432nd International Workshop on Combinatorial Algorithms, Ottawa, ON, Canada. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-030-79987-8_23"},{"key":"ref_106","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":"2017","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_107","doi-asserted-by":"crossref","unstructured":"Fellows, M., Hallet, M., and Stege, U. (1998, January 14\u201316). On the multiple gene duplication problem. Proceedings of the 9th International Symposium on Algorithms and Computation, Taejon, Korea.","DOI":"10.1007\/3-540-49381-6_37"},{"key":"ref_108","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1186\/s12864-015-2308-4","article-title":"Genomic duplication problems for unrooted gene trees","volume":"17","author":"Paszek","year":"2016","journal-title":"BMC Genom."},{"key":"ref_109","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1006\/mpev.1996.0071","article-title":"Reconstruction of Ancient Molecular Phylogeny","volume":"6","author":"Guigo","year":"1996","journal-title":"Mol. Phylogenet. Evol."},{"key":"ref_110","unstructured":"Czabarka, E., Szk\u00e9ly, L., and Vision, T. (2012). Minimizing the number of episodes and Gallai\u2019s theorem on intervals. arXiv."},{"key":"ref_111","unstructured":"Page, R., and Cotton, J. (2002). Vertebrate Phylogenomics: Reconciled Trees and Gene Duplications. Pac. Symp. Biocomput., 536\u2013547."},{"key":"ref_112","doi-asserted-by":"crossref","first-page":"i132","DOI":"10.1093\/bioinformatics\/btn150","article-title":"The multiple gene duplicationproblem revisited","volume":"24","author":"Bansal","year":"2008","journal-title":"Bioinformatics"},{"key":"ref_113","unstructured":"Burleigh, J.G., Bansal, M.S., Wehe, A., and Eulenstein, O. (April, January 30). Locating multiple gene duplications through reconciled trees. Proceedings of the Research in Computational Molecular Biology, Singapore."},{"key":"ref_114","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/TCBB.2009.52","article-title":"Linear-time algorithms for the multiple gene duplication problems","volume":"8","author":"Luo","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_115","doi-asserted-by":"crossref","unstructured":"Paszek, J., and G\u00f3recki, P. (2018). Inferring duplication episodes from unrooted gene trees. BMC Genom., 19.","DOI":"10.1186\/s12864-018-4623-z"},{"key":"ref_116","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-019-0139-6","article-title":"Reconciling Multiple Genes Trees via Segmental Duplications and Losses","volume":"14","author":"Dondi","year":"2019","journal-title":"Algorithms Mol. Biol."},{"key":"ref_117","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1007\/s11103-010-9705-5","article-title":"The amplification and evolution of orthologous 22-kDa \u03b1-prolamin tandemly arrayed genes in coix, sorghum and maize genomes","volume":"74","author":"Zhou","year":"2010","journal-title":"Plant Mol. Biol."},{"key":"ref_118","doi-asserted-by":"crossref","first-page":"2134","DOI":"10.1093\/molbev\/msl085","article-title":"A Roadmap of Tandemly Arrayed Genes in the Genomes of Human, Mouse, and Rat","volume":"23","author":"Shoja","year":"2006","journal-title":"Mol. Biol. Evol."},{"key":"ref_119","doi-asserted-by":"crossref","unstructured":"Ciccarelli, F., and Mikl\u00f3s, I. (2009). Inferring the recent duplication history of a gene cluster. Comparative Genomics, Springer.","DOI":"10.1007\/978-3-642-04744-2"},{"key":"ref_120","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1089\/cmb.2010.0090","article-title":"Reconstructing Histories of Complex Gene Clusters on a Phylogeny","volume":"17","author":"Song","year":"2010","journal-title":"J. Comput. Biol."},{"key":"ref_121","unstructured":"Zhang, Y., Song, G., Hsu, C., and Miller, W. (2021, April 08). Simultaneous History Reconstruction for Complex Gene Clusters in Multiple Species. Available online: https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/9789812836939_0016."},{"key":"ref_122","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1093\/genetics\/86.3.623","article-title":"Phylogenies constrained by cross-over process as illustrated by human hemoglobins and a thirteen-cycle, eleven amino-acid repeat in human apolipoprotein A-I","volume":"86","author":"Fitch","year":"1977","journal-title":"Genetics"},{"key":"ref_123","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1109\/TCBB.2005.15","article-title":"Topological rearrangements and local search method for tandem duplication trees","volume":"2","author":"Bertrand","year":"2005","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_124","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1089\/cmb.2008.0025","article-title":"Inferring Ancestral Gene Orders for a Family of Tandemly Arrayed Genes","volume":"15","author":"Bertrand","year":"2008","journal-title":"J. Comput. Biol."},{"key":"ref_125","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1089\/cmb.2008.0069","article-title":"DUPCAR: Reconstructing Contiguous Ancestral Regions with Duplication","volume":"15","author":"Ma","year":"2008","journal-title":"J. Comput. Biol."},{"key":"ref_126","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1093\/molbev\/msp271","article-title":"Inferring the Evolutionary History of Gene Clusters from Phylogenetic and Gene Order Data","volume":"27","author":"Lajoie","year":"2010","journal-title":"Mol. Biol. Evol."},{"key":"ref_127","doi-asserted-by":"crossref","unstructured":"Savard, O.T., Bertrand, D., and El-Mabrouk, N. (2011). Evolution of orthologous tandemly arrayed gene clusters. BMC Bioinform., 12.","DOI":"10.1186\/1471-2105-12-S9-S2"},{"key":"ref_128","first-page":"93","article-title":"An efficient algo. for gene\/species trees parsimonious reconciliation with losses, duplications and transfers","volume":"Volume 6398","author":"Doyon","year":"2010","journal-title":"RECOMB-CG"},{"key":"ref_129","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1093\/bib\/bbr045","article-title":"Models, algorithms and programs for phylogeny reconciliation","volume":"12","author":"Doyon","year":"2011","journal-title":"Briefings Bioinform."},{"key":"ref_130","doi-asserted-by":"crossref","unstructured":"Hallett, M., and Lagergren, J. (2001, January 22\u201325). Efficient algorithms for lateral gene transfer problems. Proceedings of the the Fifth Annual International Conference on Computational Biology, Montreal, QC, Canada.","DOI":"10.1145\/369133.369188"},{"key":"ref_131","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1089\/cmb.2009.0240","article-title":"The cophylogeny reconstruction problem is NP-complete","volume":"18","author":"Ovadia","year":"2011","journal-title":"J. Comput. Biol."},{"key":"ref_132","doi-asserted-by":"crossref","first-page":"283","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_133","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. Bioinform."},{"key":"ref_134","unstructured":"Tofigh, A. (2009). Using Trees to Capture Reticulate Evolution: Lateral Gene Transfers and Cancer Progression. [Ph.D. Thesis, KTH Royal Institute of Technology]."},{"key":"ref_135","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_136","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1089\/cmb.2008.0084","article-title":"On the computational complexity of the reticulate cophylogeny reconstruction problem","volume":"16","author":"Charleston","year":"2009","journal-title":"J. Comput. Biol."},{"key":"ref_137","doi-asserted-by":"crossref","unstructured":"Anselmetti, Y., El-Mabrouk, N., Lafond, M., and Ouandraoua, A. (2021, April 08). Gene Tree and Species Tree Reconciliation with Endosymbiotic Gene Transfer. Available online: http:\/\/www-labs.iro.umontreal.ca\/~mabrouk\/Publications\/ISMB2021.pdf.","DOI":"10.1093\/bioinformatics\/btab328"},{"key":"ref_138","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-7-88","article-title":"SIMMAP: Stochastic character mapping of discrete traits onphylogenies","volume":"7","author":"Bollback","year":"2006","journal-title":"BMC Bioinform."},{"key":"ref_139","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1080\/10635150390192780","article-title":"Stochastic mapping of morphological characters","volume":"52","author":"Huelsenbeck","year":"2003","journal-title":"Syst. Biol."},{"key":"ref_140","unstructured":"Simon, D., and Larget, B. (2004). Bayesian Analysis to Describe Genomic Evolution by Rearrangement (BADGER), Department of Mathematics and Computer Science, Duquesne University. Version 1.02 Beta."},{"key":"ref_141","doi-asserted-by":"crossref","first-page":"R1177","DOI":"10.1016\/j.cub.2017.09.015","article-title":"The Origin and Diversification of Mitochondria","volume":"27","author":"Roger","year":"2017","journal-title":"Curr. Biol."},{"key":"ref_142","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1038\/s41576-018-0035-9","article-title":"Cytonuclear integration and co-evolution","volume":"19","author":"Sloan","year":"2018","journal-title":"Nat. Rev. Genet."},{"key":"ref_143","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1534\/genetics.108.100024","article-title":"The Functional Transfer of Genes From the Mitochondria to the Nucleus: The Effects of Selection, Mutation, Population Sizeand Rate of Self-Fertilization","volume":"182","author":"Brandvain","year":"2009","journal-title":"Genetics"},{"key":"ref_144","unstructured":"Kelly, S. (2020). The economics of endosymbiotic gene transfer and the evolution of organellar genomes. bioRxiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/152\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:59:27Z","timestamp":1760162367000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/152"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,11]]},"references-count":144,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5]]}},"alternative-id":["a14050152"],"URL":"https:\/\/doi.org\/10.3390\/a14050152","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,5,11]]}}}