## 2 Materials and Methods
### Deterministic Algorithms
#### 2.2.2 Pattern Matching with \(K\) Mismatches  
For the \(k\) mismatches problem, without wild cards, an \(O(k(m\log m+n))\) time algorithm that requires \(O(k(m+n))\) additional space is presented in [19]. Another algorithm, that takes \(O(m\log m+kn)\) time and uses only \(O(m)\) additional space, is presented in [20]. We define the following problem, which is of interest in the discussion.  
**Problem 1**.: _Subset \(k\) mismatches: Given a text \(T\) of length \(n\), a pattern \(P\) of length \(m\), a set of positions \(S=\{i|1\leq i\leq n-m+1\}\) and an integer \(k\), output the positions \(i\in S\) for which \(Hd(P,T_{i})\leq k\)._  
The subset \(k\) mismatches problem becomes the regular \(k\) mismatches problem if \(|S|=n-m+1\). Thus, it can be solved by the \(O(nk)\) algorithms mentioned above. However, if \(|S|<<n\), then the \(O(nk)\) algorithms are too costly. A better alternative is to use the Kangaroo method proposed in [11].  
The Kangaroo method can verify if \(Hd(P,T_{i})\leq k\) in \(O(k)\) time for any \(i\). The method works as follows. Build a suffix tree of \(T\#P\) and enhance it to support \(O(1)\) lowest common ancestor (LCA) queries. For a given \(i\), perform an LCA query to find the position of the first mismatch between \(P\) and \(T_{i}\). Let this position be \(j\). Then, perform another LCA to find the first mismatch between \(P_{j+1..m}\) and \(T_{i+j+1..i+m-1}\), which is the second mismatch of alignment \(i\). Continue to \"jump\" from one mismatch to the next, until the end of the pattern is reached or we have found more than \(k\) mismatches. The Kangaroo method can process \(|S|\) positions in \(O(n+m+|S|k)\) time, and it uses \(O(n+m)\) additional memory for the LCA enhanced suffix tree. We now prove the following result:  
**Theorem 2**.: _Subset \(k\) mismatches can be solved in \(O(n+m+|S|k)\) time using only \(O(m)\) additional memory._  
Proof.: The algorithm is the following. Build an LCA-enhanced suffix tree of the pattern. Scan the text from left to right: (1) find the longest unscanned region of the text that can be found somewhere in the pattern, say starting at position \(i\) of the pattern; call this region of the text \(R\); therefore, \(R\) is identical to \(P_{i..i+|R|-1}\).; and (2) for every alignment in \(S\) that overlaps \(R\), count the number of mismatches between \(R\) and the alignment, within the overlap region. To do this, consider an alignment in \(S\) that overlaps \(R\), such that the beginning of \(R\) aligns with the \(j\)-th character in the pattern. We want to count the number of mismatches between R and \(P_{j..j+|R|-1}\). However, since \(R\) is identical to \(P_{i..i+|R|-1}\), we can simply compare \(P_{i..i+|R|-1}\) and \(P_{j..j+|R|-1}\). This comparison can be done efficiently by jumping from one mismatch to the next, like in the Kangaroo method. Repeat from Step 1 until the entire text has been scanned. Every time we process an alignment, in Step 2, we either discover at least one additional mismatch or we reach the end of the alignment. This is true, because, otherwise, the alignment would match the text for more than \(|R|\) characters, which is not possible, from the way we defined \(R\). Every alignment for which we have found more than \(k\) mismatches is excluded from further consideration to ensure \(O(k)\) time per alignment. It takes \(O(m)\) time to build the LCA enhanced suffix tree of the pattern and \(O(n)\) additional time to scan the text from left to right. Thus, the total run time is \(O(n+m+|S|k)\) with \(O(m)\) additional memory. The pseudocode is given in Algorithm 2.