{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:04:06Z","timestamp":1760234646075,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"vor","delay-in-days":0,"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":["2013\/08293-7, 2015\/11937-9, 2017\/12646-3, 2017\/16246-0, and 2017\/16871-1"],"award-info":[{"award-number":["2013\/08293-7, 2015\/11937-9, 2017\/12646-3, 2017\/16246-0, and 2017\/16871-1"]}],"id":[{"id":"10.13039\/501100001807","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":["400487\/2016-0, 425340\/2016-3, and 304380\/2018-0"],"award-info":[{"award-number":["400487\/2016-0, 425340\/2016-3, and 304380\/2018-0"]}],"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"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Understanding how different two organisms are is one question addressed by the comparative genomics field. A well-accepted way to estimate the evolutionary distance between genomes of two organisms is finding the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation, and, so, we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of rearrangements. This work investigates the problems of sorting permutations using reversals and\/or transpositions, with some additional restrictions of biological relevance. Given a value \u03bb, the problem now is how to sort a \u03bb-permutation, which is a permutation whose elements are less than \u03bb positions away from their correct places (regarding the identity), by applying the minimum number of rearrangements. Each \u03bb-rearrangement must have size, at most, \u03bb, and, when applied to a \u03bb-permutation, the result should also be a \u03bb-permutation. We present algorithms with approximation factors of O(\u03bb2), O(\u03bb), and O(1) for the problems of Sorting \u03bb-Permutations by \u03bb-Reversals, by \u03bb-Transpositions, and by both operations.<\/jats:p>","DOI":"10.3390\/a14060175","type":"journal-article","created":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T15:58:44Z","timestamp":1622563124000},"page":"175","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for Sorting \u03bb-Permutations by \u03bb-Operations"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5643-4527","authenticated-orcid":false,"given":"Guilherme Henrique Santos","family":"Miranda","sequence":"first","affiliation":[{"name":"Institute of Computing, University of Campinas, Campinas 13083-970, Brazil"}]},{"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, Campinas 13083-970, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0602-6298","authenticated-orcid":false,"given":"Carla Negri","family":"Lintzmayer","sequence":"additional","affiliation":[{"name":"Center for Mathematics, Computation and Cognition, Federal University of ABC, Santo Andr\u00e9 09210-580, Brazil"}]},{"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, Campinas 13083-970, Brazil"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,1]]},"reference":[{"key":"ref_1","first-page":"1148","article-title":"Sorting by Transpositions is Difficult","volume":"26","author":"Bulteau","year":"2012","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1137\/S089548019731994X","article-title":"Sorting Permutations by Reversals and Eulerian Cycle Decompositions","volume":"12","author":"Caprara","year":"1999","journal-title":"SIAM J. Discret. Math."},{"key":"ref_3","first-page":"200","article-title":"1.375-Approximation Algorithm for Sorting by Reversals","volume":"Volume 2461","author":"Raman","year":"2002","journal-title":"Lecture Notes in Computer Science, Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u20192002), Rome, Italy, 17\u201321 September 2002"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1109\/TCBB.2006.44","article-title":"A 1.375-Approximation Algorithm for Sorting by Transpositions","volume":"3","author":"Elias","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/300515.300516","article-title":"Transforming Cabbage into Turnip: Polynomial Algorithm for Sorting Signed Permutations by Reversals","volume":"46","author":"Hannenhalli","year":"1999","journal-title":"J. ACM"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Oliveira, A.R., Brito, K.L., Dias, U., and Dias, Z. (2019). On the Complexity of Sorting by Reversals and Transpositions Problems. J. Comput. Biol.","DOI":"10.1089\/cmb.2019.0078"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1016\/j.jda.2007.09.002","article-title":"An Approximation Algorithm for Sorting by Reversals and Transpositions","volume":"6","author":"Rahman","year":"2008","journal-title":"J. Discret. Algorithms"},{"key":"ref_8","unstructured":"Walter, M.E.M.T., Dias, Z., and Meidanis, J. Reversal and Transposition Distance of Linear Chromosomes. Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE\u20191998), Santa Cruz, Bolivia, 9\u201311 September 1998."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/s10878-010-9369-8","article-title":"On Sorting Unsigned Permutations by Double-Cut-and-Joins","volume":"25","author":"Chen","year":"2013","journal-title":"J. Comb. Optim."},{"key":"ref_10","first-page":"65","article-title":"Sorting by Prefix Transpositions","volume":"Volume 2476","author":"Laender","year":"2002","journal-title":"Lecture Notes in Computer Science, Proceedings of the 9th International Symposium on String Processing and Information Retrieval (SPIRE\u20192002), Lisbon, Portugal, 11\u201313 September 2002"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1750002","DOI":"10.1142\/S0219720017500020","article-title":"Sorting Permutations by Prefix and Suffix Rearrangements","volume":"15","author":"Lintzmayer","year":"2017","journal-title":"J. Bioinform. Comput. Biol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"i190","DOI":"10.1093\/bioinformatics\/btg1025","article-title":"Detection and validation of single gene inversions","volume":"19","author":"Lefebvre","year":"2003","journal-title":"Bioinformatics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1089\/106652703322539097","article-title":"Sorting by Short Swaps","volume":"10","author":"Heath","year":"2003","journal-title":"J. Comput. Biol."},{"key":"ref_14","first-page":"491","article-title":"An 5\/4-Approximation Algorithm for Sorting Permutations by Short Block Moves","volume":"Volume 8889","author":"Ahn","year":"2014","journal-title":"Lecture Notes in Computer Science, Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC\u20192014), Jeonju, Korea, 15\u201317 December 2014"},{"key":"ref_15","unstructured":"Vergara, J.P.C. (1998). Sorting by Bounded Permutations. [Ph.D. Thesis, Virginia Polytechnic Institute and State University]."},{"key":"ref_16","first-page":"1","article-title":"Sorting Signed Permutations by Short Operations","volume":"10","author":"Lee","year":"2015","journal-title":"Algorithms Mol. Biol."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Zhang, S., Zhu, D., Jiang, H., Guo, J., Feng, H., and Liu, X. (2021). Sorting a Permutation by Best Short Swaps. Algorithmica, 1\u201327.","DOI":"10.1007\/s00453-021-00814-x"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/978-3-319-91938-6_7","article-title":"Sorting Permutations by Limited-Size Operations","volume":"Volume 10849","author":"Miranda","year":"2018","journal-title":"Algorithms for Computational Biology"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"GC11","DOI":"10.1016\/0378-1119(95)00878-0","article-title":"Parametric Genome Rearrangement","volume":"172","author":"Blanchette","year":"1996","journal-title":"Gene"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Miranda, G.H.S., Alexandrino, A.O., Lintzmayer, C.N., and Dias, Z. Sorting \u03bb-Permutations by \u03bb-Operations. Proceedings of the 11th Brazilian Symposium on Bioinformatics (BSB\u20192018), Niter\u00f3i, Brazil, 30 October\u20131 November 2018.","DOI":"10.1007\/978-3-030-01722-4_1"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1137\/S0097539793250627","article-title":"Genome Rearrangements and Sorting by Reversals","volume":"25","author":"Bafna","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S089548019528280X","article-title":"Sorting by Transpositions","volume":"11","author":"Bafna","year":"1998","journal-title":"SIAM J. Discret. Math."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Chan, T.M., and P\u0103tra\u015fcu, M. Counting inversions, offline orthogonal range counting, and related problems. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, 17\u201319 January 2010.","DOI":"10.1137\/1.9781611973075.15"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/s10878-020-00673-2","article-title":"Length-weighted \u03bb-rearrangement distance","volume":"41","author":"Alexandrino","year":"2021","journal-title":"J. Comb. Optim."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1089\/cmb.2009.0184","article-title":"Sorting Signed Permutations by Inversions in O(nlogn) time","volume":"17","author":"Swenson","year":"2010","journal-title":"J. Comput. Biol."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/175\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:09:52Z","timestamp":1760162992000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,1]]},"references-count":25,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060175"],"URL":"https:\/\/doi.org\/10.3390\/a14060175","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,6,1]]}}}