## 2 Materials and Methods
### A Las Vegas Algorithm for \(K\) Mismatches
#### 2.4.3 A Las Vegas Algorithm
In most cases, the suffix array version was slower than the hashing-based one with \(O(m^{2})\) time pre-processing because of the added \(O(\log n)\) factor when searching in the suffix array. It would be interesting to investigate how the algorithms compare with a more efficient implementation of the suffix array. Knapsack \(k\) mismatches was the fastest among the algorithms compared, because in most cases, the knapsack could be filled with less than the given \"budget\", and thus, the algorithm did not have to perform any convolution operations. Figure 1: Run times for pattern matching on DNA, protein and English alphabet data, when the length of the text (\(n\)) varies. The length of the pattern is \(m=1000\). The maximum number of mismatches allowed is \(k=100\). Our algorithms are subset k mismatch with hashing-based preprocessing (Section 2.2.2), subset k mismatch with suffix array preprocessing (Section 2.2.2), knapsack k mismatch with hashing-based preprocessing (Section 2.2.3) and knapsack k mismatch with suffix array preprocessing (Section 2.2.3). Figure 2: Run times for pattern matching on DNA, protein and English alphabet data, when the length of the pattern (\(m\)) varies. The length of the text is \(n=10\) millions. The maximum number of mismatches allowed is \(k=10\%\) of the pattern length. Our algorithms are subset k mismatch with hashing-based preprocessing (Section 2.2.2), subset k mismatch with suffix array preprocessing (Section 2.2.2), knapsack k mismatch with hashing-based preprocessing (Section 2.2.3) and knapsack k mismatch with suffix array preprocessing (Section 2.2.3). Figure 3: Run times for pattern matching on DNA, protein and English alphabet data, when the maximum number of mismatches allowed (\(k\)) varies. The length of the text is \(n=10\) millions. The length of the pattern is \(m=2000\). Our algorithms are subset k mismatch with hashing-based preprocessing (Section 2.2.2), subset k mismatch with suffix array preprocessing (Section 2.2.2), knapsack k mismatch with hashing-based preprocessing (Section 2.2.3) and knapsack k mismatch with suffix array preprocessing (Section 2.2.3). ## 4 Conclusions

We have introduced several deterministic and randomized, exact and approximate algorithms for pattern matching with mismatches and the \(k\) mismatches problems, with or without wild cards. These algorithms improve the run time, simplify or extend previous algorithms wild cards. We have also implemented the deterministic algorithms. An empirical comparison of these algorithms showed that the algorithms based on character comparison outperform those based on convolutions. ## Acknowledgments

This work has been supported in part by the following grants: NSF 1447711, NSF 0829916 and NIH R01 LM010101. ## Author Contributions

[PERSON] designed the randomized and approximate algorithms. [PERSON] designed and implemented the deterministic algorithms and carried out the empirical experiments. [PERSON] and [PERSON] drafted and approved the manuscript. ## Conflicts of Interest

The authors declare no conflict of interest. Figure 4: Run times for pattern matching when the size of the alphabet varies from four (DNA) to 20 (protein) to 26 (English). The length of the text is \(n=10\) millions. The length of the pattern is \(m=200\) in the first graph and \(m=1000\) in the second. The maximum number of mismatches allowed is \(k=20\) in the first graph and \(k=100\) in the second. Our algorithms are subset k mismatch with hashing-based preprocessing (Section 2.2.2), subset k mismatch with suffix array preprocessing (Section 2.2.2), knapsack k mismatch with hashing-based preprocessing (Section 2.2.3) and knapsack k mismatch with suffix array preprocessing (Section 2.2.3). ## References

* (1) [PERSON]; [PERSON]; [PERSON] Fast Pattern Matching in Strings. _SIAM J. Comput._**1977**, \(6\), 323-350. * (2) [PERSON]; [PERSON] Efficient string matching: An aid to bibliographic search. _Commun. ACM_**1975**, _18_, 333-340. * (3) [PERSON]; [PERSON] String-Matching and Other Products.