{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T21:12:37Z","timestamp":1770325957630,"version":"3.49.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T00:00:00Z","timestamp":1427241600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/s13015-015-0040-x","type":"journal-article","created":{"date-parts":[[2015,3,24]],"date-time":"2015-03-24T15:08:47Z","timestamp":1427209727000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Sorting signed permutations by short operations"],"prefix":"10.1186","volume":"10","author":[{"given":"Gustavo Rodrigues","family":"Galv\u00e3o","sequence":"first","affiliation":[]},{"given":"Orlando","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Zanoni","family":"Dias","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,3,25]]},"reference":[{"key":"40_CR1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198566106.001.0001","volume-title":"Mathematics of evolution and phylogeny","author":"O Gascuel","year":"2005","unstructured":"Gascuel O. Mathematics of evolution and phylogeny. New York, New York, USA: Oxford University Press, Inc.; 2005."},{"issue":"1","key":"40_CR2","first-page":"406","volume":"4","author":"N Saitou","year":"1987","unstructured":"Saitou N, Nei M. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol. 1987; 4(1):406\u201325.","journal-title":"Mol Biol Evol."},{"key":"40_CR3","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9780262062824.001.0001","volume-title":"Combinatorics of genome rearrangements","author":"G Fertin","year":"2009","unstructured":"Fertin G, Labarre A, Rusu I, Tannier E, Vialette S. Combinatorics of genome rearrangements. Cambridge, Massachusetts, USA: The MIT Press; 2009."},{"issue":"1","key":"40_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A Caprara","year":"1999","unstructured":"Caprara A. Sorting permutations by reversals and eulerian cycle decompositions. SIAM J Discrete Math. 1999; 12(1):91\u2013110.","journal-title":"SIAM J Discrete Math."},{"issue":"1","key":"40_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","volume":"99","author":"GA Watterson","year":"1982","unstructured":"Watterson GA, Ewens WJ, Hall TE, Morgan A. The chromosome inversion problem. J Theor Biol. 1982; 99(1):1\u20137.","journal-title":"J Theor Biol."},{"key":"40_CR6","volume-title":"Proceedings of the 10th Annual European Symposium on Algorithms (ESA\u20192002), Lecture Notes in Computer Science, vol.2461","author":"P Berman","year":"2002","unstructured":"Berman P, Hannenhalli S, Karpinski M. 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. Rome, Italy: Springer: 2002. p. 200\u201310."},{"issue":"2","key":"40_CR7","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V Bafna","year":"1996","unstructured":"Bafna V, Pevzner PA. Genome rearrangements and sorting by reversals. SIAM J Comput. 1996; 25(2):272\u201389.","journal-title":"SIAM J Comput."},{"issue":"1","key":"40_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/300515.300516","volume":"46","author":"S Hannenhalli","year":"1999","unstructured":"Hannenhalli S, Pevzner PA. Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. J. ACM. 1999; 46(1):1\u201327.","journal-title":"J. ACM"},{"issue":"6-7","key":"40_CR9","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1016\/j.dam.2005.02.033","volume":"155","author":"E Tannier","year":"2007","unstructured":"Tannier E, Bergeron A, Sagot MF. Advances on sorting by reversals. Discrete Appl Math. 2007; 155(6-7):881\u20138.","journal-title":"Discrete Appl Math."},{"issue":"5","key":"40_CR10","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1089\/106652701753216503","volume":"8","author":"D Bader","year":"2001","unstructured":"Bader D, Moret B, Yan M. A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. J Comput Biol. 2001; 8(5):483\u201391.","journal-title":"J Comput Biol."},{"issue":"3","key":"40_CR11","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. Sorting by transpositions is difficult. SIAM J Discrete Math. 2012; 26(3):1148\u201380.","journal-title":"SIAM J Discrete Math."},{"issue":"2","key":"40_CR12","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V Bafna","year":"1998","unstructured":"Bafna V, Pevzner PA. Sorting by transpositions. SIAM J Discrete Math. 1998; 11(2):224\u201340.","journal-title":"SIAM J Discrete Math."},{"issue":"4","key":"40_CR13","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. A 1.375-approximation algorithm for sorting by transpositions. IEEE\/ACM Trans Comput Biol Bioinf. 2006; 3(4):369\u201379.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf."},{"key":"40_CR14","volume-title":"Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE\u20191998)","author":"MEMT Walter","year":"1998","unstructured":"Walter MEMT, Dias Z, Meidanis J. Reversal and transposition distance of linear chromosomes. In: Proceedings of the 5th International Symposium on String Processing and Information Retrieval (SPIRE\u20191998). Santa Cruz, Bolivia: IEEE Computer Society: 1998. p. 96\u2013102."},{"issue":"3","key":"40_CR15","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. An approximation algorithm for sorting by reversals and transpositions. J Discrete Algorithms. 2008; 6(3):449\u201357.","journal-title":"J Discrete Algorithms"},{"issue":"2","key":"40_CR16","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0304-3975(98)00092-9","volume":"210","author":"Q Gu","year":"1999","unstructured":"Gu Q, Peng S, Sudborough IH. A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theor Comput Sci. 1999; 210(2):327\u201339.","journal-title":"Theor Comput Sci."},{"key":"40_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"MR Jerrum","year":"1985","unstructured":"Jerrum MR. The complexity of finding minimum-length generator sequences. Theor Comput Sci. 1985; 36:265\u201389.","journal-title":"Theor Comput Sci."},{"issue":"5","key":"40_CR18","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1089\/106652703322539097","volume":"10","author":"LS Heath","year":"2003","unstructured":"Heath LS, Vergara JPC. Sorting by short swaps. J Comput Biol. 2003; 10(5):775\u201389.","journal-title":"J Comput Biol."},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0166-218X(98)00072-9","volume":"88","author":"LS Heath","year":"1998","unstructured":"Heath LS, Vergara JPC. Sorting by bounded block-moves. Discrete Appl Math. 1998; 88:181\u2013206.","journal-title":"Discrete Appl Math."},{"issue":"3","key":"40_CR20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s004530010041","volume":"28","author":"LS Heath","year":"2000","unstructured":"Heath LS, Vergara JPC. Sorting by short blockmoves. Algorithmica. 2000; 28(3):323\u201354.","journal-title":"Algorithmica"},{"key":"40_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.03.019","volume":"439","author":"H Jiang","year":"2012","unstructured":"Jiang H, Zhu D, Zhu B. A (1+ \u03b5)-approximation algorithm for sorting by short block-moves. Theor Comput Sci. 2012; 439:1\u20138.","journal-title":"Theor Comput Sci."},{"key":"40_CR22","volume-title":"Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC\u20192014), Lecture Notes in Computer Science, vol.8889","author":"H Jiang","year":"2014","unstructured":"Jiang H, Feng H, Zhu D. An 5\/4-approximation algorithm for sorting permutations by short block moves. In: Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC\u20192014), Lecture Notes in Computer Science, vol.8889. Jeonju, Korea: Springer: 2014. p. 491\u2013503."},{"key":"40_CR23","volume-title":"Sorting by bounded permutations","author":"JPC Vergara","year":"1998","unstructured":"Vergara JPC. Sorting by bounded permutations. USA: Virginia Polytechnic Institute & State University: PhD thesis, Blacksburg, VA; 1998."},{"issue":"1","key":"40_CR24","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s00239-001-0087-9","volume":"55","author":"DA Dalevi","year":"2002","unstructured":"Dalevi DA, Eriksen N, Eriksson K, Andersson SGE. Measuring genome divergence in bacteria: a case study using chlamydian data. J Mol Evol. 2002; 55(1):24\u201336.","journal-title":"J Mol Evol."},{"issue":"suppl 1","key":"40_CR25","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btg1025","volume":"19","author":"JF Lefebvre","year":"2003","unstructured":"Lefebvre JF, El-Mabrouk N, Tillier E, Sankoff D. Detection and validation of single gene inversions. Bioinformatics. 2003; 19(suppl 1):190\u20136.","journal-title":"Bioinformatics"},{"key":"40_CR26","volume-title":"Comparative Genomics, Computational Biology, vol.1","author":"A McLysaght","year":"2000","unstructured":"McLysaght A, Seoighe C, Wolfe KH. High frequency of inversions during eukaryote gene order evolution In: Sankoff D, Nadeau JH, editors. Comparative Genomics, Computational Biology, vol.1. Dordrecht, The Netherlands: Kluwer Academic Publishers: 2000. p. 47\u201358."},{"issue":"26","key":"40_CR27","doi-asserted-by":"publisher","first-page":"14433","DOI":"10.1073\/pnas.240462997","volume":"97","author":"C Seoighe","year":"2000","unstructured":"Seoighe C, Federspiel N, Jones T, Hansen N, Bivolarovic V, Surzycki R, et al. Prevalence of small inversions in yeast gene order evolution. Proc Nat Acad Sci U S A. 2000; 97(26):14433\u20137.","journal-title":"Proc Nat Acad Sci U S A."},{"key":"40_CR28","volume-title":"Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB\u20192014)","author":"GR Galv\u00e3o","year":"2014","unstructured":"Galv\u00e3o GR, Dias Z. Approximation algorithms for sorting by signed short reversals. In: Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB\u20192014). Newport Beach, California, USA: ACM Press: 2014. p. 360\u20139."},{"key":"40_CR29","volume-title":"Proceedings of the 21th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"TM Chan","year":"2010","unstructured":"Chan TM, P\u0103tra\u015fcu M. Counting inversions, offline orthogonal range counting, and related problems. In: Proceedings of the 21th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). Philadelphia, PA, USA: Society for Industrial and Applied Mathematics: 2010. p. 161\u201373."},{"issue":"21","key":"40_CR30","doi-asserted-by":"publisher","first-page":"2628","DOI":"10.1016\/j.disc.2006.11.014","volume":"307","author":"Y Koh","year":"2007","unstructured":"Koh Y, Ree S. Connected permutation graphs. Discrete Math. 2007; 307(21):2628\u201335.","journal-title":"Discrete Math."},{"issue":"Article 1.7","key":"40_CR31","first-page":"1.1","volume":"19","author":"GR Galv\u00e3o","year":"2014","unstructured":"Galv\u00e3o GR, Dias Z. An audit tool for genome rearrangement algorithms. ACM J Exp Algorithmics. 2014; 19(Article 1.7):1.1\u20131.34.","journal-title":"ACM J Exp Algorithmics"},{"key":"40_CR32","first-page":"103","volume":"13","author":"RY Pinter","year":"2002","unstructured":"Pinter RY, Skiena S. Genomic sorting with length-weighted reversals. Genome Inf. 2002; 13:103\u201311.","journal-title":"Genome Inf."},{"key":"40_CR33","volume-title":"Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM\u20192004), Lecture Notes in Computer Science, vol. 3109","author":"F Swidan","year":"2004","unstructured":"Swidan F, Bender MA, Ge D, He S, Hu H, Pinter RY. Sorting by length-weighted reversals: Dealing with signs and circularity. In: Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching (CPM\u20192004), Lecture Notes in Computer Science, vol. 3109. Istanbul, Turkey: Springer: 2004. p. 32\u201346."},{"issue":"5","key":"40_CR34","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1016\/j.jcss.2007.08.008","volume":"74","author":"MA Bender","year":"2008","unstructured":"Bender MA, Ge D, He S, Hu H, Pinter RY, Skiena S, et al. Improved bounds on sorting by length-weighted reversals. J Comput Syst Sci. 2008; 74(5):744\u2013774.","journal-title":"J Comput Syst Sci."},{"issue":"1","key":"40_CR35","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00285-013-0702-6","volume":"69","author":"A Egri-Nagy","year":"2014","unstructured":"Egri-Nagy A, Gebhardt V, Tanaka MM, Francis AR. Group-theoretic models of the inversion process in bacterial genomes. J Math Biol. 2014; 69(1):243\u201365.","journal-title":"J Math Biol."},{"issue":"7370","key":"40_CR36","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1038\/nature10549","volume":"478","author":"KI Bos","year":"2011","unstructured":"Bos KI, Schuenemann VJ, Golding GB, Burbano HA, Waglechner N, Coombes BK, et al. A draft genome of Yersinia pestis from victims of the black death. Nature. 2011; 478(7370):506\u201310.","journal-title":"Nature"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-015-0040-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-015-0040-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-015-0040-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-015-0040-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,8]],"date-time":"2024-06-08T00:33:37Z","timestamp":1717806817000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-015-0040-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,25]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["40"],"URL":"https:\/\/doi.org\/10.1186\/s13015-015-0040-x","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,25]]},"assertion":[{"value":"15 December 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}