{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:31:40Z","timestamp":1740137500668,"version":"3.37.3"},"reference-count":25,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e1 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2013\/01172-0"],"award-info":[{"award-number":["2013\/01172-0"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e1 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2014\/20738-7"],"award-info":[{"award-number":["2014\/20738-7"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e1 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2014\/19401-8"],"award-info":[{"award-number":["2014\/19401-8"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e1 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\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["477692\/2012-5"],"award-info":[{"award-number":["477692\/2012-5"]}],"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":["483370\/2013-4"],"award-info":[{"award-number":["483370\/2013-4"]}],"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":["831\/15"],"award-info":[{"award-number":["831\/15"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2017,2]]},"abstract":"<jats:p> Some interesting combinatorial problems have been motivated by genome rearrangements, which are mutations that affect large portions of a genome. When we represent genomes as permutations, the goal is to transform a given permutation into the identity permutation with the minimum number of rearrangements. When they affect segments from the beginning (respectively end) of the permutation, they are called prefix (respectively suffix) rearrangements. This paper presents results for rearrangement problems that involve prefix and suffix versions of reversals and transpositions considering unsigned and signed permutations. We give 2-approximation and ([Formula: see text])-approximation algorithms for these problems, where [Formula: see text] is a constant divided by the number of breakpoints (pairs of consecutive elements that should not be consecutive in the identity permutation) in the input permutation. We also give bounds for the diameters concerning these problems and provide ways of improving the practical results of our algorithms. <\/jats:p>","DOI":"10.1142\/s0219720017500020","type":"journal-article","created":{"date-parts":[[2017,2,9]],"date-time":"2017-02-09T22:39:04Z","timestamp":1486679944000},"page":"1750002","source":"Crossref","is-referenced-by-count":6,"title":["Sorting permutations by prefix and suffix rearrangements"],"prefix":"10.1142","volume":"15","author":[{"given":"Carla Negri","family":"Lintzmayer","sequence":"first","affiliation":[{"name":"Institute of Computing, University of Campinas, Campinas, S\u00e3o Paulo, 13083-852, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[{"name":"Laboratoire des Sciences du Num\u00e9rique de Nantes, UMR CNRS 6004, University of Nantes, 44322 Nantes Cedex 3, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[{"name":"Laboratoire des Sciences du Num\u00e9rique de Nantes, UMR CNRS 6004, University of Nantes, 44322 Nantes Cedex 3, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2017,2,26]]},"reference":[{"key":"S0219720017500020BIB001","doi-asserted-by":"publisher","DOI":"10.2307\/2318261"},{"key":"S0219720017500020BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90068-2"},{"key":"S0219720017500020BIB004","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0874"},{"key":"S0219720017500020BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.045"},{"key":"S0219720017500020BIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.02.003"},{"key":"S0219720017500020BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.028"},{"key":"S0219720017500020BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00009-3"},{"key":"S0219720017500020BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.44"},{"issue":"3","key":"S0219720017500020BIB012","first-page":"1148","volume":"26","author":"Bulteau L","year":"2012","journal-title":"SIAM J Comput"},{"key":"S0219720017500020BIB013","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019731994X"},{"key":"S0219720017500020BIB014","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250627"},{"key":"S0219720017500020BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00150-9"},{"key":"S0219720017500020BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/300515.300516"},{"key":"S0219720017500020BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.02.033"},{"key":"S0219720017500020BIB018","doi-asserted-by":"publisher","DOI":"10.1089\/106652701753216503"},{"key":"S0219720017500020BIB019","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"S0219720017500020BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.09.002"},{"key":"S0219720017500020BIB022","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"key":"S0219720017500020BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9369-8"},{"key":"S0219720017500020BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.059"},{"key":"S0219720017500020BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2015.03.007"},{"key":"S0219720017500020BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.09.004"},{"key":"S0219720017500020BIB031","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720013500133"},{"key":"S0219720017500020BIB032","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720014500127"},{"key":"S0219720017500020BIB033","first-page":"1.7:1.1","volume":"19","author":"Galv\u00e3o GR","year":"2015","journal-title":"J Exp Algor"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720017500020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T18:30:14Z","timestamp":1569954614000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720017500020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2]]},"references-count":25,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2017,2,26]]},"published-print":{"date-parts":[[2017,2]]}},"alternative-id":["10.1142\/S0219720017500020"],"URL":"https:\/\/doi.org\/10.1142\/s0219720017500020","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"type":"print","value":"0219-7200"},{"type":"electronic","value":"1757-6334"}],"subject":[],"published":{"date-parts":[[2017,2]]}}}