{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T07:40:11Z","timestamp":1749282011367,"version":"3.41.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T00:00:00Z","timestamp":1749254400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T00:00:00Z","timestamp":1749254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e4tsklinikum D\u00fcsseldorf. Anstalt \u00f6ffentlichen Rechts"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>We study the classical problem of inferring ancestral genomes from a set of extant genomes under a given phylogeny, known as the <jats:italic>Small Parsimony Problem<\/jats:italic> (SPP). Genomes are represented as sequences of oriented markers, organized in one or more linear or circular chromosomes. Any marker may appear in several copies, without restriction on orientation or genomic location, known as the <jats:italic>natural genomes<\/jats:italic> model. Evolutionary events along the branches of the phylogeny encompass large scale rearrangements, including segmental inversions, translocations, gain and loss (DCJ-indel model). Even under simpler rearrangement models, such as the classical breakpoint model without duplicates, the SPP is computationally intractable. Nevertheless, the SPP for natural genomes under the DCJ-indel model has been studied recently, with limited success.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Methods<\/jats:title>\n            <jats:p>Building on prior work, we present a highly optimized ILP that is able to solve the SPP for sufficiently small phylogenies and gene families. A notable improvement w.r.t. the previous result is an optimized way of handling both circular and linear chromosomes. This is especially relevant to the SPP, since the chromosomal structure of ancestral genomes is unknown and the solution space for this chromosomal structure is typically large.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We benchmark our method on simulated and real data. On simulated phylogenies we observe a considerable performance improvement on problems that include linear chromosomes. And even when the ground truth contains only one circular chromosome per genome, our method outperforms its predecessor due to its optimized handling of the solution space. The practical advantage becomes also visible in an analysis of seven <jats:italic>Anopheles<\/jats:italic> taxa.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/s13015-025-00279-5","type":"journal-article","created":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T07:09:50Z","timestamp":1749280190000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reconstructing rearrangement phylogenies of natural genomes"],"prefix":"10.1186","volume":"20","author":[{"given":"Leonard","family":"Bohnenk\u00e4mper","sequence":"first","affiliation":[]},{"given":"Jens","family":"Stoye","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Doerr","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,7]]},"reference":[{"issue":"9","key":"279_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1089\/cmb.2011.0118","volume":"18","author":"MDV Braga","year":"2011","unstructured":"Braga MDV, Willing E, Stoye J. Double cut and join with insertions and deletions. J Comput Biol. 2011;18(9):1167\u201384. https:\/\/doi.org\/10.1089\/cmb.2011.0118.","journal-title":"J Comput Biol"},{"issue":"16","key":"279_CR2","doi-asserted-by":"publisher","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"S Yancopoulos","year":"2005","unstructured":"Yancopoulos S, Attie O, Friedberg R. Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics. 2005;21(16):3340\u20136. https:\/\/doi.org\/10.1093\/bioinformatics\/bti535.","journal-title":"Bioinformatics"},{"issue":"4","key":"279_CR3","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1089\/cmb.2020.0434","volume":"28","author":"L Bohnenk\u00e4mper","year":"2021","unstructured":"Bohnenk\u00e4mper L, Braga MDV, Doerr D, Stoye J. Computing the rearrangement distance of natural genomes. J Comput Biol. 2021;28(4):410\u201331. https:\/\/doi.org\/10.1089\/cmb.2020.0434.","journal-title":"J Comput Biol"},{"issue":"06","key":"279_CR4","doi-asserted-by":"publisher","first-page":"2140009","DOI":"10.1142\/S0219720021400096","volume":"19","author":"D Doerr","year":"2021","unstructured":"Doerr D, Chauve C. Small parsimony for natural genomes in the DCJ-indel model. J Bioinform Comput Biol. 2021;19(06):2140009. https:\/\/doi.org\/10.1142\/S0219720021400096.","journal-title":"J Bioinform Comput Biol"},{"key":"279_CR5","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1186\/s13015-023-00238-y","volume":"18","author":"DP Rubert","year":"2023","unstructured":"Rubert DP, Braga MDV. Efficient gene orthology inference via large-scale rearrangements. Algorithms Mol Biol. 2023;18:14. https:\/\/doi.org\/10.1186\/s13015-023-00238-y.","journal-title":"Algorithms Mol Biol"},{"key":"279_CR6","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1186\/s13015-024-00253-7","volume":"19","author":"L Bohnenk\u00e4mper","year":"2024","unstructured":"Bohnenk\u00e4mper L. Recombinations, chains and caps: resolving problems with the DCJ-indel model. Algorithms Mol Biol. 2024;19:8. https:\/\/doi.org\/10.1186\/s13015-024-00253-7.","journal-title":"Algorithms Mol Biol"},{"issue":"5","key":"279_CR7","doi-asserted-by":"publisher","first-page":"152","DOI":"10.3390\/a14050152","volume":"14","author":"N El-Mabrouk","year":"2021","unstructured":"El-Mabrouk N. Predicting the evolution of syntenies-an algorithmic review. Algorithms. 2021;14(5):152. https:\/\/doi.org\/10.3390\/a14050152.","journal-title":"Algorithms"},{"key":"279_CR8","first-page":"247","volume-title":"Comparative genomics methods molecular biology","author":"EP Cribbie","year":"2024","unstructured":"Cribbie EP, Doerr D, Chauve C. AGO, a framework for the reconstruction of ancestral syntenies and gene orders. In: Setubal JC, Stoye J, Stadler PF, editors. Comparative genomics methods molecular biology. New York: Humana; 2024. p. 247\u201365."},{"key":"279_CR9","first-page":"351","volume-title":"GASTS: parsimony scoring under rearrangements","author":"AW Xu","year":"2011","unstructured":"Xu AW, Moret BME. GASTS: parsimony scoring under rearrangements. Berlin: Springer; 2011. p. 351\u201363."},{"issue":"3","key":"279_CR10","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1089\/cmb.2015.0160","volume":"23","author":"P Avdeyev","year":"2016","unstructured":"Avdeyev P, Jiang S, Aganezov S, Hu F, Alekseyev MA. Reconstruction of ancestral genomes in presence of gene gain and loss. J Comput Biol. 2016;23(3):150\u201364. https:\/\/doi.org\/10.1089\/cmb.2015.0160.","journal-title":"J Comput Biol"},{"issue":"3","key":"279_CR11","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1089\/cmb.2017.0157","volume":"25","author":"R Xia","year":"2018","unstructured":"Xia R, Lin Y, Zhou J, Feng B, Tang J. A median solver and phylogenetic inference based on double-cut-and-join sorting. J Comput Biol. 2018;25(3):302\u201312. https:\/\/doi.org\/10.1089\/cmb.2017.0157.","journal-title":"J Comput Biol"},{"issue":"5","key":"279_CR12","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1089\/cmb.2014.0096","volume":"22","author":"M Shao","year":"2015","unstructured":"Shao M, Lin Y, Moret BME. An exact algorithm to compute the double-cut-and-join distance for genomes with duplicate genes. J Comput Biol. 2015;22(5):425\u201335. https:\/\/doi.org\/10.1089\/cmb.2014.0096.","journal-title":"J Comput Biol"},{"key":"279_CR13","doi-asserted-by":"publisher","DOI":"10.1099\/mgen.0.001300","author":"D Frolova","year":"2024","unstructured":"Frolova D, Lima L, Roberts LW, Bohnenk\u00e4mper L, Wittler R, Stoye J, Iqbal Z. Applying rearrangement distances to enable plasmid epidemiology with pling. Microb Genom. 2024. https:\/\/doi.org\/10.1099\/mgen.0.001300.","journal-title":"Microb Genom"},{"issue":"5","key":"279_CR14","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, B\u00e9rard S, Chauve C, Scornavacca C, Daubin V, Tannier E. DeCoSTAR: reconstructing the ancestral organization of genes or genomes using reconciled phylogenies. Genome Biol Evol. 2017;9(5):1312\u20139. https:\/\/doi.org\/10.1093\/gbe\/evx069.","journal-title":"Genome Biol Evol"},{"issue":"4","key":"279_CR15","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1093\/bioinformatics\/btz710","volume":"36","author":"AA Dav\u00edn","year":"2019","unstructured":"Dav\u00edn AA, Tricou T, Tannier E, Vienne DM, Sz\u00f6ll\u0151si GJ. Zombi: a phylogenetic simulator of trees, genomes and sequences that accounts for dead linages. Bioinformatics. 2019;36(4):1286\u20138. https:\/\/doi.org\/10.1093\/bioinformatics\/btz710.","journal-title":"Bioinformatics"},{"issue":"D1","key":"279_CR16","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1093\/nar\/gkab929","volume":"50","author":"B Amos","year":"2021","unstructured":"...Amos B, Aurrecoechea C, Barba M, Barreto A, Basenko EY, Ba\u017cant W, Belnap R, Blevins AS, B\u00f6hme U, Brestelli J, Brunk BP, Caddick M, Callan D, Campbell L, Christensen MB, Christophides GK, Crouch K, Davis K, DeBarry J, Doherty R, Duan Y, Dunn M, Falke D, Fisher S, Flicek P, Fox B, Gajria B, Giraldo-Calder\u00f3n GI, Harb OS, Harper E, Hertz-Fowler C, Hickman MJ, Howington C, Hu S, Humphrey J, Iodice J, Jones A, Judkins J, Kelly SA, Kissinger JC, Kwon DK, Lamoureux K, Lawson D, Li W, Lies K, Lodha D, Long J, MacCallum RM, Maslen G, McDowell MA, Nabrzyski J, Roos DS, Rund SSC, Schulman SW, Shanmugasundram A, Sitnik V, Spruill D, Starns D, Stoeckert CJ Jr, Tomko SS, Wang H, Warrenfeltz S, Wieck R, Wilkinson PA, Xu L, Zheng J. VEuPathDB: the eukaryotic pathogen, vector and host bioinformatics resource center. Nucleic Acids Res. 2021;50(D1):898\u2013911. https:\/\/doi.org\/10.1093\/nar\/gkab929.","journal-title":"Nucleic Acids Res"},{"issue":"10","key":"279_CR17","doi-asserted-by":"publisher","first-page":"2582","DOI":"10.1093\/molbev\/msy159","volume":"35","author":"V Ranwez","year":"2018","unstructured":"Ranwez V, Douzery EJP, Cambon C, Chantret N, Delsuc F. MACSE v2: toolkit for the alignment of coding sequences accounting for frameshifts and stop codons. Mol Biol Evol. 2018;35(10):2582\u20134. https:\/\/doi.org\/10.1093\/molbev\/msy159.","journal-title":"Mol Biol Evol"},{"issue":"5","key":"279_CR18","doi-asserted-by":"publisher","first-page":"1530","DOI":"10.1093\/molbev\/msaa015","volume":"37","author":"BQ Minh","year":"2020","unstructured":"Minh BQ, Schmidt HA, Chernomor O, Schrempf D, Woodhams MD, Haeseler A, Lanfear R. IQ-TREE 2: new models and efficient methods for phylogenetic inference in the genomic era. Mol Biol Evol. 2020;37(5):1530\u20134. https:\/\/doi.org\/10.1093\/molbev\/msaa015.","journal-title":"Mol Biol Evol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00279-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00279-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00279-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T07:09:51Z","timestamp":1749280191000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-025-00279-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,7]]},"references-count":18,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["279"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00279-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,7]]},"assertion":[{"value":"31 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2025","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":"10"}}