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

摘要

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 0 (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. (C) 2019 The Authors. Published by Elsevier B.V.