Multiple filtration and approximate pattern matching

DOI10.1007/BF01188584MaRDI QIDQ1902470zbMATH OpenFDO

Authors Pavel Pevzner, Michael S. Waterman

Publication date 12 February 1996

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01188584

zbMATH Keywords

algorithmapproximate pattern matchingapproximate string matching with \(k\) mismatches problemdot-matrix constructionsmolecular biologymultiple filtrationmultiple hashingoptimal oligonucleotide probe selectionsequence comparisontwo-stage process

Mathematics Subject Classification ID

Combinatorics on words (68R15) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40)

Recommendations

• On using q-gram locations in approximate string matching
• New and faster filters for multiple approximate string matching
• scientific article; zbMATH DE number 1342989
• A new filtration method and a hybrid strategy for approximate string matching
• Multiple approximate string matching

Cites work

• A fast string searching algorithm
• A measure of the similarity of sets of sequences not requiring sequence alignment.
• A new distance metric on strings computable in linear time
• A sublinear algorithm for approximate keyword searching
• An algorithm for approximate membership checking with application to password security
• An approximate string-matching algorithm
• An Improved Algorithm For Approximate String Matching
• Approximate string-matching with q-grams and maximal matches
• Data structures and algorithms for approximate string matching
• Deterministic Sampling–A New Technique for Fast Pattern Matching
• Efficient randomized pattern-matching algorithms
• Efficient string matching with k mismatches
• Fast and practical approximate string matching
• Fast parallel and serial approximate string matching
• Fast Pattern Matching in Strings
• Finding approximate patterns in strings
• scientific article; zbMATH DE number 3126031 (Why is no real title available?)
• scientific article; zbMATH DE number 140453 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Parallel string matching with k mismatches
• RECOGNITION OF AN APPROXIMATE OCCURRENCE OF WORDS ON A TURING MACHINE IN REAL TIME
• Simple and efficient string matching with k mismatches
• Time-space-optimal string matching

Cited in

(13)

• Lossless filter for multiple repetitions with Hamming distance
• A simple, fast, filter-based algorithm for circular sequence comparison
• Sensitivity analysis and efficient method for identifying optimal spaced seeds
• A taxonomy of sublinear multiple keyword pattern matching algorithms
• Approximate search of short patterns with high error rates using the 01^ 0 lossless seeds
• DNA-seq error correction based on substring indices
• INDEXING GAPPED-FACTORS USING A TREE
• scientific article; zbMATH DE number 1786459 (Why is no real title available?)
• On-Line Approximate String Searching Algorithms: Survey and Experimental Results
• Faster filters for approximate string matching
• Multiple Matching and Runs by the Symbolic Method
• Multiple matching of parameterized patterns
• Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design

This page was built for publication: Multiple filtration and approximate pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1902470)