## 2 Materials and Methods
### Deterministic Algorithms
#### 2.2.1 Pattern Matching with Mismatches  
For pattern matching with mismatches, without wild cards, [PERSON] [10] gave the following \(O(n\sqrt{m\log m})\) time algorithm. Let \(A\) be a set of the most frequent characters in the pattern: (1) using convolutions, count how many matches each character in \(A\) contributes to every alignment; (2) using marking, count how many matches each character in \(\Sigma-A\) contributes to every alignment; and (3) add the two numbers to find for every alignment, the number of matches between the pattern and the text. The convolutions take \(O(|A|n\log m)\) time. A character in \(\Sigma-A\) cannot appear more than \(m/|A|\) times in the pattern; otherwise, each character in \(A\) has a frequency greater than \(m/|A|\), which is not possible.  
Thus, the run time for marking is \(O(nm/|A|)\). If we equate the two run times, we find the optimal \(|A|=\sqrt{m/\log m}\), which gives a total run time of \(O(n\sqrt{m\log m})\).  
An Example: Consider the case of \(T=2\ 3\ 1\ 1\ 4\ 1\ 2\ 3\ 4\ 4\ 2\ 1\ 1\ 3\ 2\) and \(P=1\ 2\ 3\ 4\). Since each character in the pattern occurs an equal number of times, we can pick \(A\) arbitrarily. Let \(A=\{1,2\}\). In Step 1, convolution is used to count the number of matches contributed by each character in \(A\). We obtain an array \(M_{1}[1:12]\), such that \(M_{1}[i]\) is the number of matches contributed by characters in \(A\) to the alignment of \(P\) with \(T_{i}\), for \(1\leq i\leq 12\). In this example, \(M_{1}=[0,0,1,1,0,2,0,0,0,1,0,1]\). In Step 2, we compute, using marking, the number of matches contributed by the characters \(3\) and \(4\) to each alignment between \(T\) and \(P\). We get another array \(M_{2}[1:12]\), such that \(M_{2}[i]\) is the number of matches contributed by \(3\) and \(4\) to the alignment between \(T_{i}\) and \(P\), for \(1\leq i\leq 12\). Specific to this example, \(M_{2}=[0,1,0,0,0,2,1,0,0,0,0,1]\). In Step 3, we add \(M_{1}\) and \(M_{2}\) to get the number of matches between \(T_{i}\) and \(P\), for \(1\leq i\leq 12\). In this example, this sum yields: \([0,1,1,1,0,4,1,0,0,1,0,2]\).  
For pattern matching with mismatches and wild cards, a fairly complex algorithm is given in [11]. The run time of this algorithm is \(O(n\sqrt{g}\log m)\) where \(g\) is the number of non-wild card positions in the pattern. The problem can also be solved through a simple modification of [PERSON]'s algorithm, in time \(O(n\sqrt{m\log m})\), as pointed out in [17]. We now prove the following result:  
**Theorem 1**.: _Pattern matching with mismatches and wild cards can be solved in \(O(n\sqrt{g\log m})\) time, where \(g\) is the number of non-wild card positions in the pattern._  
**Proof.** Ignoring the wild cards for now, let \(A\) be the set of the most frequent characters in the pattern. As above, count matches contributed by characters in \(A\) and \(\Sigma-A\) using convolution and marking, respectively. By a similar reasoning as above, the characters used in the marking phase will not appear more than \(g/|A|\) times in the pattern. If we equate the run times for the two phases, we obtain \(O(n\sqrt{g\log m})\) time. We are now left to count how many matches are contributed by the wild cards. For a string \(S\) and a character \(\alpha\), define \(S^{\
eg\alpha}\) as \(S^{\
eg\alpha}[i]=1-S^{\alpha}[i]\). Let \(w\) be the wild card character. Compute \(C=convolution(T^{\
eg w},P^{\
eg w})\). Then, for every alignment \(i\), the number of positions that have a wild card either in the text, or the pattern, or both, is \(m-C[i]\). Add \(m-C[i]\) to the previously-computed counts and output. The total run time is \(O(n\sqrt{g\log m})\). \(\qed\)