## 2 Materials and Methods
### Approximate Counting of Mismatches  
The algorithm of [13] takes as input a text \(T=t_{1}t_{2}\ldots t_{n}\) and a pattern \(P=p_{1}p_{2}\ldots p_{m}\) and approximately counts the Hamming distance between \(T_{i}\) and \(P\) for every \(1\leq i\leq(n-m+1)\). In particular, if the Hamming distance between \(T_{i}\) and \(P\) is \(H_{i}\) for some \(i\), then the algorithm outputs \(h_{i}\) where \(H_{i}\leq h_{i}\leq(1+\epsilon)H_{i}\) for any \(\epsilon>0\) with high probability (_i.e._, a probability of \(\geq(1-m^{-\alpha})\)). The run time of the algorithm is \(O(n\log^{2}m/\epsilon^{2})\). In this section, we show how to extend this algorithm to the case where there could be wild cards in the text and/or the pattern. Let \(\Sigma\) be the alphabet under concern, and let \(\sigma=|\Sigma|\). The algorithm runs in phases, and in each phase, we randomly map the elements of \(\Sigma\) to \(\{1,2\}\). A wild card is mapped to a zero. Under this mapping, we transform \(T\) and \(P\) to \(T^{\prime}\) and \(P^{\prime}\), respectively. We then compute a vector \(C\) where \(C[i]=\sum_{j=1}^{m}(t^{\prime}_{i+j-1}-p^{\prime}_{j})^{2}t^{\prime}_{i+j-1}p^{ \prime}_{j}\). This can be done using \(O(1)\) convolution operations (as in Section 2.4.1; see also [17]). A series of \(r\) such phases (for some relevant value of \(r\)) is done, at the end of which, we produce estimates on the Hamming distances. The intuition is that if a character \(x\) in \(T^{\prime}\) is aligned with a character \(y\) in \(P^{\prime}\), then across all of the \(r\) phases, the expected contribution to \(C\) from these characters is \(r\) if \(x\
eq y\) (assuming that \(x\) and \(y\) are non-wild cards). If \(x=y\) or if one or both of \(x\) and \(y\) are a wild card, the contribution to \(C\) is zero. ```
1 for\(i\gets 1\)to\((n-m+1)\)do\(C[i]=0\);
2 for\(\ell\gets 1\)to\(r\)do Let \(Q\) be a random mapping of \(\Sigma\) to \(\{1,2\}\). In particular, each element of \(\Sigma\) is mapped to 1 or 2 randomly with equal probability. Each wild card is mapped to a zero. Obtain two strings \(T^{\prime}\) and \(P^{\prime}\) where \(t^{\prime}_{i}=Q(t_{i})\) for \(1\leq i\leq n\) and \(p^{\prime}_{j}=Q(p_{j})\) for \(1\leq j\leq m\); Compute a vector \(C_{\ell}\) where \(C_{\ell}[i]=\sum_{j=1}^{m}(t^{\prime}_{i+j-1}-p^{\prime}_{j})^{2}\)\(t^{\prime}_{i+j-1}p^{\prime}_{j}\) for \(1\leq i\leq(n-m+1)\); for\(i\gets 1\)to\((n-m+1)\)do\(C[i]=C[i]+C_{\ell}[i]\) ;
3 for\(i\gets 1\)to\((n-m+1)\)do Output \(h_{i}=\frac{C[i]}{r}\); Here, \(h_{i}\) is an estimate on the Hamming distance \(H_{i}\) between \(T_{i}\) and \(P\). ```  
**Algorithm 4**  
Analysis: Let \(x\) be a character in \(T\), and let \(y\) be a character in \(P\). Clearly, if \(x=y\) or if one or both of \(x\) and \(y\) are a wild card, the contribution of \(x\) and \(y\) to any \(C_{\ell}[i]\) is zero. If \(x\) and \(y\) are non-wild cards and if \(x\
eq y\), then the expected contribution of these to any \(C_{\ell}[i]\) is 1. Across all of the \(r\) phases, the expected contribution of \(x\) and \(y\) to any \(C_{\ell}[i]\) is \(r\). For a given \(x\) and \(y\), we can think of each phase as a Bernoulli trial with equal probabilities for success and failure. A success refers to the possibility of \(Q(x)\
eq Q(y)\). The expected number of successes in \(r\) phases is \(\frac{r}{2}\). Using Chernoff bounds (Equation 2), this contribution is no more than \((1+\epsilon)r\) with probability \(\geq 1-\exp(-\epsilon^{2}r/6)\). The probability that this statement holds for every pair \((x,y)\) is \(\geq 1-m^{2}\exp(-\epsilon^{2}r/6)\). This probability will be \(\geq 1-m^{-\alpha}/2\) if \(r\geq\frac{6(\alpha+3)\log_{\epsilon}m}{\epsilon^{2}}\). Similarly, we can show that for any pair of non-wild card characters, the contribution of them to any \(C_{\ell}[i]\) is no less than \((1-\epsilon)r\) with probability \(\geq 1-m^{-\alpha}/2\) if \(r\geq\frac{4(\alpha+3)\log_{\epsilon}m}{\epsilon^{2}}\).