{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T02:26:50Z","timestamp":1782959210572,"version":"3.54.5"},"reference-count":38,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:p> The Small Parsimony Problem (SPP) aims at finding the gene orders at internal nodes of a given phylogenetic tree such that the overall genome rearrangement distance along the tree branches is minimized. This problem is intractable in most genome rearrangement models, especially when gene duplication and loss are considered. In this work, we describe an Integer Linear Program algorithm to solve the SPP for natural genomes, i.e. genomes that contain conserved, unique, and duplicated markers. The evolutionary model that we consider is the DCJ-indel model that includes the Double-Cut and Join rearrangement operation and the insertion and deletion of genome segments. We evaluate our algorithm on simulated data and show that it is able to reconstruct very efficiently and accurately ancestral gene orders in a very comprehensive evolutionary model. <\/jats:p>","DOI":"10.1142\/s0219720021400096","type":"journal-article","created":{"date-parts":[[2021,10,6]],"date-time":"2021-10-06T13:13:28Z","timestamp":1633526008000},"source":"Crossref","is-referenced-by-count":7,"title":["Small parsimony for natural genomes in the DCJ-indel model"],"prefix":"10.1142","volume":"19","author":[{"given":"Daniel","family":"Doerr","sequence":"first","affiliation":[{"name":"Faculty of Medicine, Heinrich Heine University, D\u00fcsseldorf, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cedric","family":"Chauve","sequence":"additional","affiliation":[{"name":"Department of Mathematic, Simon Fraser University, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2021,11,19]]},"reference":[{"key":"S0219720021400096BIB001","first-page":"270","volume":"50","author":"Smith J","year":"2018","journal-title":"Nature"},{"key":"S0219720021400096BIB002","doi-asserted-by":"publisher","DOI":"10.1093\/gbe\/evv014"},{"key":"S0219720021400096BIB003","doi-asserted-by":"publisher","DOI":"10.1038\/ng.3435"},{"key":"S0219720021400096BIB004","doi-asserted-by":"publisher","DOI":"10.1126\/science.1258522"},{"key":"S0219720021400096BIB005","doi-asserted-by":"publisher","DOI":"10.1186\/s12915-019-0728-3"},{"key":"S0219720021400096BIB006","doi-asserted-by":"publisher","DOI":"10.1186\/s12864-018-4466-7"},{"key":"S0219720021400096BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30219-3_2"},{"key":"S0219720021400096BIB008","doi-asserted-by":"publisher","DOI":"10.1101\/gr.5383506"},{"key":"S0219720021400096BIB009","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000234"},{"key":"S0219720021400096BIB010","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"issue":"71","key":"S0219720021400096BIB011","volume":"5","author":"Pe\u2019er I","year":"1998","journal-title":"Electron Colloq Comput Compl (ECCC)"},{"key":"S0219720021400096BIB012","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.15.1.93.15155"},{"key":"S0219720021400096BIB013","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-120"},{"key":"S0219720021400096BIB014","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2013.0004"},{"key":"S0219720021400096BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.34"},{"key":"S0219720021400096BIB016","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2017.2661761"},{"key":"S0219720021400096BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2007.1069"},{"key":"S0219720021400096BIB018","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00175"},{"key":"S0219720021400096BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-4309-7_46"},{"key":"S0219720021400096BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5298-9_4"},{"key":"S0219720021400096BIB021","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2008.0069"},{"key":"S0219720021400096BIB022","doi-asserted-by":"publisher","DOI":"10.1093\/gbe\/evx069"},{"key":"S0219720021400096BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30219-3_1"},{"key":"S0219720021400096BIB024","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-S19-S4"},{"key":"S0219720021400096BIB025","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0108796"},{"key":"S0219720021400096BIB026","first-page":"97","volume-title":"7th Int Conf Bioinformatics and Computational Biology (BICoB 2015)","author":"Zhou L","year":"2015"},{"issue":"14","key":"S0219720021400096BIB027","first-page":"201","volume":"17","author":"Rajaraman A","year":"2016","journal-title":"BMC Bioinf"},{"key":"S0219720021400096BIB028","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-020-00169-y"},{"key":"S0219720021400096BIB030","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti535"},{"key":"S0219720021400096BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/11851561_16"},{"key":"S0219720021400096BIB032","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2014.0096"},{"key":"S0219720021400096BIB033","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45257-5_1"},{"key":"S0219720021400096BIB034","volume":"15","author":"Avdeyev P","year":"2019","journal-title":"Evolut Bioinf"},{"key":"S0219720021400096BIB035","doi-asserted-by":"publisher","DOI":"10.1145\/3388440.3412484"},{"key":"S0219720021400096BIB036","series-title":"No commercial publisher \u2014 Authors open access book","first-page":"2.5:1","volume-title":"Phylogenetics in the Genomic Era","author":"Tannier E","year":"2020"},{"key":"S0219720021400096BIB037","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2011.0118"},{"key":"S0219720021400096BIB038","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2016.0149"},{"key":"S0219720021400096BIB040","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz710"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720021400096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T10:01:57Z","timestamp":1640858517000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720021400096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,19]]},"references-count":38,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.1142\/S0219720021400096"],"URL":"https:\/\/doi.org\/10.1142\/s0219720021400096","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,19]]},"article-number":"2140009"}}