{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T06:12:20Z","timestamp":1744697540345},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540432838"},{"type":"electronic","value":"9783540458418"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_21","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:11:17Z","timestamp":1186891877000},"page":"262-273","source":"Crossref","is-referenced-by-count":16,"title":["On the Parameterized Intractability of Closest Substring and Related Problems"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Gramm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"M. Blanchette. Algorithms for phylogenetic footprinting. In Proc. of 5th ACM RECOMB, pages 49\u201358, 2001, ACM Press.","DOI":"10.1145\/369133.369170"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H. L. Bodlaender","year":"1995","unstructured":"H. L. Bodlaender, R. G. Downey, M. R. Fellows, and H. T. Wareham. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science, 147:31\u201354, 1995.","journal-title":"Theoretical Computer Science"},{"key":"21_CR3","first-page":"49","volume":"11","author":"H. L. Bodlaender","year":"1995","unstructured":"H. L. Bodlaender, R. G. Downey, M. R. Fellows, M. T. Hallett, and H. T. Wareham. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences, 11: 49\u201357, 1995.","journal-title":"Computer Applications in the Biosciences"},{"issue":"4","key":"21_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"M. Cesati and L. Trevisan. On the efficiency of polynomial time approximation schemes. Information Processing Letters, 64(4):165\u2013171, 1997.","journal-title":"Information Processing Letters"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. ParameterizedComplexity. Springer. 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"21_CR6","unstructured":"P. A. Evans and H. T. Wareham. Practical non-polynomial time algorithms for designing universal DNAoligon ucleotides: a systematic approach. Manuscript, April 2001."},{"key":"21_CR7","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02679443","volume":"30","author":"M. Frances","year":"1997","unstructured":"M. Frances and A. Litman. On covering problems of codes. Theory of Computing Systems, 30:113\u2013119, 1997.","journal-title":"Theory of Computing Systems"},{"key":"21_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Exact solutions for Closest String and related problems","author":"J. Gramm","year":"2001","unstructured":"J. Gramm, R. Niedermeier, and P. Rossmanith. Exact solutions for Closest String and related problems. To appear in Proc. of 12th ISAAC (Christchurch, New Zealand), LNCS, December 2001. Springer."},{"key":"21_CR9","unstructured":"M. T. Hallett. An IntegratedComplexity Analysis of Problems from Computational Biology. PhD Thesis, University of Victoria, Canada, 1996."},{"key":"21_CR10","unstructured":"J. K. Lanctot, M. Li, B. Ma, S. Wang, and L. Zhang. Distinguishing string selection problems. In Proc. of 10th ACM-SIAM SODA, pages 633\u2013642, 1999, ACM Press. To appear in Information andComputation."},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"M. Li, B. Ma, and L. Wang. Finding similar regions in many strings. In Proc. of 31st ACM STOC, pages 473\u2013482, 1999. ACM Press. To appear in Journal of Computer andSystem Sciences.","DOI":"10.1145\/301250.301376"},{"key":"21_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/3-540-45123-4_10","volume-title":"A polynomial time approximation scheme for the closest substring problem","author":"B. Ma","year":"2000","unstructured":"B. Ma. A polynomial time approximation scheme for the closest substring problem. In Proc. of 11th CPM, number 1848 in LNCS, pages 99\u2013107, 2000. Springer."},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"P. A. Pevzner. Computational Molecular Biology \u2014 An Algorithmic Approach. MITPress. 2000.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"21_CR14","unstructured":"P. A. Pevzner and S.-H. Sze. Combinatorial approaches to finding subtle signals in DNA sequences. In Proc. of 8th ISMB, pages 269\u2013278, 2000. AAAI Press."},{"key":"21_CR15","series-title":"Lect Notes Comput Sci","first-page":"111","volume-title":"Spelling approximate repeated or common motifs using a sufix tree","author":"M.-F. Sagot","year":"1998","unstructured":"M.-F. Sagot. Spelling approximate repeated or common motifs using a sufix tree. In Proc. of 3rdLA TIN, number 1380 in LNCS, pages 111\u2013127, 1998. Springer."},{"key":"21_CR16","unstructured":"D. Sanko. and J. Kruskal (eds.). Time Warps, String Edits, and Macromolecules. Addison-Wesley. 1983. Reprinted in 1999 by CSLI Publications."}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T20:00:34Z","timestamp":1556740834000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}