Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform

J.W. Daykin , Richard Groult (1) , Y. Guesnet (2) , T. Lecroq (2) , A. Lefebvre (2) , M. Leonard (2) , L. Mouchard (2) , É. Prieur-Gaston (2) , B. Watson

1 MIS - Modélisation, Information et Systèmes - UR UPJV 4290
2 TIBS - LITIS - Equipe Traitement de l'information en Biologie Santé

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.

Mots clés: Algorithm; Burrows–Wheeler transform; Degenerate; Pattern matching; String

Domaines: Algorithme et structure de données [cs.DS]

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