IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences

摘要

Let S = s(1)s(2) ... s(n) be a string, with symbols from an alphabet. S is said to be degenerate if for some positions, say i, s(i) can contain a subset of symbols from the symbol alphabet, rather than just one symbol. Given a text string T and a pattern P, both with symbols from an alphabet Sigma, the degenerate string matching problem, is to find positions in T where P occured, such that T, P, or both are allowed to be degenerate. Though some algorithms have been proposed, their huge computational cost pose a significant challenge to their practical utilization. In this work, we propose IDPM, an improved degenerate pattern matching algorithm based on an extension of the Boyer-Moore algorithm. At the preprocessing phase, the algorithm defines an alphabet-independent compatibility rule, and computes the shift arrays using respective variants of the bad character and good suffix heuristics. At the search phase, IDPM improves the matching speed by using the compatibility rule. On average, the proposed IDPM algorithm has a linear time complexity with respect to the text size, and to the overall size of the pattern. IDPM demonstrates significance performance improvement over state-of-the-art approaches. It can be used in fast practical degenerate pattern matching with large data sizes, with important applications in flexible and scalable searching of huge biological sequences.