 |
Journal articles
Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform
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, we present a new method based on the Burrows--Wheeler transform 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 complexity time is O(qm2). Experimental results show that our method performs well in practice.
https://hal-normandie-univ.archives-ouvertes.fr/hal-02113307
Contributor : Thierry Lecroq Connect in order to contact the contributor
Submitted on : Sunday, April 28, 2019 - 3:46:40 PM
Last modification on : Wednesday, November 3, 2021 - 6:27:41 AM
Contributor : Thierry Lecroq Connect in order to contact the contributor
Submitted on : Sunday, April 28, 2019 - 3:46:40 PM
Last modification on : Wednesday, November 3, 2021 - 6:27:41 AM
Links full text
