{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:54:05Z","timestamp":1742396045018},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438625"},{"type":"electronic","value":"9783540454526"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45452-7_19","type":"book-chapter","created":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T21:55:29Z","timestamp":1179266129000},"page":"225-234","source":"Crossref","is-referenced-by-count":20,"title":["One-Gapped q-Gram Filters for Levenshtein Distance"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Burkhardt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S. F. Altschul","year":"1990","unstructured":"S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 215:403\u2013410, 1990.","journal-title":"Journal of Molecular Biology"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"S. Burkhardt, A. Crauser, P. Ferragina, H.-P. Lenhof, E. Rivals, and M. Vingron. q-gram based database searching using a suffix array (QUASAR). In Proc. 3rd Annual International Conference on Computational Molecular Biology (RECOMB), pages 77\u201383. ACM Press, 1999.","DOI":"10.1145\/299432.299460"},{"key":"19_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/3-540-48194-X_6","volume-title":"Proc. 12th Annual Symposium on Combinatorial Pattern Matching","author":"S. Burkhardt","year":"2001","unstructured":"S. Burkhardt and J. K\u00e4rkk\u00e4inen. Better filtering with gapped q-grams. In Proc. 12th Annual Symposium on Combinatorial Pattern Matching, volume 2089 of LNCS, pages 73\u201385. Springer, 2001."},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"A. Califano and I. Rigoutsos. FLASH: A fast look-up algorithm for string homology. In Proc. 1st International Conference on Intelligent Systems for Molecular Biology, pages 56\u201364. AAAI Press, 1993.","DOI":"10.1109\/CVPR.1993.341106"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"19_CR6","unstructured":"N. Holsti and E. Sutinen. Approximate string matching using q-gram places. In Proc. 7th Finnish Symposium on Computer Science, pages 23\u201332, 1994."},{"key":"19_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-54345-7_67","volume-title":"Proc. 16th Symposium on Mathematical Foundations of Computer Science","author":"P. Jokinen","year":"1991","unstructured":"P. Jokinen and E. Ukkonen. Two algorithms for approximate string matching in static texts. In Proc. 16th Symposium on Mathematical Foundations of Computer Science, volume 520 of LNCS, pages 240\u2013248. Springer, 1991."},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"J. K\u00e4rkk\u00e4inen. Computing the threshold for q-gram filters. In Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT), July 2002. To appear.","DOI":"10.1007\/3-540-45471-3_36"},{"key":"19_CR9","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1093\/bioinformatics\/14.5.430","volume":"14","author":"A. Krause","year":"1998","unstructured":"A. Krause and M. Vingron. A set-theoretic approach to database searching and clustering. Bioinformatics, 14:430\u2013438, 1998.","journal-title":"Bioinformatics"},{"key":"19_CR10","unstructured":"O. Lehtinen, E. Sutinen, and J. Tarhio. Experiments on block indexing. In Proc. 3rd South American Workshop on String Processing (WSP), pages 183\u2013193. Carleton University Press, 1996."},{"key":"19_CR11","unstructured":"G. Navarro. Approximate Text Searching. PhD thesis, Dept. of Computer Science, University of Chile, 1998."},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"G. Navarro. A guided tour to approximate string matching. ACM Computing Surveys, 33(1):31\u201388, 2001.","journal-title":"ACM Computing Surveys"},{"issue":"1\/2","key":"19_CR13","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01188584","volume":"13","author":"P. A. Pevzner","year":"1995","unstructured":"P. A. Pevzner and M. S. Waterman. Multiple filtration and approximate pattern matching. Algorithmica, 13(1\/2):135\u2013154, 1995.","journal-title":"Algorithmica"},{"issue":"1","key":"19_CR14","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"E. Ukkonen","year":"1992","unstructured":"E. Ukkonen. Approximate string matching with q-grams and maximal matches. Theor. Comput. Sci, 92(1):191\u2013212, 1992.","journal-title":"Theor. Comput. Sci"},{"key":"19_CR15","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1101\/gr.7.5.401","volume":"7","author":"J. Weber","year":"1997","unstructured":"J. Weber and H. Myers. Human whole genome shotgun sequencing. Genome Research, 7:401\u2013409, 1997.","journal-title":"Genome Research"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45452-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T20:52:43Z","timestamp":1556398363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45452-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438625","9783540454526"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45452-7_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}