Name
Abstract | ||
|---|---|---|
We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the alignments for which the pattern matches the text with Hamming distance at most k and also returns the location and identity of each mismatch. The algorithm we present is deterministic and runs in Õ(kn) time, matching the best known randomised time complexity to within logarithmic factors. The solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.
|
Year | DOI | Venue |
|---|---|---|
2009 | 10.5555/1496770.1496855 | SODA: Symposium on Discrete Algorithms |
Keywords | Field | DocType |
approximate pattern,hamming distance,algebraic coding theory,promiscuously matching wildcard symbol,randomised time complexity,length n,optional wildcard symbol,bound k,pattern p,efficient pattern matching,length m,pattern matching,time complexity,coding theory | Discrete mathematics,Combinatorics,Wildcard,Computer science,Algorithm,Coding theory,Hamming distance,Approximate string matching,Logarithm,3-dimensional matching,Time complexity,Pattern matching | Conference |
ISBN | Citations | PageRank |
978-0-89871-698-6 | 19 | 0.75 |
References | Authors | |
17 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Klim Efremenko | 2 | 135 | 15.31 |
| ely porat | 3 | 1007 | 79.16 |
| Amir Rothschild | 4 | 49 | 3.46 |