{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:01:50Z","timestamp":1760234510577,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,5,29]],"date-time":"2021-05-29T00:00:00Z","timestamp":1622246400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100012453","name":"PHC","doi-asserted-by":"publisher","award":["Procope"],"award-info":[{"award-number":["Procope"]}],"id":[{"id":"10.13039\/100012453","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"DAAD","doi-asserted-by":"publisher","award":["Procope"],"award-info":[{"award-number":["Procope"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A multi-cut rearrangement of a string S is a string S\u2032 obtained from S by an operation called k-cut rearrangement, that consists of (1) cutting S at a given number k of places in S, making S the concatenated string X1\u00b7X2\u00b7X3\u00b7\u2026\u00b7Xk\u00b7Xk+1, where X1 and Xk+1 are possibly empty, and (2) rearranging the Xis so as to obtain S\u2032=X\u03c0(1)\u00b7X\u03c0(2)\u00b7X\u03c0(3)\u00b7\u2026\u00b7X\u03c0(k+1), \u03c0 being a permutation on 1,2,\u2026,k+1 satisfying \u03c0(1)=1 and \u03c0(k+1)=k+1. Given two strings S and T built on the same multiset of characters from an alphabet \u03a3, the Sorting by Multi-Cut Rearrangements (SMCR) problem asks whether a given number \u2113 of k-cut rearrangements suffices to transform S into T. The SMCR problem generalizes several classical genomic rearrangements problems, such as Sorting by Transpositions and Sorting by Block Interchanges. It may also model chromoanagenesis, a recently discovered phenomenon consisting of massive simultaneous rearrangements. In this paper, we study the SMCR problem from an algorithmic complexity viewpoint. More precisely, we investigate its classical and parameterized complexity, as well as its approximability, in the general case or when S and T are permutations.<\/jats:p>","DOI":"10.3390\/a14060169","type":"journal-article","created":{"date-parts":[[2021,5,31]],"date-time":"2021-05-31T00:22:15Z","timestamp":1622420535000},"page":"169","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sorting by Multi-Cut Rearrangements"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1645-9345","authenticated-orcid":false,"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[{"name":"LIGM, CNRS, Universit\u00e9 Gustave Eiffel, F-77454 Marne-la-Vall\u00e9e, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8251-2012","authenticated-orcid":false,"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[{"name":"CNRS, LS2N, Universit\u00e9 de Nantes, F-44000 Nantes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1534-2682","authenticated-orcid":false,"given":"G\u00e9raldine","family":"Jean","sequence":"additional","affiliation":[{"name":"CNRS, LS2N, Universit\u00e9 de Nantes, F-44000 Nantes, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7032","authenticated-orcid":false,"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[{"name":"Fachbereich f\u00fcr Mathematik und Informatik, Philipps-Universit\u00e4t Marburg, D-35037 Marburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,29]]},"reference":[{"key":"ref_1","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_2","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_3","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/S0020-0190(96)00155-X","article-title":"Sorting Permutations by Block-Interchanges","volume":"60","author":"Christie","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Fertin, G., Labarre, A., Rusu, I., Tannier, E., and Vialette, S. (2009). Combinatorics of Genome Rearrangements, MIT Press. Computational Molecular Biology.","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.cell.2010.11.055","article-title":"Massive Genomic Rearrangement Acquired in a Single Catastrophic Event during Cancer Development","volume":"144","author":"Stephens","year":"2011","journal-title":"Cell"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/s13039-020-0470-0","article-title":"Chromoanagenesis: A piece of the macroevolution scenario","volume":"13","author":"Pellestor","year":"2020","journal-title":"Mol. Cytogenet."},{"key":"ref_7","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_8","doi-asserted-by":"crossref","unstructured":"Bulteau, L., Fertin, G., Jean, G., and Komusiewicz, C. (2021, January 25\u201329). Sorting by Multi-cut Rearrangements. Proceedings of the SOFSEM 2021: Theory and Practice of Computer Science\u201447th International Conference on Current Trends in Theory and Practice of Computer Science, Bolzano-Bozen, Italy.","DOI":"10.1007\/978-3-030-67731-2_43"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Downey, R., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_11","unstructured":"Bulteau, L., H\u00fcffner, F., Komusiewicz, C., and Niedermeier, R. (2014). Multivariate algorithmics for NP-hard string problems. Bull. Eur. Assoc. Theor. Comput. Sci., 114, Available online: https:\/\/hal.archives-ouvertes.fr\/hal-01260610\/document."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/110851390","article-title":"Sorting by Transpositions Is Difficult","volume":"26","author":"Bulteau","year":"2012","journal-title":"SIAM J. Discret. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S0895480103433550","article-title":"Reversals and transpositions over finite alphabets","volume":"19","author":"Radcliffe","year":"2005","journal-title":"SIAM J. Discret. Math."},{"key":"ref_14","unstructured":"Christie, D.A. (1998). Genome Rearrangement Problems. [Ph.D. Thesis, University of Glasgow]."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1089\/cmb.2005.12.102","article-title":"An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species","volume":"12","author":"Lin","year":"2005","journal-title":"J. Comput. Biol."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Kolman, P., Goldstein, A., and Zheng, J. (2005). Minimum Common String Partition Problem: Hardness and Approximations. Electron. J. Comb., 12.","DOI":"10.37236\/1947"},{"key":"ref_17","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bulteau, L., and Komusiewicz, C. (2014, January 5\u20137). Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, USA.","DOI":"10.1137\/1.9781611973402.8"},{"key":"ref_19","first-page":"251","article-title":"The Median Problem for Breakpoints in Comparative Genomics","volume":"Volume 1276","author":"Sankoff","year":"1997","journal-title":"Proceedings of the Computing and Combinatorics, Third Annual International Conference, COCOON \u201997"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/169\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:08:52Z","timestamp":1760162932000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,29]]},"references-count":19,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060169"],"URL":"https:\/\/doi.org\/10.3390\/a14060169","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,5,29]]}}}