{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:28:53Z","timestamp":1773271733200,"version":"3.50.1"},"reference-count":53,"publisher":"Oxford University Press (OUP)","issue":"10","license":[{"start":{"date-parts":[[2020,2,14]],"date-time":"2020-02-14T00:00:00Z","timestamp":1581638400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1406984"],"award-info":[{"award-number":["DMS-1406984"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Government of the Russian Federation"},{"name":"ITMO Fellowship and Professorship Program"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,5,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>One of the key computational problems in comparative genomics is the reconstruction of genomes of ancestral species based on genomes of extant species. Since most dramatic changes in genomic architectures are caused by genome rearrangements, this problem is often posed as minimization of the number of genome rearrangements between extant and ancestral genomes. The basic case of three given genomes is known as the genome median problem. Whole-genome duplications (WGDs) represent yet another type of dramatic evolutionary events and inspire the reconstruction of preduplicated ancestral genomes, referred to as the genome halving problem. Generalization of WGDs to whole-genome multiplication events leads to the genome aliquoting problem.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>In this study, we propose polynomial-size integer linear programming (ILP) formulations for the aforementioned problems. We further obtain such formulations for the restricted and conserved versions of the median and halving problems, which have been recently introduced to improve biological relevance of the solutions. Extensive evaluation of solutions to the different ILP problems demonstrates their good accuracy. Furthermore, since the ILP formulations for the conserved versions have linear size, they provide a novel practical approach to ancestral genome reconstruction, which combines the advantages of homology- and rearrangements-based methods.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>Code and data are available in https:\/\/github.com\/AvdeevPavel\/ILP-WGD-reconstructor.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa100","type":"journal-article","created":{"date-parts":[[2020,2,7]],"date-time":"2020-02-07T20:17:01Z","timestamp":1581106621000},"page":"2993-3003","source":"Crossref","is-referenced-by-count":7,"title":["A unified ILP framework for core ancestral genome reconstruction problems"],"prefix":"10.1093","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7953-6259","authenticated-orcid":false,"given":"Pavel","family":"Avdeyev","sequence":"first","affiliation":[{"name":"Department of Mathematics , The George Washington University, Washington, DC 20052, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3415-9565","authenticated-orcid":false,"given":"Nikita","family":"Alexeev","sequence":"additional","affiliation":[{"name":"Computer Technologies Laboratory , ITMO University, Saint Petersburg, 197101, Russia"}]},{"given":"Yongwu","family":"Rong","sequence":"additional","affiliation":[{"name":"Department of Mathematics , Queens College, City University of New York, Flushing, NY 11367, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5140-8095","authenticated-orcid":false,"given":"Max A","family":"Alekseyev","sequence":"additional","affiliation":[{"name":"Department of Mathematics , The George Washington University, Washington, DC 20052, USA"},{"name":"Department of Biostatistics and Bioinformatics , The George Washington University, Washington, DC 20052, USA"}]}],"member":"286","published-online":{"date-parts":[[2020,2,14]]},"reference":[{"key":"2023020108352488700_btaa100-B1","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1109\/TCBB.2007.1002","article-title":"Colored de Bruijn graphs and the genome halving problem","volume":"4","author":"Alekseyev","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020108352488700_btaa100-B2","first-page":"665","author":"Alekseyev","year":"2007"},{"key":"2023020108352488700_btaa100-B3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/j.tcs.2008.01.013","article-title":"Multi-break rearrangements and chromosomal evolution","volume":"395","author":"Alekseyev","year":"2008","journal-title":"Theor. Comput. Sci"},{"key":"2023020108352488700_btaa100-B4","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":"2023020108352488700_btaa100-B5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/s12864-017-3733-3","article-title":"Estimation of the true evolutionary distance under the fragile breakage model","volume":"18","author":"Alexeev","year":"2017","journal-title":"BMC Genomics"},{"key":"2023020108352488700_btaa100-B6","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1186\/s12859-016-1263-7","article-title":"Comparative genomics meets topology: a novel view on genome median and halving problems","volume":"17","author":"Alexeev","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B7378","doi-asserted-by":"publisher","first-page":"117693431882053","DOI":"10.1177\/1176934318820534","article-title":"Linearization of median genomes under the double-cut-and-join-indel model","volume":"15","author":"Avdeyev","year":"2019","journal-title":"Evol. Bioinforma."},{"key":"2023020108352488700_btaa100-B7","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":"2023020108352488700_btaa100-B8","author":"Avdeyev","year":"2017"},{"key":"2023020108352488700_btaa100-B9","first-page":"163","author":"Bergeron","year":"2006"},{"key":"2023020108352488700_btaa100-B10","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1093\/gbe\/evw083","article-title":"Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation","volume":"8","author":"Biller","year":"2016","journal-title":"Genome Biol. Evol"},{"key":"2023020108352488700_btaa100-B11","doi-asserted-by":"crossref","first-page":"1456","DOI":"10.1101\/gr.3672305","article-title":"The yeast gene order browser: combining curated homology and syntenic context reveals gene fate in polyploid species","volume":"15","author":"Byrne","year":"2005","journal-title":"Genome Res"},{"key":"2023020108352488700_btaa100-B12","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","article-title":"The reversal median problem","volume":"15","author":"Caprara","year":"2003","journal-title":"INFORMS J. Comput"},{"key":"2023020108352488700_btaa100-B13","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1090\/dimacs\/047\/10","article-title":"A column-generation based branch-and-bound algorithm for sorting by reversals","volume":"47","author":"Caprara","year":"1999","journal-title":"Math. Support Mol. Biol"},{"key":"2023020108352488700_btaa100-B14","first-page":"12","author":"Caprara","year":"2000"},{"key":"2023020108352488700_btaa100-B15","first-page":"74","author":"Dias","year":"2007"},{"key":"2023020108352488700_btaa100-B16","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1137\/S0097539700377177","article-title":"The reconstruction of doubled genomes","volume":"32","author":"El-Mabrouk","year":"2003","journal-title":"SIAM J. Comput"},{"key":"2023020108352488700_btaa100-B17","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-16-S14-S3","article-title":"Reconstruction of ancestral gene orders using intermediate genomes","volume":"16","author":"Feij\u00e3o","year":"2015","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B18","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1186\/s12859-016-1261-9","article-title":"Fast ancestral gene order reconstruction of genomes with unequal gene content","volume":"17","author":"Feij\u00e3o","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B19","author":"Gagnon","year":"2010"},{"key":"2023020108352488700_btaa100-B20","first-page":"1","article-title":"Ancestral genome inference using a genetic algorithm approach","volume":"8","author":"Gao","year":"2013","journal-title":"PLoS One"},{"key":"2023020108352488700_btaa100-B21","first-page":"21","author":"Gavranovi\u0107","year":"2010"},{"key":"2023020108352488700_btaa100-B22","year":"2019"},{"key":"2023020108352488700_btaa100-B23","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1139\/g04-016","article-title":"Ancestral genome duplication in rice","volume":"47","author":"Guyot","year":"2004","journal-title":"Genome"},{"key":"2023020108352488700_btaa100-B24","doi-asserted-by":"crossref","first-page":"S5","DOI":"10.1186\/1471-2105-13-S19-S5","article-title":"Medians seek the corners, and other conjectures","volume":"13","author":"Haghighi","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B25","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":"46","author":"Hannenhalli","year":"1999","journal-title":"J. ACM"},{"key":"2023020108352488700_btaa100-B26","doi-asserted-by":"crossref","first-page":"1585","DOI":"10.1109\/TCBB.2017.2708121","article-title":"Genome rearrangement with ILP","volume":"15","author":"Hartmann","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020108352488700_btaa100-B28","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1038\/nature02424","article-title":"Proof and evolutionary analysis of ancient genome duplication in the yeast Saccharomyces cerevisiae","volume":"428","author":"Kellis","year":"2004","journal-title":"Nature"},{"key":"2023020108352488700_btaa100-B29","author":"Lancia","year":"2015"},{"key":"2023020108352488700_btaa100-B30","author":"Laohakiat","year":"2008"},{"key":"2023020108352488700_btaa100-B31","doi-asserted-by":"crossref","first-page":"i114","DOI":"10.1093\/bioinformatics\/btn148","article-title":"Estimating true evolutionary distances under the DCJ model","volume":"24","author":"Lin","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020108352488700_btaa100-B32","author":"Mixtacki","year":"2008"},{"key":"2023020108352488700_btaa100-B33","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1101\/gr.757503","article-title":"Genome rearrangements in mammalian evolution: lessons from human and mouse genomes","volume":"13","author":"Pevzner","year":"2003","journal-title":"Genome Res"},{"key":"2023020108352488700_btaa100-B34","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1038\/ng0498-345","article-title":"Vertebrate genome evolution and the zebrafish gene map","volume":"18","author":"Postlethwait","year":"1998","journal-title":"Nat. Genet"},{"key":"2023020108352488700_btaa100-B35","doi-asserted-by":"crossref","first-page":"S30","DOI":"10.1186\/1471-2105-11-S1-S30","article-title":"Heuristics for the inversion median problem","volume":"11","author":"Rajan","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B36","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1089\/cmb.2011.0136","article-title":"Genome halving and double distance with losses","volume":"18","author":"Savard","year":"2011","journal-title":"J. Comput. Biol"},{"key":"2023020108352488700_btaa100-B37","doi-asserted-by":"crossref","first-page":"i329","DOI":"10.1093\/bioinformatics\/btv229","article-title":"Comparing genomes with rearrangements and segmental duplications","volume":"31","author":"Shao","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020108352488700_btaa100-B38","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":"2023020108352488700_btaa100-B39","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1142\/S0219720007002552","article-title":"Computing the reversal distance between genomes in the presence of multi-gene families via binary integer programming","volume":"05","author":"Suksawatchon","year":"2007","journal-title":"J. Bioinform. Comput. Biol"},{"key":"2023020108352488700_btaa100-B40","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1186\/1471-2105-10-120","article-title":"Multichromosomal median and halving problems under different genomic distances","volume":"10","author":"Tannier","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B41","year":"2019"},{"key":"2023020108352488700_btaa100-B42","doi-asserted-by":"crossref","first-page":"S2","DOI":"10.1186\/1471-2105-10-S1-S2","article-title":"Genome aliquoting with double cut and join","volume":"10","author":"Warren","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023020108352488700_btaa100-B43","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S0219720009004102","article-title":"Genome halving with double cut and join","volume":"7","author":"Warren","year":"2009","journal-title":"J. Bioinform. Comput. Biol"},{"key":"2023020108352488700_btaa100-B44","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1089\/cmb.2017.0157","article-title":"A median solver and phylogenetic inference based on double-cut-and-join sorting","volume":"25","author":"Xia","year":"2018","journal-title":"J. Comput. Biol"},{"key":"2023020108352488700_btaa100-B45","author":"Xu","year":"2009"},{"key":"2023020108352488700_btaa100-B46","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.1089\/cmb.2009.0087","article-title":"A fast and exact algorithm for the median of three problem: a graph decomposition approach","volume":"16","author":"Xu","year":"2009","journal-title":"J. Comput. Biol"},{"key":"2023020108352488700_btaa100-B47","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":"2023020108352488700_btaa100-B48","author":"Zabelkin","year":"2018"},{"key":"2023020108352488700_btaa100-B49","first-page":"bty381","article-title":"Sorting cancer karyotypes using double-cut-and-joins, duplications and deletions","author":"Zeira","year":"2018","journal-title":"Bioinformatics"},{"key":"2023020108352488700_btaa100-B50","author":"Zhang","year":"2009"},{"key":"2023020108352488700_btaa100-B51","doi-asserted-by":"crossref","first-page":"1579","DOI":"10.1109\/TCBB.2017.2712695","article-title":"Evolutionary model for the statistical divergence of paralogous and orthologous gene pairs generated by whole genome duplication and speciation","volume":"15","author":"Zhang","year":"2017","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020108352488700_btaa100-B52","doi-asserted-by":"crossref","first-page":"117693430600200","DOI":"10.1177\/117693430600200028","article-title":"Genome halving with an outgroup","volume":"2","author":"Zheng","year":"2006","journal-title":"Evol. Bioinform"},{"key":"2023020108352488700_btaa100-B53","doi-asserted-by":"crossref","first-page":"i96","DOI":"10.1093\/bioinformatics\/btn146","article-title":"Guided genome halving: hardness, heuristics and the history of the hemiascomycetes","volume":"24","author":"Zheng","year":"2008","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa100\/32927088\/btaa100.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/10\/2993\/48990574\/bioinformatics_36_10_2993.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/10\/2993\/48990574\/bioinformatics_36_10_2993.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,31]],"date-time":"2024-07-31T08:11:16Z","timestamp":1722413476000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/10\/2993\/5736131"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2020,2,14]]},"references-count":53,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa100","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,5,15]]},"published":{"date-parts":[[2020,2,14]]}}}