Multiple filtration and approximate pattern matching
From MaRDI portal
Publication:1902470
DOI10.1007/BF01188584zbMath0831.92015MaRDI QIDQ1902470
Pavel A. Pevzner, Michael S. Waterman
Publication date: 12 February 1996
Published in: Algorithmica (Search for Journal in Brave)
algorithmmolecular biologysequence comparisonapproximate pattern matchingtwo-stage processapproximate string matching with \(k\) mismatches problemdot-matrix constructionsmultiple filtrationmultiple hashingoptimal oligonucleotide probe selection
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
