{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T07:31:30Z","timestamp":1778916690281,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,29]],"date-time":"2021-12-29T00:00:00Z","timestamp":1640736000000},"content-version":"vor","delay-in-days":28,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","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 Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["425340\/2016-3"],"award-info":[{"award-number":["425340\/2016-3"]}],"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":["2013\/08293-7"],"award-info":[{"award-number":["2013\/08293-7"]}],"id":[{"id":"10.13039\/501100001807","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":["2015\/11937-9"],"award-info":[{"award-number":["2015\/11937-9"]}],"id":[{"id":"10.13039\/501100001807","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":["2017\/12646-3"],"award-info":[{"award-number":["2017\/12646-3"]}],"id":[{"id":"10.13039\/501100001807","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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>In the comparative genomics field, one of the goals is to estimate a sequence of genetic changes capable of transforming a genome into another. Genome rearrangement events are mutations that can alter the genetic content or the arrangement of elements from the genome. Reversal and transposition are two of the most studied genome rearrangement events. A reversal inverts a segment of a genome while a transposition swaps two consecutive segments. Initial studies in the area considered only the order of the genes. Recent works have incorporated other genetic information in the model. In particular, the information regarding the size of intergenic regions, which are structures between each pair of genes and in the extremities of a linear genome.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results and conclusions<\/jats:title>\n                <jats:p>In this work, we investigate the <jats:sc>sorting by intergenic reversals and transpositions<\/jats:sc> problem on genomes sharing the same set of genes, considering the cases where the orientation of genes is known and unknown. Besides, we explored a variant of the problem, which generalizes the transposition event. As a result, we present an approximation algorithm that guarantees an approximation factor of 4 for both cases considering the reversal and transposition (classic definition) events, an improvement from the 4.5-approximation previously known for the scenario where the orientation of the genes is unknown. We also present a 3-approximation algorithm by incorporating the generalized transposition event, and we propose a greedy strategy to improve the performance of the algorithms. We performed practical tests adopting simulated data which indicated that the algorithms, in both cases, tend to perform better when compared with the best-known algorithms for the problem. Lastly, we conducted experiments using real genomes to demonstrate the applicability of the algorithms.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-021-00203-7","type":"journal-article","created":{"date-parts":[[2021,12,29]],"date-time":"2021-12-29T17:02:46Z","timestamp":1640797366000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["An improved approximation algorithm for the reversal and transposition distance considering gene order and intergenic sizes"],"prefix":"10.1186","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5287-2925","authenticated-orcid":false,"given":"Klairton L.","family":"Brito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0568-1859","authenticated-orcid":false,"given":"Andre R.","family":"Oliveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6320-9747","authenticated-orcid":false,"given":"Alexsandro O.","family":"Alexandrino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4763-3046","authenticated-orcid":false,"given":"Ulisses","family":"Dias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3333-6822","authenticated-orcid":false,"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,29]]},"reference":[{"issue":"1","key":"203_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner PA. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. JACM. 1999;46(1):1\u201327.","journal-title":"JACM"},{"key":"203_CR2","doi-asserted-by":"crossref","unstructured":"Berman P, Hannenhalli S, Karpinski M. 1.375-Approximation algorithm for sorting by reversals. In: Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u20192002). Lecture Notes in Computer Science, vol 2461; 2002. p. 200\u2013210.","DOI":"10.1007\/3-540-45749-6_21"},{"issue":"4","key":"203_CR3","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I Elias","year":"2006","unstructured":"Elias I, Hartman T. A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans Comput Biol Bioinform. 2006;3(4):369\u201379.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"1","key":"203_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A Caprara","year":"1999","unstructured":"Caprara A. Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J Discrete Math. 1999;12(1):91\u2013110.","journal-title":"SIAM J Discrete Math"},{"issue":"3","key":"203_CR5","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/110851390","volume":"26","author":"L Bulteau","year":"2012","unstructured":"Bulteau L, Fertin G, Rusu I. Sorting by transpositions is difficult. SIAM J Discrete Math. 2012;26(3):1148\u201380.","journal-title":"SIAM J Discrete Math"},{"key":"203_CR6","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1089\/cmb.2019.0078","volume":"26","author":"AR Oliveira","year":"2019","unstructured":"Oliveira AR, Brito KL, Dias U, Dias Z. On the complexity of sorting by reversals and transpositions problems. J Comput Biol. 2019;26:1223\u20139.","journal-title":"J Comput Biol"},{"key":"203_CR7","unstructured":"Walter MEMT, Dias Z, Meidanis J. Reversal and transposition distance of linear chromosomes. In: Proceedings of the 5th international symposium on string processing and information retrieval (SPIRE\u20191998). IEEE Computer Society, Los Alamitos, CA, USA; 1998. p. 96\u2013102."},{"issue":"3","key":"203_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1016\/j.jda.2007.09.002","volume":"6","author":"A Rahman","year":"2008","unstructured":"Rahman A, Shatabda S, Hasan M. An approximation algorithm for sorting by reversals and transpositions. J Discrete Algorithms. 2008;6(3):449\u201357.","journal-title":"J Discrete Algorithms"},{"key":"203_CR9","doi-asserted-by":"crossref","unstructured":"Chen X. On sorting permutations by double-cut-and-joins. In: Proceedings of the 16th international computing and combinatorics conference (COCOON\u20192010). Lecture Notes in Computer Science, vol 6196; 2010. p. 439\u2013448.","DOI":"10.1007\/978-3-642-14031-0_47"},{"issue":"5","key":"203_CR10","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1093\/gbe\/evw083","volume":"8","author":"P Biller","year":"2016","unstructured":"Biller P, Gu\u00e9guen L, Knibbe C, Tannier E. Breaking good: accounting for fragility of genomic regions in rearrangement distance estimation. Genome Biol Evol. 2016;8(5):1427\u201339.","journal-title":"Genome Biol Evol"},{"key":"203_CR11","doi-asserted-by":"crossref","unstructured":"Biller P, Knibbe C, Beslon G, Tannier E. Comparative genomics on artificial life. In: Pursuit of the Universal; 2016. p. 35\u201344.","DOI":"10.1007\/978-3-319-40189-8_4"},{"issue":"1","key":"203_CR12","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1186\/s13015-017-0107-y","volume":"12","author":"G Fertin","year":"2017","unstructured":"Fertin G, Jean G, Tannier E. Algorithms for computing the double cut and join distance on both gene order and intergenic sizes. Algorithms Mol Biol. 2017;12(1):16.","journal-title":"Algorithms Mol Biol"},{"issue":"14","key":"203_CR13","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1186\/s12859-016-1264-6","volume":"17","author":"L Bulteau","year":"2016","unstructured":"Bulteau L, Fertin G, Tannier E. Genome rearrangements with indels in intergenes restrict the scenario space. BMC Bioinform. 2016;17(14):426.","journal-title":"BMC Bioinform"},{"key":"203_CR14","doi-asserted-by":"crossref","unstructured":"Dias U, Oliveira AR, Brito KL, Dias Z. Block-interchange distance considering intergenic regions. In: Proceedings of the 12th Brazilian symposium on bioinformatics (BSB\u20192019); 2019. p. 58\u201369.","DOI":"10.1007\/978-3-030-46417-2_6"},{"issue":"6","key":"203_CR15","doi-asserted-by":"publisher","first-page":"2870","DOI":"10.1109\/TCBB.2020.2993002","volume":"18","author":"AR Oliveira","year":"2021","unstructured":"Oliveira AR, Jean G, Fertin G, Brito KL, Bulteau L, Dias U, Dias Z. Sorting signed permutations by intergenic reversals. IEEE\/ACM Trans Comput Biol Bioinform. 2021;18(6):2870\u20136.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"2","key":"203_CR16","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1089\/cmb.2019.0293","volume":"27","author":"KL Brito","year":"2020","unstructured":"Brito KL, Jean G, Fertin G, Oliveira AR, Dias U, Dias Z. Sorting by genome rearrangements on both gene order and intergenic sizes. J Comput Biol. 2020;27(2):156\u201374.","journal-title":"J Comput Biol"},{"issue":"6","key":"203_CR17","doi-asserted-by":"publisher","first-page":"2080","DOI":"10.1109\/TCBB.2021.3077418","volume":"18","author":"AR Oliveira","year":"2021","unstructured":"Oliveira AR, Jean G, Fertin G, Brito KL, Dias U, Dias Z. Sorting permutations by intergenic operations. IEEE\/ACM Trans Comput Biol Bioinform. 2021;18(6):2080\u201393.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"1","key":"203_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-019-0156-5","volume":"14","author":"AR Oliveira","year":"2019","unstructured":"Oliveira AR, Jean G, Fertin G, Dias U, Dias Z. Super short operations on both gene order and intergenic sizes. Algorithms Mol Biol. 2019;14(1):1\u201317.","journal-title":"Algorithms Mol Biol"},{"key":"203_CR19","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"JD Kececioglu","year":"1995","unstructured":"Kececioglu JD, Sankoff D. Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement. Algorithmica. 1995;13:180\u2013210.","journal-title":"Algorithmica"},{"issue":"D1","key":"203_CR20","doi-asserted-by":"publisher","first-page":"D667","DOI":"10.1093\/nar\/gkaa958","volume":"49","author":"L Garczarek","year":"2021","unstructured":"Garczarek L, Guyet U, Dor\u00e9 H, Farrant GK, Hoebeke M, Brillet-Gu\u00e9guen L, Bisch A, Ferrieux M, Siltanen J, Corre E, et al. Cyanorak v2. 1: a scalable information system dedicated to the visualization and expert curation of marine and brackish picocyanobacteria genomes. Nucleic Acids Res. 2021;49(D1):D667\u201376.","journal-title":"Nucleic Acids Res"},{"key":"203_CR21","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1090\/dimacs\/037\/11","volume":"37","author":"V Makarenkov","year":"1997","unstructured":"Makarenkov V, Leclerc B. Tree metrics and their circular orders: Some uses for the reconstruction and fitting of phylogenetic trees. Math Hierarch Biol DIMACS Ser Discrete Math Theor Comput Sci. 1997;37:183\u2013208.","journal-title":"Math Hierarch Biol DIMACS Ser Discrete Math Theor Comput Sci"},{"issue":"23","key":"203_CR22","doi-asserted-by":"publisher","first-page":"3119","DOI":"10.1093\/bioinformatics\/btm500","volume":"23","author":"DM De Vienne","year":"2007","unstructured":"De Vienne DM, Giraud T, Martin OC. A congruence index for testing topological similarity between trees. Bioinformatics. 2007;23(23):3119\u201324.","journal-title":"Bioinformatics"},{"issue":"2","key":"203_CR23","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1093\/molbev\/msz240","volume":"37","author":"L-G Wang","year":"2020","unstructured":"Wang L-G, Lam TT-Y, Xu S, Dai Z, Zhou L, Feng T, Guo P, Dunn CW, Jones BR, Bradley T, et al. treeio: an R package for phylogenetic tree input and output with richly annotated and associated data. Mol Biol Evol. 2020;37(2):599\u2013603.","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-021-00203-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00203-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00203-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,29]],"date-time":"2021-12-29T17:03:05Z","timestamp":1640797385000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00203-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["203"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00203-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12]]},"assertion":[{"value":"30 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2021","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 that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"24"}}