## 2 Materials and Methods
### A Las Vegas Algorithm for \(K\) Mismatches
#### 2.4.3 A Las Vegas Algorithm  
In this section, we present a Las Vegas algorithm for the \(k\) mismatches problem when there are wild cards in the text and/or the pattern. This algorithm runs in time \(\widetilde{O}(nk\log^{2}m+n\log^{2}m\log n+n\log m\log n\log\log n)\). This algorithm is based on the algorithm of [17]. When the algorithm terminates, for each \(i\) (\(1\leq i\leq(n-m+1)\)), either we would have identified all of the \(q_{i}\) mismatches between \(T_{i}\) and \(P\) or we would have identified more than \(k\) mismatches between \(T_{i}\) and \(P\). Algorithm 5 will be used for every \(i\) for which \(q_{i}\leq 2k\). For every \(i\) for which \(q_{i}>2k\), we use the following strategy. Let \(2^{\ell}k<q_{i}\leq 2^{\ell+1}k\) (where \(1\leq\ell\leq\log\left(\left\lfloor\frac{m}{2k}\right\rfloor\right)\)). Let \(w=\log\left(\left\lfloor\frac{m}{2k}\right\rfloor\right)\). There will be \(w\) phases in the algorithm, and in each phase, we perform \(O(k)\) sampling steps. Each sampling step in phase \(\ell\) involves choosing \(\frac{m}{2^{\ell+1}k}\) positions of the pattern uniformly at random (for \(1\leq\ell\leq w\)). As we show below, if for any \(i\), \(q_{i}\) is in the interval \([2^{\ell},2^{\ell+1}]\), then at least \(k\) mismatches between \(T_{i}\) and \(P\) will be found in phase \(\ell\) with high probability. The pseudocode for the algorithm is given in Algorithm 7. ```
1:\(\widetilde{O}(nk\log^{2}m+n\log^{2}m\log n+n\log m\log n\log\log n)\)
2:\(\widetilde{O}(nk\log m\log n+nk\log^{2}m+n\log^{2}m\log n)\)
3:\(\widetilde{O}(nk\log m\log n+nk\log^{2}m+n\log^{2}m\log n)\)
4:\(\widetilde{O}(nk\log m\log n+nk\log^{2}m+n\log^{2}m\log n)\)
5:\(\widetilde{O}(nk\log m\log n+nk\log^{2}m+n\log^{2}m\log n)\)
6:\(\widetilde{O}(nk\log m\log n+nk\log^{2}m+n\log^{2



**Proof. ** As shown in [17], the run time of Algorithm 5 is \(O(nk\log m\log n)\), and that of Algorithm 6 is \(O(n\log m(k+\log n\log\log n))\). The analysis will be done with respect to an arbitrary \(T_{i}\). In particular, we will show that after the specified amount of time, with high probability, we will either know \(q_{i}\) or realize that \(q_{i}>k\). It will then follow that the same statement holds for every \(T_{i}\) (for \(1\leq i\leq(n-m+1)\). Consider phase \(\ell\) of Step 2 (for an arbitrary \(1\leq\ell\leq w\)). Let \(2^{\ell}k<q_{i}\leq 2^{\ell+1}k\) for some \(i\). Using the fact that \(\binom{a}{b}\approx\left(\frac{ae}{b}\right)^{b}\), the probability of isolating one of the mismatches in one run of the sampling step is:

\[\frac{\binom{m-q_{i}}{m/(2^{\ell+1}k)-1}q_{i}}{\binom{m}{m/(2^{\ell+1}k)}} \geq\frac{\binom{m-2^{\ell+1}k}{m/(2^{\ell+1}k)-1}2^{\ell}k}{\binom{m}{m/(2^ {\ell+1}k)}}\geq\frac{1}{2e}\]

As a result, using Chernoff bounds (Equation (3) with \(\delta=1/2\), for example), it follows that if \(13 ke\) sampling steps are made in phase \(\ell\), then at least \(6k\) of these steps will result in the isolation of single mismatches (not all of them need be distinct) with high probability (assuming that \(k=\Omega(\log n)\)). Moreover, we can see that at least \(1.1k\) of these mismatches will be distinct. This is because the probability that \(\leq 1.1k\) of these are distinct is \(\leq\binom{q_{i}}{1.1k}/\binom{1.1k}{q_{i}}^{6k}\leq 2^{-2.64k}\) using the fact that \(q_{i}\geq 2k\). This probability will be very low when \(k=\Omega(\log n)\). In the above analysis, we have assumed that \(k=\Omega(\log n)\). If this is not the case, in any phase of Step 2, we can do \(c\alpha\log n\) sampling steps, for some suitable constant \(c\). In this case, also we can perform an analysis similar to that of the above case using Chernoff bounds. Specifically, we can show that with high probability, we will be able to identify all of the mismatches between \(T_{i}\) and \(P\). As a result, each phase of Step 2 takes \(O(n\log m(k+\log n))\) time. We have \(O(\log m)\) phases. Thus, the run time of Step 2 is \(O(n\log^{2}m(k+\log n))\). Furthermore, the probability that the condition in Step 3 holds is very high.