Name
Abstract | ||
|---|---|---|
A degenerate or indeterminate string on an alphabet Σ is a sequence of non-empty subsets of Σ. Given a degenerate string t of length n and its Burrows–Wheeler transform we present a new method for searching for a degenerate pattern of length m in t running in O(mn) time on a constant size alphabet Σ. Furthermore, it is a hybrid pattern matching technique that works on both regular and degenerate strings. A degenerate string is said to be conservative if its number of non-solid letters is upper-bounded by a fixed positive constant q; in this case we show that the search time complexity is O(qm2) for counting the number of occurrences and O(qm2+occ) for reporting the found occurrences where occ is the number of occurrences of the pattern in t. Experimental results show that our method performs well in practice. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.ipl.2019.03.003 | Information Processing Letters |
Keywords | Field | DocType |
Algorithms,Burrows–Wheeler transform,Degenerate,Pattern matching,String | Degenerate energy levels,Discrete mathematics,Combinatorics,Burrows–Wheeler transform,Indeterminate,Time complexity,Pattern matching,Mathematics,Alphabet | Journal |
Volume | ISSN | Citations |
147 | 0020-0190 | 0 |
PageRank | References | Authors |
0.34 | 5 | 9 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jacqueline W. Daykin | 1 | 79 | 14.68 |
| Richard Groult | 2 | 34 | 6.77 |
| Yannick Guesnet | 3 | 0 | 0.68 |
| Thierry Lecroq | 4 | 662 | 58.52 |
| Arnaud Lefebvre | 5 | 164 | 18.47 |
| Martine Léonard | 6 | 37 | 5.66 |
| Laurent Mouchard | 7 | 251 | 25.07 |
| Elise Prieur-Gaston | 8 | 37 | 6.02 |
| Bruce W. Watson | 9 | 338 | 53.24 |