{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T06:55:56Z","timestamp":1742799356243},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676331"},{"type":"electronic","value":"9783540451235"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45123-4_22","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T19:59:14Z","timestamp":1194983954000},"page":"248-263","source":"Crossref","is-referenced-by-count":4,"title":["Structural Properties and Tractability Results for Linear Synteny"],"prefix":"10.1007","author":[{"given":"David","family":"Liben-Nowell","sequence":"first","affiliation":[]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,11,7]]},"reference":[{"issue":"1","key":"22_CR1","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1287\/opre.26.1.141","volume":"26","author":"H. M. Abdel-Wahab","year":"1978","unstructured":"H. M. Abdel-Wahab and T. Kameda. Scheduling to minimize maximum cumulative costs subject to series-parallel precedence constraints. Operations Research, 26(1):141\u2013158, January\/February 1978.","journal-title":"Operations Research"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Vineet Bafna and Pavel A. Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25(2):272\u2013289, April 1996. A previous version appeared in FOCS\u201993.","DOI":"10.1137\/S0097539793250627"},{"issue":"2","key":"22_CR3","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Vineet Bafna and Pavel A. Pevzner. Sorting by transpositions. SIAM Journal on Discrete Mathematics, 11(2):224\u2013240, 1998. A previous version appeared in SODA\u201995.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Piotr Berman and Marek Karpinski. On some tighter inapproximability results. Electronic Colloquium on Computational Complexity, Report No. 29, 1998.","DOI":"10.1007\/3-540-48523-6_17"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Alberto Caprara. Sorting by reversals is difficult. In 1st Annual International Conference on Computational Molecular Biology, pages 75\u201383, 1997.","DOI":"10.1145\/267521.267531"},{"key":"22_CR6","unstructured":"D. A. Christie. A 3\/2-approximation algorithm for sorting by reversals. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 244\u2013252, 1998."},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Bhaskar DasGupta, Tao Jiang, Sampath Kannan, Ming Li, and Elizabeth Sweedyk. On the complexity and approximation of syntenic distance. Discrete Applied Mathematics (special issue on computational biology), 88(1\u20133):59\u201382, November 1998. A previous version appeared in RECOMB\u201997.","DOI":"10.1016\/S0166-218X(98)00066-3"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Jason Ehrlich, David Sankoff, and Joseph H. Nadeau. Synteny conservation and chromosome rearrangements during mammalian evolution. Genetics, 147(1):289\u2013296, September 1997.","DOI":"10.1093\/genetics\/147.1.289"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Vincent Ferretti, Joseph H. Nadeau, and David Sankoff. Original synteny. In 7th Annual Symposium on Combinatorial Pattern Matching, pages 159\u2013167, 1996.","DOI":"10.1007\/3-540-61258-0_13"},{"key":"22_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979."},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"David Liben-Nowell. On the structure of syntenic distance. In 10th Annual Symposium on Combinatorial Pattern Matching, pages 43\u201356, 1999.","DOI":"10.1007\/3-540-48452-3_4"},{"key":"22_CR12","unstructured":"C. L. Monma and J. B. Sidney. A general algorithm for optimal job sequencing with series-parallel precedence constraints. Technical Report 347, School of Operations Research, Cornell University, 1977."},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"David Sankoff and Joseph H. Nadeau. Conserved synteny as a measure of genomic distance. Discrete Applied Mathematics (special issue on computational biology), 71(1\u20133):247\u2013257, December 1996.","DOI":"10.1016\/S0166-218X(96)00067-4"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45123-4_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T12:49:39Z","timestamp":1630068579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45123-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676331","9783540451235"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-45123-4_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}