{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T10:20:23Z","timestamp":1756462823195,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T00:00:00Z","timestamp":1634083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T00:00:00Z","timestamp":1634083200000},"content-version":"vor","delay-in-days":0,"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":["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","2015\/11937-9"],"award-info":[{"award-number":["2013\/08293-7","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","2019\/27331-3"],"award-info":[{"award-number":["2017\/12646-3","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:p>The rearrangement distance is a method to compare genomes of different species. Such distance is the number of rearrangement events necessary to transform one genome into another. Two commonly studied events are the transposition, which exchanges two consecutive blocks of the genome, and the reversal, which reverts a block of the genome. When dealing with such problems, seminal works represented genomes as sequences of genes without repetition. More realistic models started to consider gene repetition or the presence of intergenic regions, sequences of nucleotides between genes and in the extremities of the genome. This work explores the transposition and reversal events applied in a genome representation considering both gene repetition and intergenic regions. We define two problems called Minimum Common Intergenic String Partition and Reverse Minimum Common Intergenic String Partition. Using a relation with these two problems, we show a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta \\left( k \\right)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mfenced>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:mfenced>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for the Intergenic Transposition Distance, the Intergenic Reversal Distance, and the Intergenic Reversal and Transposition Distance problems, where <jats:italic>k<\/jats:italic> is the maximum number of copies of a gene in the genomes. Our practical experiments on simulated genomes show that the use of partitions improves the estimates for the distances.<\/jats:p>","DOI":"10.1186\/s13015-021-00200-w","type":"journal-article","created":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T11:32:47Z","timestamp":1634124767000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximation algorithm for rearrangement distances considering repeated genes and intergenic regions"],"prefix":"10.1186","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5745-399X","authenticated-orcid":false,"given":"Gabriel","family":"Siqueira","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6320-9747","authenticated-orcid":false,"given":"Alexsandro Oliveira","family":"Alexandrino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0568-1859","authenticated-orcid":false,"given":"Andre Rodrigues","family":"Oliveira","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,10,13]]},"reference":[{"key":"200_CR1","doi-asserted-by":"crossref","unstructured":"Willing E, Stoye J, Braga MD. Computing the Inversion-Indel Distance. IEEE\/ACM transactions on computational biology and bioinformatics. 2020.","DOI":"10.1109\/TCBB.2020.2988950"},{"issue":"16","key":"200_CR2","doi-asserted-by":"publisher","first-page":"i133","DOI":"10.1093\/bioinformatics\/btn292","volume":"24","author":"C Kahn","year":"2008","unstructured":"Kahn C, Raphael B. Analysis of segmental duplications via duplication distance. Bioinformatics. 2008;24(16):i133\u20138.","journal-title":"Bioinformatics."},{"issue":"3","key":"200_CR3","doi-asserted-by":"publisher","first-page":"98","DOI":"10.6026\/97320630012098","volume":"12","author":"T Abdullah","year":"2016","unstructured":"Abdullah T, Faiza M, Pant P, Rayyan Akhtar M, Pant P. An analysis of single nucleotide substitution in genetic codons\u2013probabilities and outcomes. Bioinformation. 2016;12(3):98\u2013104.","journal-title":"Bioinformation."},{"key":"200_CR4","series-title":"Computational molecular biology","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001","volume-title":"Combinatorics of genome rearrangements","author":"G Fertin","year":"2009","unstructured":"Fertin G, Labarre A, Rusu I, Tannier \u00c9, Vialette S. Combinatorics of genome rearrangements. Computational molecular biology. London: The MIT Press; 2009."},{"key":"200_CR5","doi-asserted-by":"crossref","unstructured":"Bergeron A, Mixtacki J, Stoye J. A Unifying View of Genome Rearrangements. In: International Workshop on Algorithms in Bioinformatics. Springer; 2006. p. 163\u201373.","DOI":"10.1007\/11851561_16"},{"issue":"11","key":"200_CR6","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1093\/bioinformatics\/15.11.909","volume":"15","author":"D Sankoff","year":"1999","unstructured":"Sankoff D. Genome rearrangement with gene families. Bioinformatics. 1999;15(11):909\u201317.","journal-title":"Bioinformatics."},{"issue":"4","key":"200_CR7","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"X Chen","year":"2005","unstructured":"Chen X, Zheng J, Fu Z, Nan P, Zhong Y, Lonardi S, et al. Assignment of orthologous genes via genome rearrangement. IEEE\/ACM Trans Comput Biol Bioinform. 2005;2(4):302\u201315.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"200_CR8","doi-asserted-by":"crossref","unstructured":"Siqueira G, Brito KL, Dias U, Dias Z. Heuristics for Genome Rearrangement Distance with Replicated Genes. IEEE\/ACM Transactions on Computational Biology and Bioinformatics. 2021; p. 1.","DOI":"10.1109\/TCBB.2021.3095021"},{"issue":"5","key":"200_CR9","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":"200_CR10","doi-asserted-by":"crossref","unstructured":"Biller P, Knibbe C, Beslon G, Tannier E. Comparative Genomics on Artificial Life. In: Pursuit of the Universal. Springer International Publishing; 2016. p. 35\u201344.","DOI":"10.1007\/978-3-319-40189-8_4"},{"issue":"3","key":"200_CR11","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"},{"issue":"4","key":"200_CR12","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1109\/TCBB.2006.44","volume":"3","author":"I Elias","year":"2006","unstructured":"Elias I, Hartman TA. 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans Comput Biol Bioinfor. 2006;3(4):369\u201379.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinfor"},{"issue":"1","key":"200_CR13","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"},{"key":"200_CR14","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). vol. 2461 of Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg New York; 2002. p. 200\u2013210.","DOI":"10.1007\/3-540-45749-6_21"},{"issue":"1","key":"200_CR15","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. J ACM. 1999;46(1):1\u201327.","journal-title":"J ACM."},{"key":"200_CR16","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 tanspositions problems. J Comput Biol. 2019;26:1223\u20139.","journal-title":"J Comput Biol"},{"issue":"3","key":"200_CR17","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."},{"issue":"3","key":"200_CR18","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s10878-010-9369-8","volume":"25","author":"X Chen","year":"2013","unstructured":"Chen X. On sorting unsigned permutations by double-cut-and-joins. J Combinatorial Optim. 2013;25(3):339\u201351.","journal-title":"J Combinatorial Optim"},{"key":"200_CR19","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). Los Alamitos, CA, USA: IEEE Computer Society; 1998. p. 96\u2013102."},{"key":"200_CR20","doi-asserted-by":"crossref","unstructured":"Kolman P, Wale\u0144 T. Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set. In: Proceedings of the 4th International Workshop on Approximation and Online Algorithms (WAOA\u20192006). Springer Berlin Heidelberg; 2007. p. 279\u2013289.","DOI":"10.1007\/11970125_22"},{"issue":"2","key":"200_CR21","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.jda.2005.01.010","volume":"5","author":"D Shapira","year":"2007","unstructured":"Shapira D, Storer JA. Edit distance with move operations. Journal of Discrete Algorithms. 2007;5(2):380\u201392.","journal-title":"Journal of Discrete Algorithms."},{"issue":"1","key":"200_CR22","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S0895480103433550","volume":"19","author":"AJ Radcliffe","year":"2005","unstructured":"Radcliffe AJ, Scott AD, Wilmer EL. Reversals and transpositions over finite alphabets. SIAM J Discrete Math. 2005;19(1):224\u201344.","journal-title":"SIAM J Discrete Math"},{"key":"200_CR23","doi-asserted-by":"crossref","unstructured":"Oliveira AR, Jean G, Fertin G, Brito KL, Dias U, Dias Z. A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions. In: Algorithms for Computational Biology. Springer International Publishing; 2020. p. 16\u201328.","DOI":"10.1007\/978-3-030-42266-0_2"},{"issue":"2","key":"200_CR24","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"},{"key":"200_CR25","doi-asserted-by":"crossref","unstructured":"Oliveira AR, Jean G, Fertin G, Brito KL, Dias U, Dias Z. Sorting Permutations by Intergenic Operations. IEEE\/ACM Transactions on Computational Biology and Bioinformatics. 2021; p. 1.","DOI":"10.1109\/TCBB.2021.3077418"},{"issue":"3","key":"200_CR26","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.dam.2006.05.011","volume":"155","author":"P Kolman","year":"2007","unstructured":"Kolman P, Wale\u0144 T. Approximating reversal distance for strings with bounded number of duplicates. Discrete Appl Math. 2007;155(3):327\u201336.","journal-title":"Discrete Appl Math"},{"issue":"1","key":"200_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1186810.1186812","volume":"3","author":"G Cormode","year":"2007","unstructured":"Cormode G, Muthukrishnan S. The string edit distance matching problem with moves. ACM Trans Algorithms. 2007;3(1):1\u201319.","journal-title":"ACM Trans Algorithms."},{"key":"200_CR28","doi-asserted-by":"crossref","unstructured":"Goldstein A, Kolman P, Zheng J. Minimum Common String Partition Problem: Hardness and Approximations. In: Proceedings of the 15th International Symposium on Algorithms and Computation (ISAAC\u20192004). Springer Berlin Heidelberg; 2005. p. 484\u2013495.","DOI":"10.1007\/978-3-540-30551-4_43"},{"key":"200_CR29","doi-asserted-by":"crossref","unstructured":"Crochemore M, Lecroq T. Suffix Tree. In: Encyclopedia of Database Systems. US: Springer; 2009. p. 2876\u201380.","DOI":"10.1007\/978-0-387-39940-9_1142"},{"key":"200_CR30","doi-asserted-by":"crossref","unstructured":"Alexandrino AO, Brito KL, Oliveira AR, Dias U, Dias Z. Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information. In: Algorithms for Computational Biology. vol. 12715. Springer International Publishing; 2021. p. 121\u2013133.","DOI":"10.1007\/978-3-030-74432-8_9"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00200-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00200-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00200-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,13]],"date-time":"2021-10-13T11:38:14Z","timestamp":1634125094000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00200-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,13]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["200"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00200-w","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2021,10,13]]},"assertion":[{"value":"26 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 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":"21"}}