Skip to Main content Skip to Navigation
Journal articles

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

J.W. Daykin R. 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 & Systèmes
2 TIBS - LITIS - Equipe Traitement de l'information en Biologie Santé
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
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.
Keywords : Algorithm Burrows–Wheeler transform Degenerate Pattern matching String
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

openaccess

Identifiers

Collections

COMUE-NORMANDIE | LITIS | INSA-ROUEN | UNIROUEN | UNILEHAVRE | INSA-GROUPE

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

73