{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T20:35:08Z","timestamp":1773866108986,"version":"3.50.1"},"reference-count":14,"publisher":"EDP Sciences","issue":"3","license":[{"start":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T00:00:00Z","timestamp":1683763200000},"content-version":"vor","delay-in-days":10,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,4,9]]},"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:p>Ancestral reconstruction is a classic task in comparative genomics. Here, we study the<jats:italic>genome median problem<\/jats:italic>, a related computational problem which, given a set of three or more genomes, asks to find a new genome that minimizes the sum of pairwise distances between it and the given genomes. The<jats:italic>distance<\/jats:italic>stands for the amount of evolution observed at the genome level, for which we determine the minimum number of rearrangement operations necessary to transform one genome into the other. For almost all rearrangement operations the median problem is NP-hard, with the exception of the<jats:italic>breakpoint median<\/jats:italic>that can be constructed efficiently for multichromosomal circular and mixed genomes. In this work, we study the median problem under a restricted rearrangement measure called<jats:italic>c<\/jats:italic><jats:sub>4<\/jats:sub><jats:italic>-distance<\/jats:italic>, which is closely related to the breakpoint and the DCJ distance. We identify tight bounds and decomposers of the<jats:italic>c<\/jats:italic><jats:sub>4<\/jats:sub>-median and develop algorithms for its construction, one exact ILP-based and three combinatorial heuristics. Subsequently, we perform experiments on simulated data sets. Our results suggest that the<jats:italic>c<\/jats:italic><jats:sub>4<\/jats:sub>-distance is useful for the study the genome median problem, from theoretical and practical perspectives.<\/jats:p>","DOI":"10.1051\/ro\/2023052","type":"journal-article","created":{"date-parts":[[2023,4,13]],"date-time":"2023-04-13T19:03:24Z","timestamp":1681412604000},"page":"1045-1058","source":"Crossref","is-referenced-by-count":3,"title":["Algorithms for the genome median under a restricted measure of rearrangement"],"prefix":"10.1051","volume":"57","author":[{"given":"Helmuth O.M.","family":"Silva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4131-7309","authenticated-orcid":false,"given":"Diego P.","family":"Rubert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eloi","family":"Araujo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9808-7401","authenticated-orcid":false,"given":"Eckhard","family":"Steffen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3720-6227","authenticated-orcid":false,"given":"Daniel","family":"Doerr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6809-3547","authenticated-orcid":false,"given":"F\u00e1bio V.","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2023,5,11]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"Bafna","year":"1996","journal-title":"SIAM J. Comput."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Bergeron A., Mixtacki J. and Stoye J., A unifying view of genome rearrangements, in Proc. of WABI. Vol. 4175 of LNBI Springer Berlin Heidelberg (2006) 163\u2013173.","DOI":"10.1007\/11851561_16"},{"key":"R3","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1287\/ijoc.15.1.93.15155","volume":"15","author":"Caprara","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"R4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-017-0092-1","volume":"12","author":"Doerr","year":"2017","journal-title":"Algorithm Mol. Biol."},{"key":"R5","doi-asserted-by":"crossref","first-page":"1318","DOI":"10.1109\/TCBB.2011.34","volume":"8","author":"Feij\u00e3o","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Fertin G., Labarre A., Rusu I., Tannier E. and Vialette S., Combinatorics of Genomes Rearrangements. The MIT Press (2009).","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Hannenhalli S. and Pevzner P., Transforming men into mice (polynomial algorithm for genomic distance problem), in Proc. of FOCS 1995. IEEE (1995) 581\u2013592.","DOI":"10.1109\/SFCS.1995.492588"},{"key":"R8","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.ipl.2007.04.011","volume":"104","author":"Jean","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"R9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.2013.0004","volume":"21","author":"Kov\u00e1\u010d","year":"2013","journal-title":"J. Comput. Biol."},{"key":"R10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-10-120","volume":"10","author":"Tannier","year":"2009","journal-title":"BMC Bioinf."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Xu A.W., DCJ median problems on linear multichromosomal genomes: graph representation and fast exact solutions, in Proc. of RECOMB-CG. Vol. 5817 of LNCS. Springer Berlin Heidelberg (2009) 70\u201383.","DOI":"10.1007\/978-3-642-04744-2_7"},{"key":"R12","doi-asserted-by":"crossref","first-page":"1369","DOI":"10.1089\/cmb.2009.0087","volume":"16","author":"Xu","year":"2009","journal-title":"J. Comput. Biol."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Xu A.W. and Sankoff D., Decompositions of multiple breakpoint graphs and rapid exact solutions to the median problem, in Proc. of WABI. Vol. 5251 of LNBI. Springer (2008) 25\u201337.","DOI":"10.1007\/978-3-540-87361-7_3"},{"key":"R14","doi-asserted-by":"crossref","first-page":"3340","DOI":"10.1093\/bioinformatics\/bti535","volume":"21","author":"Yancopoulos","year":"2005","journal-title":"Bioinformatics"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023052\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T07:33:20Z","timestamp":1729236800000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023052"}},"subtitle":[],"editor":[{"given":"M.B.","family":"Campelo Neto","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"S.","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"I.","family":"Loiseau","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Y.","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"A.","family":"Weintraub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"V.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"T.","family":"Liebling","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"R.","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"N.","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,5]]},"references-count":14,"journal-issue":{"issue":"3"},"alternative-id":["ro220741"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023052","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5]]}}}