@article{265, keywords = {Algorithms, Burrows–Wheeler transform, Degenerate, Pattern matching, String}, author = {J.W. Daykin and R. Groult and Y. Guesnet and T. Lecroq and A. Lefebvre and M. Leonard and L. Mouchard and E. Prieur-Gaston and Bruce Watson}, title = {Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform}, abstract = {A degenerate or indeterminate string on an alphabet SIGMA is a sequence of non-empty subsets of SIGMA . 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 SIGMA. 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 ( qm^2 ) for counting the number of occurrences and O ( qm^2 + 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 = {2019}, journal = {Information Processing Letters}, volume = {147}, chapter = {82 - 87}, publisher = {Elsevier}, doi = {https://doi.org/10.1016/j.ipl.2019.03.003}, }