## 2 Materials and Methods
### A Las Vegas Algorithm for \(K\) Mismatches
#### 2.4.3 A Las Vegas Algorithm
Therefore, the run time of the entire algorithm is \(\widetilde{O}(nk\log^{2}m\;+\;n\log^{2}m\log n\)\(+n\log m\log n\log\log n)\) if Algorithm 6 is used in Step 1 or \(\widetilde{O}(nk\log m\log n\;+\;nk\log^{2}m\;+\;n\log^{2}m\log n)\) if Algorithm 5 is used in Step 1. ## 3 Results

The above algorithms are based on symbol comparison, arithmetic operations or a combination of both. Therefore, it is interesting to see how these algorithms compare in practice. In this section, we compare deterministic algorithms for pattern matching. Some of these algorithms solve the pattern matching with mismatches problem, and others solve the \(k\) mismatches problem. For the sake of comparison, we treated all of them as algorithms for the \(k\) mismatches problem, which is a special case of the pattern matching with mismatches problem. We implemented the following algorithms: the naive \(O(nm)\) time algorithm, [PERSON]'s algorithm Abrahamson (1966), subset \(k\) mismatches (Section 2.2.2) and knapsack \(k\) mismatches (Section 2.2.3). For subset \(k\) mismatches, we simulate the suffix tree and LCA extensions by a suffix array with an LCP (longest common prefix; [PERSON] and others (2015)) table and data structures to perform RMQ queries (range minimum queries; [PERSON] and others (2015)) on it. This adds a \(O(\log n)\) factor to preprocessing. For searching in the suffix array, we use a simple forward traversal with a cost of \(O(\log n)\) per character. The traversal uses binary search to find the interval of suffixes that start with the first character of the pattern. Then, another binary search is performed to find the suffixes that start with the first two characters of the pattern, and so on. However, more efficient implementations are possible (e.g., [PERSON] and others (2015)). For subset \(k\) mismatches, we also tried a simple \(O(m^{2})\) time pre-processing using dynamic programming to precompute LCPs and hashing to quickly determine whether a portion of the text is present in the pattern. This method takes more preprocessing time, but it does not have the \(O(\log n)\) factor when searching. Knapsack \(k\) mismatches uses subset \(k\) mismatches as a subroutine, so we have two versions of it, as well. We tested the algorithms on protein, DNA and English inputs generated randomly. We randomly selected a substring of length \(m\) from the text and used it as the pattern. The algorithms were tested on an Intel Core i7 machine with 8 GB of RAM, Linux Mint 17.1 Operating System and gcc 4.8.2. All convolutions were performed using the fftwKrawczyk and others (2015) library Version 3.3.3. We used the suffix array algorithm RadixSAof RadixSAof (2015). Figure 1 shows run times for varying the length of the text \(n\). All algorithms scale linearly with the length of the text. Figure 2 shows run times for varying the length of the pattern \(m\). [PERSON]'s algorithm is expensive, because, for alphabet sizes smaller than \(\sqrt{m/\log m}\), it computes one convolution for every character in the alphabet. The convolutions proved to be expensive in practice, so [PERSON]'s algorithm was competitive only for DNA data, where the alphabet is small. Figure 3 shows runtimes for varying the maximum number of mismatches \(k\) allowed. The naive algorithm and [PERSON]'s algorithm do not depend on \(k\); therefore, their runtime is constant. Subset \(k\) mismatch, with its \(O(nk)\) runtime, is competitive for relatively small \(k\). Knapsack \(k\) mismatch, on the other hand, scaled very well with \(k\). Figure 4 shows runtimes for varying the alphabet from four (DNA) to 20 (protein) to 26 (English). As expected, [PERSON]'s algorithm is the most sensitive to the alphabet size. Overall, the naive algorithm performed well in practice, most likely due to its simplicity and cache locality. [PERSON]'s algorithm was competitive only for small alphabet size or for large \(k\). Subset \(k\) mismatches performed well for relatively small \(k\).