{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:09:07Z","timestamp":1781323747011,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1995,2,1]],"date-time":"1995-02-01T00:00:00Z","timestamp":791596800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1995,2]]},"DOI":"10.1007\/bf01188586","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T21:03:45Z","timestamp":1108674225000},"page":"180-210","source":"Crossref","is-referenced-by-count":194,"title":["Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement"],"prefix":"10.1007","volume":"13","author":[{"given":"J.","family":"Kececioglu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D.","family":"Sankoff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01188586_CR1","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1016\/0097-3165(87)90022-7","volume":"45","author":"M. Aigner","year":"1987","unstructured":"Aigner, M., and D. B. West. Sorting by insertion of leading elements.Journal of Combinatorial Theory, Series A,45, 306\u2013309, 1987.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"BF01188586_CR2","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/0196-6774(89)90037-0","volume":"10","author":"N. Amato","year":"1989","unstructured":"Amato, N., M. Blum, S. Irani, and R. Rubinfeld. Reversing trains: a turn of the century sorting problem.Journal of Algorithms,10, 413\u2013428, 1989.","journal-title":"Journal of Algorithms"},{"key":"BF01188586_CR3","doi-asserted-by":"crossref","unstructured":"Bafna, V., and P. A. Pevzner. Genome rearrangements and sorting by reversals.Proceedings of the 34th Symposium on Foundations of Computer Science, November 1993, pp. 148\u2013157.","DOI":"10.1109\/SFCS.1993.366872"},{"key":"BF01188586_CR4","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0092-8674(81)90300-7","volume":"26","author":"M. J. Bibb","year":"1981","unstructured":"Bibb, M. J., R. A. van Etten, C. T. Wright, M. W. Walberg, and D. A. Clayton. Sequence and gene organization of mouse mitochondrial DNA.Cell,26, 167\u2013180, 1981.","journal-title":"Cell"},{"key":"BF01188586_CR5","volume-title":"Genetics of the Evolutionary Process","author":"T. Dobzhansky","year":"1970","unstructured":"Dobzhansky, T.Genetics of the Evolutionary Process. Columbia University Press, New York, 1970."},{"key":"BF01188586_CR6","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0890-5401(87)90043-5","volume":"72","author":"J. R. Driscoll","year":"1987","unstructured":"Driscoll, J. R., and M. L. Furst. Computing short generator sequences.Information and Computation,72, 117\u2013132, 1987.","journal-title":"Information and Computation"},{"key":"BF01188586_CR7","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0196-6774(81)90029-8","volume":"2","author":"S. Even","year":"1981","unstructured":"Even, S., 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":"BF01188586_CR8","doi-asserted-by":"crossref","unstructured":"Furst, M., J. Hopcroft, and E. Luks. Polynomial-time algorithms for permutation groups.Proceedings of the 21st Symposium on Foundations of Computer Science, 1980, pp. 36\u201341.","DOI":"10.1109\/SFCS.1980.34"},{"key":"BF01188586_CR9","volume-title":"Computers and Intractability: A Guide to The Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., and D. S. Johnson.Computers and Intractability: A Guide to The Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"BF01188586_CR10","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(79)90068-2","volume":"27","author":"W. H. Gates","year":"1979","unstructured":"Gates, W. H., and C. H. Papadimitriou. Bounds for sorting by prefix reversal.Discrete Mathematics,27, 47\u201357, 1979.","journal-title":"Discrete Mathematics"},{"key":"BF01188586_CR11","unstructured":"Golan, H. Personal communication, 1991."},{"key":"BF01188586_CR12","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"M. R. Jerrum","year":"1985","unstructured":"Jerrum, M. R. The complexity of finding minimum-length generator sequences.Theoretical Computer Science,36, 265\u2013289, 1985.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"BF01188586_CR13","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"D. B. Johnson","year":"1975","unstructured":"Johnson, D. B. Finding all the elementary circuits of a directed graph.SIAM Journal on Computing,4(1), 77\u201384, 1975.","journal-title":"SIAM Journal on Computing"},{"key":"BF01188586_CR14","first-page":"87","volume-title":"Lecture Notes in Computer Science, vol. 684","author":"J. Kececioglu","year":"1993","unstructured":"Kececioglu, J., and D. Sankoff. Exact and approximation algorithms for the inversion distance between two chromosomes.Proceedings of the 4th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 684, Springer-Verlag, Berlin, June 1993, pp. 87\u2013105. (An earlier version appeared as \u201cExact and approximation algorithms for sorting by reversals,\u201d Technical Report 1824, Centre de recherches math\u00e9matiques, Universit\u00e9 de Montr\u00e9al, July 1992)."},{"key":"BF01188586_CR15","first-page":"307","volume-title":"Lecture Notes in Computer Science, vol. 807","author":"J. Kececioglu","year":"1994","unstructured":"Kececioglu, J., and D. Sankoff. Efficient bounds for oriented chromosome-inversion distance.Proceedings of the 5th Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 807, Springer-Verlag, Berlin, June 1994, pp. 307\u2013325."},{"key":"BF01188586_CR16","volume-title":"The Art of Computer Programming, Vol. 3","author":"D. E. Knuth","year":"1973","unstructured":"Knuth, D. E.The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, MA, 1973."},{"key":"BF01188586_CR17","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"34","author":"H. Mannila","year":"1985","unstructured":"Mannila, H. Measures of presortedness and optimal sorting algorithms,IEEE Transactions on Computers, 34, 318\u2013325, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"BF01188586_CR18","doi-asserted-by":"crossref","unstructured":"Micali, S. and V. Vazirani. Ano(\u221a\u00a6V\u00a6\u00b7\u00a6E\u00a6) algorithm for finding maximum matchings in general graphs.Proceedings of the 21st Symposium on Foundations of Computer Science, 1980, pp. 17\u201327.","DOI":"10.1109\/SFCS.1980.12"},{"key":"BF01188586_CR19","doi-asserted-by":"crossref","first-page":"814","DOI":"10.1073\/pnas.81.3.814","volume":"81","author":"J. H. Nadeau","year":"1984","unstructured":"Nadeau, J. H., and B. A. Taylor. Lengths of chromosomal segments conserved since divergence of man and mouse.Proceedings of the National Academy of Sciences of the USA,81, 814, 1984.","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"BF01188586_CR20","volume-title":"Genetic Maps: Locus Maps of Complex Genomes","year":"1993","unstructured":"O'Brien, S. J., ed.Genetic Maps: Locus Maps of Complex Genomes. 6th edition. Cold Spring Harbor Laboratory Press, Cold Spring Harbor, NY, 1993.","edition":"6th edition"},{"key":"BF01188586_CR21","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF00405856","volume":"14","author":"J. D. Palmer","year":"1988","unstructured":"Palmer, J. D., B. Osorio, and W. F. Thompson. Evolutionary significance of inversions in legume chloroplast DNAs.Current Genetics,14, 65\u201374, 1988.","journal-title":"Current Genetics"},{"key":"BF01188586_CR22","doi-asserted-by":"crossref","first-page":"6575","DOI":"10.1073\/pnas.89.14.6575","volume":"89","author":"D. Sankoff","year":"1992","unstructured":"Sankoff, D., G. Leduc, N. Antoine, B. Paquin, B. F. Lang, and R. Cedergren. Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome.Proceedings of the National Academy of Sciences of the USA,89, 6575\u20136579, 1992.","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"BF01188586_CR23","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/BF02459633","volume":"54","author":"M. Sch\u00f6niger","year":"1992","unstructured":"Sch\u00f6niger, M., and M. S. Waterman. A local algorithm for DNA sequence alignment with inversions.Bulletin of Mathematical Biology,54, 521\u2013536, 1992.","journal-title":"Bulletin of Mathematical Biology"},{"key":"BF01188586_CR24","first-page":"156","volume-title":"Molecular Systematics","author":"S. K. Sessions","year":"1990","unstructured":"Sessions, S. K. Chromosomes: molecular cytogenetics. InMolecular Systematics, D. M. Hillis and C. Moritz, eds., Sinauer, Sunderland, MA, 1990, pp. 156\u2013204."},{"issue":"4","key":"BF01188586_CR25","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/357401.357404","volume":"2","author":"W. F. Tichy","year":"1984","unstructured":"Tichy, W. F. The string-to-string correction problem with block moves.ACM Transactions on Computer Systems,2(4), 309\u2013321, 1984.","journal-title":"ACM Transactions on Computer Systems"},{"key":"BF01188586_CR26","first-page":"215","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"R. A. Wagner","year":"1983","unstructured":"Wagner, R. A. On the complexity of the extended string-to-string correction problem. InTime Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, D. Sankoft and J. B. Kruskal, eds., Addison-Wesley, Reading, MA, 1983, pp. 215\u2013235."},{"key":"BF01188586_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0022-5193(82)90384-8","volume":"99","author":"G. A. Watterson","year":"1982","unstructured":"Watterson, G. A., W. J. Ewens, T. E. Hall, and A. Morgan. The chromosome inversion problem.Journal of Theoretical Biology,99, 1\u20137, 1982.","journal-title":"Journal of Theoretical Biology"},{"key":"BF01188586_CR28","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1073\/pnas.84.5.1324","volume":"84","author":"D. R. Wolstenholme","year":"1987","unstructured":"Wolstenholme, D. R., J. L. MacFarlane, R. Okimoto, D. O. Clary, and J. A. Wahieithner. Bizarre tRNAs inferred from DNA sequences of mitochondrial genomes of nematode worms.Proceedings of the National Academy of Sciences of the USA,84, 1324\u20131328, 1987.","journal-title":"Proceedings of the National Academy of Sciences of the USA"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188586.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188586\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188586","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:33:59Z","timestamp":1586118839000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,2]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,2]]}},"alternative-id":["BF01188586"],"URL":"https:\/\/doi.org\/10.1007\/bf01188586","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,2]]}}}