Multiple filtration and approximate pattern matching

DOI10.1007/BF01188584zbMath0831.92015MaRDI QIDQ1902470

Pavel A. Pevzner, Michael S. Waterman

Publication date: 12 February 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

algorithmmolecular biologysequence comparisonapproximate pattern matchingtwo-stage processapproximate string matching with \(k\) mismatches problemdot-matrix constructionsmultiple filtrationmultiple hashingoptimal oligonucleotide probe selection

Mathematics Subject Classification ID

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

Related Items

Sensitivity analysis and efficient method for identifying optimal spaced seeds ⋮ On-Line Approximate String Searching Algorithms: Survey and Experimental Results ⋮ INDEXING GAPPED-FACTORS USING A TREE ⋮ DNA-Seq Error Correction Based on Substring Indices ⋮ Seed optimization for i.i.d. similarities is no easier than optimal Golomb ruler design

Cites Work

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