{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:17Z","timestamp":1759638737695,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2015,1,7]],"date-time":"2015-01-07T00:00:00Z","timestamp":1420588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"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 and 2014\/04718-6"],"award-info":[{"award-number":["2013\/08293-7 and 2014\/04718-6"]}],"id":[{"id":"10.13039\/501100001807","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","id":[{"id":"10.13039\/501100002322","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":["306730\/2012-0, 477692\/2012-5, and 483370\/2013-4"],"award-info":[{"award-number":["306730\/2012-0, 477692\/2012-5, and 483370\/2013-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2015,2,3]]},"abstract":"<jats:p>\n            We consider the combinatorial problem of sorting a permutation using a minimum number of rearrangement events, which finds application in the estimation of evolutionary distance between species. Many variants of this problem, which we generically refer to as the rearrangement sorting problem, have been tackled in the literature, and for most of them, the best known algorithms are approximations or heuristics. In this article, we present a tool, called\n            <jats:italic>GRAAu<\/jats:italic>\n            , to aid in the evaluation of the results produced by these algorithms. To illustrate its application, we use GRAAu to evaluate the results of four approximation algorithms regarding two variants of the rearrangement sorting problem: the problem of sorting by prefix reversals and the problem of sorting by prefix transpositions. As a result, we show that the approximation ratios of three algorithms are tight and conjecture that the approximation ratio of the remaining one is also tight.\n          <\/jats:p>","DOI":"10.1145\/2661633","type":"journal-article","created":{"date-parts":[[2014,10,21]],"date-time":"2014-10-21T12:36:57Z","timestamp":1413895017000},"source":"Crossref","is-referenced-by-count":1,"title":["An Audit Tool for Genome Rearrangement Algorithms"],"prefix":"10.1145","volume":"19","author":[{"given":"Gustavo Rodrigues","family":"Galv\u00e3o","sequence":"first","affiliation":[{"name":"University of Campinas, Brazil"}]},{"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[{"name":"University of Campinas, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2015,1,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1089\/106652701753216503"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250627"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"volume":"4580","volume-title":"Combinatorial Pattern Matching. Lecture Notes in Computer Science","author":"Beno\u00eet-Gagn\u00e9 M.","key":"e_1_2_1_4_1"},{"volume":"2461","volume-title":"Lecture Notes in Computer Science","author":"Berman P.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_24"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/110851390"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019731994X"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.045"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.11.018"},{"key":"e_1_2_1_11_1","unstructured":"D. A. Christie. 1998. Genome Rearrangement Problems. Ph.D. Dissertation. University of Glasgow Glasgow Scotland.  D. A. Christie. 1998. Genome Rearrangement Problems. Ph.D. Dissertation. University of Glasgow Glasgow Scotland."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00009-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1854776.1854823"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219720013500133"},{"volume":"2476","volume-title":"String Processing and Information Retrieval. Lecture Notes in Computer Science","author":"Dias Z.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2318261"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2006.44"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00150-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"G. Fertin A. Labarre I. Rusu E. Tannier and S. Vialette. 2009. Combinatorics of Genome Rearrangements. MIT Press Cambridge MA.   G. Fertin A. Labarre I. Rusu E. Tannier and S. Vialette. 2009. Combinatorics of Genome Rearrangements. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/9780262062824.001.0001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_38"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.02.002"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00092-9"},{"volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS\u201995)","year":"1995","author":"Hannenhalli S.","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.12.006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0874"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01188586"},{"key":"e_1_2_1_27_1","unstructured":"A. Labarre. 2008. Combinatorial Aspects of Genome Rearrangements and Haplotype Networks. Ph.D. Dissertation. Universit\u00e9 Libre de Bruxelles Brussels Belgium.  A. Labarre. 2008. Combinatorial Aspects of Genome Rearrangements and Haplotype Networks. Ph.D. Dissertation. Universit\u00e9 Libre de Bruxelles Brussels Belgium."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/13090897X"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/080741860"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1089\/106652702761034163"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.005"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00141-7"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.09.002"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2010.05.030"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2005.02.033"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/18.3.492"},{"key":"e_1_2_1_37_1","unstructured":"J. P. C. Vergara. 1998. Sorting by Bounded Permutations. Ph.D. Dissertation. Virginia Polytechnic Institute and State University Blacksburg VA.   J. P. C. Vergara. 1998. Sorting by Bounded Permutations. Ph.D. Dissertation. Virginia Polytechnic Institute and State University Blacksburg VA."},{"volume-title":"Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE\u201998)","year":"1998","author":"Walter M. E. M. T.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/829519.830850"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.012"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-5193(82)90384-8"},{"volume-title":"Fun With Algorithms","series-title":"Lecture Notes in Computer Science","author":"Williams A.","key":"e_1_2_1_42_1"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661633","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2661633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:15Z","timestamp":1750231695000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2661633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,7]]},"references-count":42,"alternative-id":["10.1145\/2661633"],"URL":"https:\/\/doi.org\/10.1145\/2661633","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2015,1,7]]}}}