Skip to Main content Skip to Navigation
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.
Document type :
Journal articles
Complete list of metadatas

https://hal-normandie-univ.archives-ouvertes.fr/hal-02113307
Contributor : Thierry Lecroq <>
Submitted on : Sunday, April 28, 2019 - 3:46:40 PM
Last modification on : Tuesday, November 19, 2019 - 9:00:02 AM

Links full text

Identifiers

Citation

J.W. Daykin, R. Groult, Y. Guesnet, T. Lecroq, A. Lefebvre, et al.. Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform. Information Processing Letters, Elsevier, 2019, 147, pp.82-87. ⟨10.1016/j.ipl.2019.03.003⟩. ⟨hal-02113307⟩

Share

Metrics

Record views

73