{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:47:48Z","timestamp":1766065668524},"publisher-location":"Berlin\/Heidelberg","reference-count":28,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354056764X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0029806","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T04:36:08Z","timestamp":1133411768000},"page":"197-214","source":"Crossref","is-referenced-by-count":6,"title":["A fast filtration algorithm for the substring matching problem"],"prefix":"10.1007","author":[{"given":"Pavel A.","family":"Pevzner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael S.","family":"Waterman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Baeza-Yates R.A., Gonnet G.H. A new approach to text searching. in Proc. of the 12th Annual ACM-SIGIR conference on Information Retrieval, Cambridge, MA, (1989), 168\u2013175","DOI":"10.1145\/75334.75352"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science, 644","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-56024-6_15","volume-title":"Combinatorial Pattern Matching 92","author":"R.A. Baeza-Yates","year":"1992","unstructured":"Baeza-Yates R.A., Perleberg C.H. Fast and practical approximate string matching. In A. Apostolico, M. Crochermore, Z. Galil, U. Manber (eds.) Combinatorial Pattern Matching 92, Tucson, Arizona, Lecture Notes in Computer Science, 644, Springer-Verlag, (1992), 185\u2013192"},{"key":"15_CR3","doi-asserted-by":"crossref","first-page":"5155","DOI":"10.1073\/pnas.83.14.5155","volume":"83","author":"B.E. Blaisdell","year":"1986","unstructured":"Blaisdell B.E. A measure of the similarity of sets of sequences not requiring sequence alignment. Proc. Nat. Acad. Sci. U.S.A., 83, (1986), 5155\u20135159.","journal-title":"Proc. Nat. Acad. Sci. U.S.A."},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Chang W.I., Lawler E.L. Approximate string matching in sublinear expected time. Proceedings of 31st IEEE FOCS, (1990), 116\u2013124","DOI":"10.1109\/FSCS.1990.89530"},{"key":"15_CR5","first-page":"303","volume":"3","author":"A. Danckaert","year":"1987","unstructured":"Danckaert A., Mugnier C., Dessen P., and Cohen-Solal M. A computer program for the design of optimal synthetic oligonucleotides probes for protein coding genes. CABIOS, 3, (1987) 303\u2013307.","journal-title":"CABIOS"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1093\/nar\/10.1.197","volume":"10","author":"J.P. Dumas","year":"1982","unstructured":"Dumas, J.P., Ninio, J. Efficient algorithms for folding and comparing nucleic acid sequences. Nucl. Acids Res., 10, (1982), 197\u2013206.","journal-title":"Nucl. Acids Res."},{"key":"15_CR7","volume-title":"An introduction to probability theory and its applications","author":"W. Feller","year":"1970","unstructured":"Feller W. An introduction to probability theory and its applications. John Wiley & Sons, New York, (1970)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Galil, Z. and Giancarlo, R. Improved string matching with k mismatches. SIGACT News, April, (1986), 52\u201354.","DOI":"10.1145\/8307.8309"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(89)90188-9","volume":"33","author":"R. Grossi","year":"1990","unstructured":"Grossi R., Luccio F. Simple and efficient string matching with k mismatches. Information Processing Letters, 33, (1990), 113\u2013120","journal-title":"Information Processing Letters"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1145\/362919.362934","volume":"14","author":"M.C. Harrison","year":"1971","unstructured":"Harrison M.C. Implementation of the substring test by hashing. C.ACM, 14, (1971), 777\u2013779","journal-title":"C.ACM"},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1002\/spe.4380211105","volume":"21","author":"A. Hume","year":"1991","unstructured":"Hume A., Sunday D. Fast string searching. Software \u2014 Practice and Experience, 21, (1991), 1221\u20131248","journal-title":"Software \u2014 Practice and Experience"},{"key":"15_CR12","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R.M. Karp","year":"1987","unstructured":"Karp R.M., Rabin M.O. Efficient randomized pattern-matching algorithms. IBM J. Res. Develop., 31, (1987), 249\u2013260","journal-title":"IBM J. Res. Develop."},{"key":"15_CR13","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0304-3975(92)90138-6","volume":"92","author":"J.Y. Kim","year":"1992","unstructured":"Kim J.Y. Shawe-Taylor J. An approximate string matching algorithm. Theoretical Computer Science, 92, (1992), 107\u2013117","journal-title":"Theoretical Computer Science"},{"key":"15_CR14","volume-title":"The art of computer programming, vol.III: sorting and searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth D.E. The art of computer programming, vol.III: sorting and searching. Addison-Wesley, Reading, Mass., (1973)"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau G.M., Vishkin U. Efficient string matching with k mismatches, Theoret. Computer Sci., 43, (1986), 239\u2013249","journal-title":"Theoret. Computer Sci."},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau G.M., Vishkin U. Fast parallel and serial approximate string matching. J. of Algorithms, 10, (1989), 157\u2013169","journal-title":"J. of Algorithms"},{"key":"15_CR17","first-page":"19","volume":"4","author":"G.M. Landau","year":"1988","unstructured":"Landau, G.M., Vishkin, U., and Nussinov, R. Locating alignments with k differences for nucleotide and amino acid sequences. CABIOS, 4, (1988), 19\u201324.","journal-title":"CABIOS"},{"key":"15_CR18","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1126\/science.2983426","volume":"227","author":"D.J. Lipman","year":"1985","unstructured":"Lipman, D.J., Pearson, W.R. Rapid and sensitive protein similarity searches. Science, 227, (1985), 1435\u20131441.","journal-title":"Science"},{"key":"15_CR19","doi-asserted-by":"crossref","first-page":"7665","DOI":"10.1073\/pnas.78.12.7665","volume":"78","author":"J. V. Maizel Jr.","year":"1981","unstructured":"Maizel, J. V.,Jr. and Lenk, R.P. Enhanced graphic matrix analysis of nucleic acid and protein sequences. Proc. Nat. Acad. Sci. USA, 78, (1981), 7665\u20137669.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1093\/nar\/14.1.501","volume":"14","author":"E.W. Myers","year":"1986","unstructured":"Myers E.W., Mount D. (1986) Computer program for the IBM personal computer that searches for approximate matches of short oligonucleotide sequences in long target DNA sequences. Nucleic Acids Research, 14, 501\u2013508","journal-title":"Nucleic Acids Research"},{"key":"15_CR21","volume-title":"Technical Report TR-90-25, Department of Computer Science","author":"E.W. Myers","year":"1990","unstructured":"Myers E.W. (1990) A sublinear algorithm for approximate keyword searching. Technical Report TR-90-25, Department of Computer Science, The University of Arizona, Tucson, Arizona. (to appear in Algorithmica)"},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1002\/spe.4380180407","volume":"18","author":"O. Owolabi","year":"1988","unstructured":"Owolabi O., McGregor D.R. Fast approximate string matching. Software-Practice and Experience, 18, (1988), 387\u2013393","journal-title":"Software-Practice and Experience"},{"key":"15_CR23","first-page":"348","volume-title":"Boyer-Moore approach to approximate string matching Lecture Notes in Computer Science, 447","author":"J. Tarhio","year":"1990","unstructured":"Tarhio J., Ukkonen E. Boyer-Moore approach to approximate string matching Lecture Notes in Computer Science, 447, Springer, Berlin, (1990), 348\u2013359"},{"key":"15_CR24","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0196-6774(85)90023-9","volume":"6","author":"U. Ukkonen","year":"1985","unstructured":"Ukkonen U. Finding approximate patterns in strings. Journal of Algorithms, 6, (1985), 132\u2013137","journal-title":"Journal of Algorithms"},{"key":"15_CR25","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(92)90143-4","volume":"92","author":"U. Ukkonen","year":"1992","unstructured":"Ukkonen U. Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science, 92, (1992), 191\u2013211","journal-title":"Theoretical Computer Science"},{"key":"15_CR26","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1073\/pnas.80.3.726","volume":"80","author":"W. J. Wilbur","year":"1983","unstructured":"Wilbur W. J., Lipman D.J., Rapid similarity searches of nucleic acid and protein data banks. Proc. Nat. Acad. Sci. USA, 80, (1983), 726\u2013730.","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"15_CR27","unstructured":"Wu S., Manber U. Agrep \u2014 A Fast Approximate Pattern-Matching Tool. Usenix Winter 1992 Technical Conference, San Francisco (January 1992), (1992), 153\u2013162."},{"issue":"No.10","key":"15_CR28","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S. Wu","year":"1992","unstructured":"Wu S., Manber U. Fast Text Searching Allowing Errors. Comm. of the ACM, 35, No.10 (1992),83\u201390","journal-title":"Comm. of the ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0029806","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T04:33:53Z","timestamp":1586579633000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0029806"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354056764X"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/bfb0029806","relation":{},"subject":[]}}