{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T14:20:16Z","timestamp":1753885216991,"version":"3.41.2"},"reference-count":24,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnologico","doi-asserted-by":"publisher","award":["140272\/2020-8"],"award-info":[{"award-number":["140272\/2020-8"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnologico","doi-asserted-by":"publisher","award":["202292\/2020-7"],"award-info":[{"award-number":["202292\/2020-7"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2019\/27331-3"],"award-info":[{"award-number":["2019\/27331-3"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:p> Genome rearrangement events are widely used to estimate a minimum-size sequence of mutations capable of transforming a genome into another. The length of this sequence is called distance, and determining it is the main goal in genome rearrangement distance problems. Problems in the genome rearrangement field differ regarding the set of rearrangement events allowed and the genome representation. In this work, we consider the scenario where the genomes share the same set of genes, gene orientation is known or unknown, and intergenic regions (structures between a pair of genes and at the extremities of the genome) are taken into account. We use two models, the first model allows only conservative events (reversals and moves), and the second model includes non-conservative events (insertions and deletions) in the intergenic regions. We show that both models result in NP-hard problems no matter if gene orientation is known or unknown. When the information regarding the orientation of genes is available, we present for both models an approximation algorithm with a factor of 2. For the scenario where this information is unavailable, we propose a 4-approximation algorithm for both models. <\/jats:p>","DOI":"10.1142\/s0219720023500099","type":"journal-article","created":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T08:53:56Z","timestamp":1679043236000},"source":"Crossref","is-referenced-by-count":0,"title":["Rearrangement distance with reversals, indels, and moves in intergenic regions on signed and unsigned permutations"],"prefix":"10.1142","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5287-2925","authenticated-orcid":false,"given":"Klairton Lima","family":"Brito","sequence":"first","affiliation":[{"name":"Institute of Computing, University of Campinas, 1251 Albert Einstein Avenue, Campinas, S\u00e3o Paulo, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0568-1859","authenticated-orcid":false,"given":"Andre Rodrigues","family":"Oliveira","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas, 1251 Albert Einstein Avenue, Campinas, S\u00e3o Paulo, Brazil"},{"name":"Computing and Informatics Department, Mackenzie Presbyterian University, 905 Mackenzie Avenue, Barueri, S\u00e3o Paulo, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6320-9747","authenticated-orcid":false,"given":"Alexsandro Oliveira","family":"Alexandrino","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas, 1251 Albert Einstein Avenue, Campinas, S\u00e3o Paulo, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4763-3046","authenticated-orcid":false,"given":"Ulisses","family":"Dias","sequence":"additional","affiliation":[{"name":"School of Technology, University of Campinas, 1888 Paschoal Marmo Street, Limeira, S\u00e3o Paulo, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3333-6822","authenticated-orcid":false,"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[{"name":"Institute of Computing, University of Campinas, 1251 Albert Einstein Avenue, Campinas, S\u00e3o Paulo, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2023,4,27]]},"reference":[{"issue":"10","key":"S0219720023500099BIB001","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/S0168-9525(98)01555-8","volume":"14","author":"Lupski JR","year":"1998","journal-title":"Trends Genet"},{"issue":"4","key":"S0219720023500099BIB002","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.semcancer.2010.05.007","volume":"20","author":"Chen JM","year":"2010","journal-title":"Semin Cancer Biol"},{"issue":"11","key":"S0219720023500099BIB003","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1016\/j.tig.2022.06.003","volume":"38","author":"Schuy J","year":"2022","journal-title":"Trends Genet"},{"key":"S0219720023500099BIB004","first-page":"581","volume-title":"Proc 36th Annual Symp Foundations of Computer Science (FOCS\u20191995)","author":"Hannenhalli S","year":"1995"},{"issue":"1","key":"S0219720023500099BIB005","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12864-018-5245-1","volume":"19","author":"Bochkareva OO","year":"2018","journal-title":"BMC Genom"},{"issue":"1","key":"S0219720023500099BIB006","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"Hannenhalli S","year":"1999","journal-title":"J ACM"},{"key":"S0219720023500099BIB007","first-page":"12","volume-title":"Proc 11th ACM-SIAM Annual Symp Discrete Algorithms (SODA\u20192000)","author":"Caprara A","year":"2000"},{"key":"S0219720023500099BIB008","first-page":"200","volume-title":"Proc 10th Annual European Symp Algorithms (ESA\u20192002)","author":"Berman P","year":"2002"},{"issue":"1","key":"S0219720023500099BIB009","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"Caprara A","year":"1999","journal-title":"SIAM J Discrete Math"},{"issue":"2","key":"S0219720023500099BIB010","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/S0895480197331995","volume":"14","author":"Christie DA","year":"2001","journal-title":"SIAM J Discrete Math"},{"issue":"1","key":"S0219720023500099BIB011","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S0895480103433550","volume":"19","author":"Radcliffe AJ","year":"2005","journal-title":"SIAM J Discrete Math"},{"issue":"5","key":"S0219720023500099BIB012","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1093\/gbe\/evw083","volume":"8","author":"Biller P","year":"2016","journal-title":"Genome Biol Evol"},{"key":"S0219720023500099BIB013","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-319-40189-8_4","volume-title":"Pursuit of the Universal","author":"Biller P","year":"2016"},{"issue":"6","key":"S0219720023500099BIB014","doi-asserted-by":"crossref","first-page":"2870","DOI":"10.1109\/TCBB.2020.2993002","volume":"18","author":"Oliveira AR","year":"2021","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"2","key":"S0219720023500099BIB015","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1089\/cmb.2019.0293","volume":"27","author":"Brito KL","year":"2020","journal-title":"J Comput Biol"},{"issue":"6","key":"S0219720023500099BIB016","doi-asserted-by":"crossref","first-page":"2080","DOI":"10.1109\/TCBB.2021.3077418","volume":"18","author":"Oliveira AR","year":"2021","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"3","key":"S0219720023500099BIB017","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/s10878-010-9369-8","volume":"25","author":"Chen X","year":"2013","journal-title":"J Comb Optim"},{"issue":"1","key":"S0219720023500099BIB018","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1186\/s13015-017-0107-y","volume":"12","author":"Fertin G","year":"2017","journal-title":"Algorithms Mol Biol"},{"issue":"14","key":"S0219720023500099BIB019","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1186\/s12859-016-1264-6","volume":"17","author":"Bulteau L","year":"2016","journal-title":"BMC Bioinform"},{"issue":"1","key":"S0219720023500099BIB020","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-021-00203-7","volume":"16","author":"Brito KL","year":"2021","journal-title":"Algorithms Mol Biol"},{"issue":"4","key":"S0219720023500099BIB021","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"Chen X","year":"2005","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"S0219720023500099BIB022","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13015-021-00200-w","volume":"16","author":"Siqueira G","year":"2021","journal-title":"Algorithms Mol Biol"},{"issue":"2","key":"S0219720023500099BIB023","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"Bafna V","year":"1998","journal-title":"SIAM J Discrete Math"},{"volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","year":"1990","author":"Garey MR","key":"S0219720023500099BIB024"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720023500099","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T13:29:21Z","timestamp":1683638961000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0219720023500099"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4]]},"references-count":24,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10.1142\/S0219720023500099"],"URL":"https:\/\/doi.org\/10.1142\/s0219720023500099","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"type":"print","value":"0219-7200"},{"type":"electronic","value":"1757-6334"}],"subject":[],"published":{"date-parts":[[2023,4]]},"article-number":"2350009"}}