BWT Arrays and Mismatching Trees: A New Way for String Matching with k Mismatches

In this paper, we discuss an efficient and effective index mechanism to do the string matching with k mismatches, by which we will find all the substrings in a target string s having at most k positions different from a pattern string r. The main idea is to transform s to a BWT-array as index, denoted as BWT(s), and search r against it. During the process, the precomputed mismatch information of r will be utilized to speed up the BWT(s)'s navigation. In this way, the time complexity can be reduced to O(kn' + n + mlogm), where m = |r|, n = |s|, and n' is the number of leaf nodes of a tree structure, called a mismatching tree, produced during a search of BWT(s). Extensive experiments have been conducted, which show that our method for this problem is promising