{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T19:48:22Z","timestamp":1774727302598,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T00:00:00Z","timestamp":1772323200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T00:00:00Z","timestamp":1772841600000},"content-version":"vor","delay-in-days":6,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2021\/13824-8"],"award-info":[{"award-number":["2021\/13824-8"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2026,3]]},"abstract":"Abstract<\/jats:title>\n \n In genome rearrangement, graph-based representations are widely used to analyze and solve rearrangement problems. In particular, when each gene occurs at most once, the breakpoint graph is a useful tool. A maximum cycle decomposition of this graph yields immediate lower bounds for several genome rearrangement distances. This paper introduces a generalization of the Maximum Alternating Cycle Decomposition problem (\n MAX-ACD<\/jats:sc>\n ), called the Maximum Alternating Clean Balanced Cycle Decomposition problem (\n MAX-ACBCD<\/jats:sc>\n ). The\n MAX-ACD<\/jats:sc>\n problem is closely related to some rearrangement problems, where the orientation of the genes is unknown, and all genes are common to both genomes. The\n MAX-ACBCD<\/jats:sc>\n problem has applications to related rearrangement problems, which allow genes present in only one of the genomes and consider both gene order and intergenic-region information. We present a constant-factor approximation and a heuristic for the\n MAX-ACBCD<\/jats:sc>\n problem, and we performed tests with the heuristic applied to artificially generated genomes. Considering intergenic regions and a scenario where the orientation of the genes is known, we design an improved algorithm for the Sorting by Reversals and Intergenic Indels problem that guarantees an approximation factor of\n \n \n $$\\frac{3}{2}$$<\/jats:tex-math>\n \n \n 3<\/mml:mn>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . For the scenario where the orientation of the genes is unknown, and using the\n MAX-ACBCD<\/jats:sc>\n problem, we develop approximation algorithms for the Sorting by Reversals, the Sorting by Reversals and Intergenic Indels, the Reversal, Transposition and Indel Distance, the Sorting by DCJ, and the Sorting by DCJ and Intergenic Indels problems with approximation factors of 2\n k<\/jats:italic>\n ,\n \n \n $$\\frac{3k}{2}$$<\/jats:tex-math>\n \n \n \n 3<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:mfrac>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , 4\n k<\/jats:italic>\n , 2\n k<\/jats:italic>\n , and\n k<\/jats:italic>\n , respectively, where\n \n \n $$k=\\frac{31}{21}+\\epsilon $$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n =<\/mml:mo>\n \n 31<\/mml:mn>\n 21<\/mml:mn>\n <\/mml:mfrac>\n +<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>","DOI":"10.1007\/s10878-026-01405-8","type":"journal-article","created":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T05:18:32Z","timestamp":1772860712000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximum alternating clean balanced cycle decomposition and applications in rearrangement distance problems"],"prefix":"10.1007","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5745-399X","authenticated-orcid":false,"given":"Gabriel","family":"Siqueira","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5287-2925","authenticated-orcid":false,"given":"Klairton Lima","family":"Brito","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6320-9747","authenticated-orcid":false,"given":"Alexsandro Oliveira","family":"Alexandrino","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0568-1859","authenticated-orcid":false,"given":"Andre Rodrigues","family":"Oliveira","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4763-3046","authenticated-orcid":false,"given":"Ulisses","family":"Dias","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3333-6822","authenticated-orcid":false,"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,7]]},"reference":[{"key":"1405_CR1","doi-asserted-by":"crossref","unstructured":"Alexandrino AO, Brito KL, Oliveira AR, Dias U, Dias Z (2021) Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information. In: Algorithms for Computational Biology, vol. 12715, pp 121\u2013133. Springer International Publishing","DOI":"10.1007\/978-3-030-74432-8_9"},{"key":"1405_CR2","unstructured":"Alexandrino AO, Brito KL, Oliveira AR, Dias U, Dias Z (2022) Reversal and indel distance with intergenic region information. IEEE\/ACM Transactions on Computational Biology and Bioinformatics pp 1\u201313"},{"issue":"06","key":"1405_CR3","doi-asserted-by":"publisher","first-page":"2140011","DOI":"10.1142\/S0219720021400114","volume":"19","author":"AO Alexandrino","year":"2021","unstructured":"Alexandrino AO, Oliveira AR, Dias U, Dias Z (2021) Incorporating intergenic regions into reversal and transposition distances with indels. J Bioinform Comput Biol 19(06):2140011","journal-title":"J Bioinform Comput Biol"},{"issue":"8","key":"1405_CR4","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1089\/cmb.2023.0087","volume":"30","author":"AO Alexandrino","year":"2023","unstructured":"Alexandrino AO, Oliveira AR, Jean G, Fertin G, Dias U, Dias Z (2023) Reversal and transposition distance on unbalanced genomes using intergenic information. J Comput Biol 30(8):861\u2013876","journal-title":"J Comput Biol"},{"issue":"2","key":"1405_CR5","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V Bafna","year":"1996","unstructured":"Bafna V, Pevzner PA (1996) Genome rearrangements and sorting by reversals. SIAM J Comput 25(2):272\u2013289","journal-title":"SIAM J Comput"},{"key":"1405_CR6","unstructured":"Berman P, F\u00fcrer M (1994) Approximating Maximum Independent Set in Bounded Degree Graphs. In: SODA\u20191994: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 365\u2013371. Society for Industrial and Applied Mathematics"},{"key":"1405_CR7","doi-asserted-by":"crossref","unstructured":"Berman P, Hannenhalli S, Karpinski M (2002) 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, pp 200\u2013210. Springer-Verlag, Berlin Heidelberg New York, Berlin\/Heidelberg, Germany","DOI":"10.1007\/3-540-45749-6_21"},{"key":"1405_CR8","doi-asserted-by":"crossref","unstructured":"Berman P, Karpinski M (1999) On Some Tighter Inapproximability Results (Extended Abstract). In: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICAL\u20191999), Lecture Notes in Computer Science, vol. 1644, pp. 200\u2013209. Springer-Verlag, London, UK","DOI":"10.1007\/3-540-48523-6_17"},{"key":"1405_CR9","doi-asserted-by":"crossref","unstructured":"Biller P, Knibbe C, Beslon G, Tannier E (2016) Comparative Genomics on Artificial Life. In: Pursuit of the Universal, pp. 35\u201344. Springer International Publishing","DOI":"10.1007\/978-3-319-40189-8_4"},{"issue":"2","key":"1405_CR10","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 (2020) Sorting by genome rearrangements on both gene order and intergenic sizes. J Comput Biol 27(2):156\u2013174","journal-title":"J Comput Biol"},{"key":"1405_CR11","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.jda.2016.05.002","volume":"37","author":"L Bulteau","year":"2016","unstructured":"Bulteau L, Fertin G, Komusiewicz C (2016) (Prefix) reversal distance for (signed) strings with few blocks or small alphabets. J Discrete Algorithms 37:44\u201355","journal-title":"J Discrete Algorithms"},{"issue":"3","key":"1405_CR12","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 (2012) Sorting by transpositions is difficult. SIAM J Discret Math 26(3):1148\u20131180","journal-title":"SIAM J Discret Math"},{"issue":"14","key":"1405_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 (2016) Genome rearrangements with indels in intergenes restrict the scenario space. BMC Bioinformatics 17(14):426","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"1405_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1023\/A:1009838309166","volume":"3","author":"A Caprara","year":"1999","unstructured":"Caprara A (1999) On the tightness of the alternating-cycle lower bound for sorting by reversals. J Comb Optim 3(2):149\u2013182","journal-title":"J Comb Optim"},{"issue":"1","key":"1405_CR15","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A Caprara","year":"1999","unstructured":"Caprara A (1999) Sorting permutations by reversals and Eulerian cycle decompositions. SIAM J Discret Math 12(1):91\u2013110","journal-title":"SIAM J Discret Math"},{"issue":"2","key":"1405_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1023\/A:1013851611274","volume":"6","author":"A Caprara","year":"2002","unstructured":"Caprara A, Rizzi R (2002) Improved approximation for breakpoint graph decomposition and sorting by reversals. J Comb Optim 6(2):157\u2013182","journal-title":"J Comb Optim"},{"issue":"3","key":"1405_CR17","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s10878-010-9369-8","volume":"25","author":"X Chen","year":"2013","unstructured":"Chen X (2013) On sorting unsigned permutations by double-cut-and-joins. J Comb Optim 25(3):339\u2013351","journal-title":"J Comb Optim"},{"issue":"4","key":"1405_CR18","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 (2006) A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans Comput Biol Bioinf 3(4):369\u2013379","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"1405_CR19","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 (2017) Algorithms for computing the double cut and join distance on both gene order and intergenic sizes. Algorithms Mol Biol 12(1):16","journal-title":"Algorithms Mol Biol"},{"key":"1405_CR20","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA"},{"issue":"1","key":"1405_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner PA (1999) Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J ACM 46(1):1\u201327","journal-title":"J ACM"},{"issue":"1","key":"1405_CR22","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0402008","volume":"2","author":"CAJ Hurkens","year":"1989","unstructured":"Hurkens CAJ, Schrijver A (1989) On the size of systems of sets every t of which have an sdr, with an application to the worst-case ratio of heuristics for packing problems. SIAM J Discret Math 2(1):68\u201372","journal-title":"SIAM J Discret Math"},{"key":"1405_CR23","doi-asserted-by":"crossref","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations, pp. 85\u2013103. Springer","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"1405_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1023\/B:JOCO.0000031419.12290.2b","volume":"8","author":"G Lin","year":"2004","unstructured":"Lin G, Jiang T (2004) A further improved approximation algorithm for breakpoint graph decomposition. J Comb Optim 8(2):183\u2013194","journal-title":"J Comb Optim"},{"issue":"8","key":"1405_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3653295","volume":"56","author":"AR Oliveira","year":"2024","unstructured":"Oliveira AR, Brito KL, Alexandrino AO, Siqueira G, Dias U, Dias Z (2024) Rearrangement distance problems: an updated survey. ACM Comput Surv 56(8):1","journal-title":"ACM Comput Surv"},{"key":"1405_CR26","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 (2019) On the complexity of sorting by reversals and transpositions problems. J Comput Biol 26:1223\u20131229. https:\/\/doi.org\/10.1089\/cmb.2019.0078","journal-title":"J Comput Biol"},{"issue":"6","key":"1405_CR27","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 (2021) Sorting signed permutations by intergenic reversals. IEEE\/ACM Trans Comput Biol Bioinf 18(6):2870\u20132876","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"1405_CR28","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43:425\u2013440","journal-title":"J Comput Syst Sci"},{"key":"1405_CR29","doi-asserted-by":"crossref","unstructured":"Pinheiro PO, Alexandrino AO, Oliveira AR, de Souza CC, Dias Z (2020) Heuristics for Breakpoint Graph Decomposition with Applications in Genome Rearrangement Problems. In: Proceedings of the 13th Brazilian Symposium on Bioinformatics (BSB\u20192020), pp. 129\u2013140. Springer International Publishing","DOI":"10.1007\/978-3-030-65775-8_12"},{"issue":"3","key":"1405_CR30","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 (2008) An approximation algorithm for sorting by reversals and transpositions. J Discrete Algorithms 6(3):449\u2013457","journal-title":"J Discrete Algorithms"},{"key":"1405_CR31","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-540-87989-3_18","volume-title":"Comparative Genomics","author":"KM Swenson","year":"2008","unstructured":"Swenson KM, Lin Y, Rajan V, Moret BME (2008) Hurdles hardly have to be heeded. In: Nelson CE, Vialette S (eds) Comparative Genomics. Springer, Berlin Heidelberg, Berlin, Heidelberg, pp 241\u2013251"},{"key":"1405_CR32","doi-asserted-by":"crossref","unstructured":"Walter MEMT, Dias Z, Meidanis J (1998) Reversal and Transposition Distance of Linear Chromosomes. In: Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE\u20191998), pp. 96\u2013102. IEEE Computer Society, Los Alamitos, CA, USA","DOI":"10.1109\/SPIRE.1998.712988"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01405-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-026-01405-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-026-01405-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T18:59:44Z","timestamp":1774724384000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-026-01405-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["1405"],"URL":"https:\/\/doi.org\/10.1007\/s10878-026-01405-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]},"assertion":[{"value":"25 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2026","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 conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"26"}}