## 2 Materials and Methods
### A Las Vegas Algorithm for \(K\) Mismatches  
#### 2.4.1 The 1 Mismatch Problem  
Problem definition: For this problem, also, the inputs are two strings \(T\) and \(P\) with \(|T|=n,|P|=m,\)\(m\leq n\) and possible wild cards in \(T\) and \(P\). Let \(T_{i}\) stand for the substring \(t_{i}t_{i+1}\ldots t_{i+m-1}\), for any \(i\), with \(1\leq i\leq(n-m+1)\). The problem is to check if the Hamming distance between \(T_{i}\) and \(P\) is exactly 1, for \(1\leq i\leq(n-m+1)\). The following Lemma is shown in [17]. **Lemma 1**. : _The 1 mismatch problem can be solved in \(O(n\log m)\) time using a constant number of convolution operations._  
The algorithm: Assume that each wild card in the pattern as well as the text is replaced with a zero. Furthermore, assume that the characters in the text, as well as the pattern are integers in the range \([1:|\Sigma|]\) where \(\Sigma\) is the alphabet of concern. Let \(e_{i,j}\) stand for the \"error term\" introduced by the character \(t_{i+j-1}\) in \(T_{i}\) and the character \(p_{j}\) in \(P\), and its value is \((t_{i+j-1}-p_{j})^{2}t_{i+j-1}p_{j}\). Furthermore, let \(E_{i}=\sum_{j=1}^{m}e_{i,j}\). There are four steps in the algorithm:  
1. Compute \(E_{i}\) for \(1\leq i\leq(n-m+1)\). Note that \(E_{i}\) will be zero if \(T_{i}\) and \(P\) match (assuming that a wild card can be matched with any character). \(E_{i}=\sum_{j=1}^{m}(t_{i+j-1}-p_{j})^{2}t_{i+j-1}p_{j}=\sum_{j=1}^{m}t_{i+j-1 }^{3}p_{j}+\sum_{j=1}^{m}t_{i+j-1}^{3}p_{j}^{3}-2\sum_{j=1}^{m}t_{i+j-1}^{2}p_ {j}^{2}\). Thus, this step can be completed with three convolution operations. 2. Compute \(E_{i}^{\prime}\) for \(1\leq i\leq(n-m+1)\), where \(E_{i}^{\prime}=\sum_{j=1}^{m}(i+j-1)(t_{i+j-1}-p_{j})^{2}p_{j}t_{i+j-1}\) (for \(1\leq i\leq(n-m+1)\)). Like Step 1, this step can also be completed with three convolution operations. 3. Let \(B_{i}=E_{i}^{\prime}/E_{i}\) if \(E_{i}\
eq 0\), for \(1\leq i\leq(n-m+1)\). Note that if the Hamming distance between \(T_{i}\) and \(P\) is exactly one, then \(B_{i}\) will give the position in the text where this mismatch occurs. 4. If for any \(i\) (\(1\leq i\leq(n-m+1)\)), \(E_{i}\
eq 0\) and if \((t_{B_{i}}-p_{B_{i}-i+1})^{2}t_{B_{i}}p_{B_{i}-i+1}=E_{i}\), then we conclude that the Hamming distance between \(T_{i}\) and \(P\) is exactly one. Note: If the Hamming distance between \(T_{i}\) and \(P\) is exactly 1 (for any \(i\)), then the above algorithm will not only detect it, but also will identify the position where there is a mismatch. Specifically, it will identify the integer \(j\), such that \(t_{i+j-1}\
eq p_{j}\). An example. Consider the case where \(\Sigma=\{1,2,3,4,5,6\},\ T=5\ 6\ 4\ 6\ 2\ *\ 3\ 3\ 4\ 5\ 1\ *\ 1\ 2\ 5\ 5\ 5\ 6\ 4\ 3\) and \(P=2\ 5\ 6\ 3\). Here, \(*\) represents the wild card. In Step 1, we compute \(E_{i}\), for \(1\leq i\leq 17\). For example, \(E_{1}=(5-2)^{2}\times 5\times 2+(6-5)^{2}\times 6\times 5+(4-6)^{2}\times 4 \times 6+(6-3)^{2}\times 6\times 3=378\); \(E_{2}=(6-2)^{2}\times 6\times 2+(4-5)^{2}\times 4\times 5+(6-6)^{2}\times 6 \times 6+(2-3)^{2}\times 2\times 3=218\); \(E_{3}=254\); \(E_{5}=(2-2)^{2}\times 2\times 2+0+(6-3)^{2}\times 6\times 3+(3-3)^{2}\times 3 \times 3=162\). Note that since \(t_{5}\) is a wild card, it matches with any character in the pattern. Furthermore, \(E_{9}=182\). In Step 2, we compute \(E_{i}^{\prime}\), for \(1\leq i\leq 17\). For instance, \(E_{1}^{\prime}=1\times(5-2)^{2}\times 5\times 2+2\times(6-5)^{2}\times 6\times 5+3(4-6)^{2} \times 4\times 6+4\times(6-3)^{2}\times 6\times 3=1410\); \(E_{5}^{\prime}=5\times(2-2)^{2}\times 2\times 2+0+7\times(6-3)^{2}\times 6 \times 3+8\times(3-3)^{2}\times 3\times 3=1134\). In Step 3, the value of \(B_{i}=E_{i}^{\prime}/E_{i}\) is computed for \(1\leq i\leq 17\). For example, \(B_{1}=E_{1}^{\prime}/E_{1}=1410/378\approx 3.73\); \(B_{5}=E_{5}^{\prime}/E_{5}=1134/162=7\). In Step 4, we identify all of the positions in the text corresponding to a single mismatch. For instance, we note that \(E_{5}\
eq 0\) and \((t_{7}-p_{3})^{2}\times t_{7}\times p_{3}=E_{5}\).