{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:27:46Z","timestamp":1751282866027},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540612582"},{"type":"electronic","value":"9783540683902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61258-0_14","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:21:05Z","timestamp":1330273265000},"page":"168-185","source":"Crossref","is-referenced-by-count":61,"title":["Fast sorting by reversal"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sridhar","family":"Hannenhalli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/0097-3165(87)90022-7","volume":"45","author":"M. Aigner","year":"1987","unstructured":"M. Aigner and D. B. West. Sorting by insertion of leading element. Journal of Combinatorial Theory, 45:306\u2013309, 1987.","journal-title":"Journal of Combinatorial Theory"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"V. Bafna and P. Pevzner. Genome rearrangements and sorting by reversals. In 34th Annual IEEE Symposium on Foundations of Computer Science, pages 148\u2013157, 1993. (to appear in SIAM J. Computing).","DOI":"10.1109\/SFCS.1993.366872"},{"key":"14_CR3","first-page":"239","volume":"12","author":"V. Bafna","year":"1995","unstructured":"V. Bafna and P. Pevzner. Sorting by reversals: Genome rearrangements in plant organelles and evolutionary history of X chromosome. Mol. Biol. and Evol., 12:239\u2013246, 1995a.","journal-title":"Mol. Biol. and Evol."},{"key":"14_CR4","unstructured":"V. Bafna and P. Pevzner. Sorting by transpositions. In Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 614\u2013623, 1995b."},{"key":"14_CR5","unstructured":"D. Cohen and M. Blum. Improved bounds for sorting pancakes under a conjecture. 1993 (manuscript)."},{"key":"14_CR6","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0196-6774(81)90029-8","volume":"2","author":"S. Even","year":"1981","unstructured":"S. Even and O. Goldreich. The minimum-length generator sequence problem is NP-hard. Journal of Algorithms, 2:311\u2013313, 1981.","journal-title":"Journal of Algorithms"},{"key":"14_CR7","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W. H. Gates","year":"1979","unstructured":"W. H. Gates and C. H. Papadimitriou. Bounds for sorting by prefix reversals. Discrete Mathematics, 27:47\u201357, 1979.","journal-title":"Discrete Mathematics"},{"key":"14_CR8","first-page":"162","volume-title":"Lecture Notes in Computer Science","author":"S. Hannenhalli","year":"1995","unstructured":"S. Hannenhalli. Polynomial algorithm for computing translocation distance between genomes. In Combinatorial Pattern Matching, Proc. 6th Annual Symposium (CPM'95), Lecture Notes in Computer Science, pages 162\u2013176. Springer-Verlag, Berlin, 1995."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"S. Hannenhalli and P. Pevzner. Transforming cabbage into turnip (polynomial algorithm for sorting signed permutations by reversals). In Proc. 27th Annual ACM Symposium on the Theory of Computing, pages 178\u2013189, 1995a.","DOI":"10.1145\/225058.225112"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"S. Hannenhalli and P. Pevzner. Transforming men into mice (polynomial algorithm for genomic distance problem). In 36th Annual IEEE Symposium on Foundations of Computer Science, pages 581\u2013592, 1995c.","DOI":"10.1109\/SFCS.1995.492588"},{"key":"14_CR11","unstructured":"S. Hannenhalli and P. Pevzner. To cut... or not to cut (applications of comparative physical maps in molecular evolution). In Seventh Anuual ACM-SIAM Symposium on Discrete Algorithms, pages 304\u2013313, 1996."},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"M. Heydari and I. H. Sudborough. On sorting by prefix reversals and the diameter of pancake networks. 1993 (manuscript).","DOI":"10.1007\/3-540-56731-3_21"},{"key":"14_CR13","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"M. Jerrum","year":"1985","unstructured":"M. Jerrum. The complexity of finding minimum-length generator sequences. Theoretical Computer Science, 36:265\u2013289, 1985.","journal-title":"Theoretical Computer Science"},{"key":"14_CR14","unstructured":"J. Kececioglu and D. Gusfield. Reconstructing a history of recombinations from a set of sequences. In 5th Annual ACM-SIAM Symp. on Discrete Algorithms, pages 471\u2013480, 1994."},{"key":"14_CR15","unstructured":"J. Kececioglu and R. Ravi. Of mice and men: Evolutionary distances between genomes under translocation. In Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 604\u2013613, 1995."},{"key":"14_CR16","first-page":"87","volume-title":"volume 684 of Lecture Notes in Computer Science","author":"J. Kececioglu","year":"1993","unstructured":"J. Kececioglu and D. Sankoff. Exact and approximation algorithms for the inversion distance between two permutations. In Combinatorial Pattern Matching, Proc. 4th Annual Symposium (CPM'93), volume 684 of Lecture Notes in Computer Science, pages 87\u2013105. Springer-Verlag, Berlin, 1993. (Extended version has appeared in Algorithmica, 13: 180\u2013210, 1995.)."},{"key":"14_CR17","first-page":"307","volume-title":"volume 807 of Lecture Notes in Computer Science 807","author":"J. Kececioglu","year":"1994","unstructured":"J. Kececioglu and D. Sankoff. Efficient bounds for oriented chromosome inversion distance. In Combinatorial Pattern Matching, Proc. 5th Annual Symposium (CPM'94), volume 807 of Lecture Notes in Computer Science 807, pages 307\u2013325. Springer-Verlag, Berlin, 1994."},{"key":"14_CR18","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1128\/MCB.8.4.1474","volume":"8","author":"C. A. Makaroff","year":"1988","unstructured":"C. A. Makaroff and J. D. Palmer. Mitochondrial DNA rearrangements and transcriptional alterations in the male sterile cytoplasm of Ogura radish. Molecular Cellular Biology, 8:1474\u20131480, 1988.","journal-title":"Molecular Cellular Biology"},{"key":"14_CR19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF02143500","volume":"27","author":"J. D. Palmer","year":"1988","unstructured":"J. D. Palmer and L. A. Herbon. Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence. Journal of Molecular Evolution, 27:87\u201397, 1988.","journal-title":"Journal of Molecular Evolution"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"P.A. Pevzner and M.S. Waterman. Open combinatorial problems in computational molecular biology. In 3rd Israel Symposium on Theory of Computing and Systems, pages 158\u2013163. IEEE Computer Society Press, 1995.","DOI":"10.1109\/ISTCS.1995.377035"},{"key":"14_CR21","first-page":"121","volume-title":"volume 644 of Lecture Notes in Computer Science","author":"D. Sankoff","year":"1992","unstructured":"D. Sankoff. Edit distance for genome comparison based on non-local operations. In Combinatorial Pattern Matching, Proc. 3rd Annual Symposium (CPM'92), volume 644 of Lecture Notes in Computer Science, pages 121\u2013135. Springer-Verlag, Berlin, 1992."},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"D. Sankoff, R. Cedergren, and Y. Abel. Genomic divergence through gene rearrangement. In Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences, chapter 26, pages 428\u2013438. Academic Press, 1990.","DOI":"10.1016\/0076-6879(90)83028-8"},{"key":"14_CR23","doi-asserted-by":"crossref","first-page":"6575","DOI":"10.1073\/pnas.89.14.6575","volume":"89","author":"D. Sankoff","year":"1992","unstructured":"D. Sankoff, G. Leduc, N. Antoine, B. Paquin, B. F. Lang, and R. Cedergren. Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. USA, 89:6575\u20136579, 1992.","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61258-0_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:04:39Z","timestamp":1605629079000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61258-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540612582","9783540683902"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-61258-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}