{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:47:47Z","timestamp":1766065667348},"publisher-location":"Berlin\/Heidelberg","reference-count":21,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354056764X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029799","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T09:36:08Z","timestamp":1133429768000},"page":"87-105","source":"Crossref","is-referenced-by-count":38,"title":["Exact and approximation algorithms for the inversion distance between two chromosomes"],"prefix":"10.1007","author":[{"given":"John","family":"Kececioglu","sequence":"first","affiliation":[]},{"given":"David","family":"Sankoff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_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, Martin and Douglas 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":"8_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, Nancy, Manuel Blum, Sandra Irani, and Ronitt Rubinfeld. Reversing trains: a turn of the century sorting problem. Journal of Algorithms 10, 413\u2013428, 1989.","journal-title":"Journal of Algorithms"},{"key":"8_CR3","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0092-8674(81)90300-7","volume":"26","author":"J.J. Bibb","year":"1981","unstructured":"Bibb, J.J., R.A. van Etten, C.T. Wright, M.W. Walberg, and D.A. Clayton. Cell 26, 167\u2013180, 1981.","journal-title":"Cell"},{"key":"8_CR4","unstructured":"Dobzhansky, Theodosius. Genetics of the Evolutionary Process. Columbia Univeristy Press, 1970."},{"key":"8_CR5","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":"8_CR6","volume-title":"Computers and Intractability: A Guide to The Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, Michael R. and David S. Johnson. Computers and Intractability: A Guide to The Theory of NP-Completeness. W.H. Freeman, New York, 1979."},{"key":"8_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":"Gates, William H. and Christos H. Papadimitriou. Bounds for sorting by prefix reversal. Discrete Mathematics 27, 47\u201357, 1979.","journal-title":"Discrete Mathematics"},{"key":"8_CR8","unstructured":"Golan, Holger. Personal communication, 1991."},{"key":"8_CR9","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, Mark R. The complexity of finding minimum-length generator sequences. Theoretical Computer Science 36, 265\u2013289, 1985.","journal-title":"Theoretical Computer Science"},{"key":"8_CR10","unstructured":"Kececioglu, John and David Sankoff. Exact and approximation algorithms for the inversion distance between two chromosomes. To appear in Algorithmica."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Micali, S. and V. Vazirani. An O(\u221a\u00a6V\u00a6\u00b7\u00a6E\u00a6) algorithm for finding maximum matchings in general graphs. In Proceedings of the 21st Symposium on Foundations of Computer Science, 17\u201327, 1980.","DOI":"10.1109\/SFCS.1980.12"},{"key":"8_CR12","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 USA 81, 814, 1984.","journal-title":"Proceedings of the National Academy of Sciences USA"},{"key":"8_CR13","unstructured":"O'Brien, S.J., editor. Genetic Maps. Cold Spring Harbor Laboratory, 1987."},{"key":"8_CR14","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":"8_CR15","doi-asserted-by":"crossref","first-page":"6575","DOI":"10.1073\/pnas.89.14.6575","volume":"89","author":"D. Sankoff","year":"1992","unstructured":"Sankoff, David, Guillame Leduc, Natalie Antoine, Bruno Paquin, B. Franz Lang, and Robert Cedergren. Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proceedings of the National Academy of Sciences USA 89, 6575\u20136579, 1992.","journal-title":"Proceedings of the National Academy of Sciences USA"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/BF02459633","volume":"54","author":"M. Sch\u00f6niger","year":"1992","unstructured":"Sch\u00f6niger, Michael and Michael 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":"8_CR17","first-page":"156","volume-title":"Molecular Systematics","author":"S. K. Sessions","year":"1990","unstructured":"Sessions, Stanley K. Chromosomes: molecular cytogenetics. In Molecular Systematics, David M. Hillis and Craig Moritz editors, Sinauer, Sunderland, Massachusetts, 156\u2013204, 1990."},{"issue":"4","key":"8_CR18","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/357401.357404","volume":"2","author":"W. F. Tichy","year":"1984","unstructured":"Tichy, Walter 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":"8_CR19","first-page":"215","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Prac tice of Sequence Comparison","author":"R. A. Wagner","year":"1983","unstructured":"Wagner, Robert A. On the complexity of the extended string-to-string correction problem. In Time Warps, String Edits, and Macromolecules: The Theory and Prac tice of Sequence Comparison, David Sankoff and Joseph B. Kruskal, editors, Addison-Wesley, Reading Massachusetts, 215\u2013235, 1983."},{"key":"8_CR20","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":"8_CR21","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. Wahleithner. Proceedings of the National Academy of Sciences USA 84, 1324\u20131328, 1987.","journal-title":"Proceedings of the National Academy of Sciences USA"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T08:34:11Z","timestamp":1586594051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354056764X"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/bfb0029799","relation":{},"subject":[]}}