## 7 Case Studies  
In Section 2, we considered three practically relevant algorithms, namely [PERSON]'s algorithm, backward oracle matching (BOM), and backward (non)-deterministic DAWG matching (B(N)DM). Now, we compare the distributions of running time costs of these algorithms for several patterns over the DNA alphabet {A,C,G,T}. Figure 3 shows these distributions for the patterns ATATAT and ACGTAC for text lengths 100 and 500 under a second order Markovian text model estimated from the human genome. For text length 500, the distributions for Horspool and B(N)DM resemble the shape of normal distributions. In fact, for [PERSON]'s algorithm it has been proven that the distribution is asymptotically normal [12]. For smaller text lengths (e.g., 100, as shown in left column of Figure 3), the distributions are less smooth than for longer texts. It is remarkable that for BOM we find zero probabilities with a fixed period. The period equals \(m+1\) which is 7 in the shown examples. This behavior is caused by the factor-based nature of BOM; when a suffix of the search window has been recognized as not being a factor (substring) of the pattern, the window is just moved far enough to exclude this substring, creating the relation \(\text{shift}^{p}(w)=m-\xi^{p}(w)+1\) between cost and shift of a window \(w\). As the following lemma shows, this property is a sufficient condition for the observed zero probabilities. **Lemma 5**: _Let a window-based pattern matching algorithm \(A\), a pattern \(p\) with \(|p|=m\), and the functions shift \({}^{A,p}\) and \(\xi^{A,p}\) be given such that shift \({}^{A,p}(w)=m-\xi^{A,p}(w)+1\) for all \(w\in\Sigma^{m}\). Then,_  
\[\xi^{A,p}(s)+n+1\
ot\equiv 0\mod(m+1)\]  
_for all \(n\in\mathbb{N}\) and all \(s\in\Sigma^{n}\)._  
ProofLet \(w_{1},\ldots,w_{k}\) be the sequence of windows examined by algorithm \(A\) when processing the text \(s\in\Sigma^{n}\). In the beginning, the rightmost position of the current window is at position \(m-1\) and is moved by _shift_\({}^{A,p}(w_{i})\) after processing window \(w_{i}\). After processing all windows it is beyond the end of the text. Formally,  
\[n\leq m-1+\sum_{i=1}^{k}\text{shift}\,^{A,p}(w_{i})<n+m\]  
Figure 3: Exact distributions of character access counts for patterns ATATAT (top) and ACGTAC (bottom) for text length 100 (left) and text length 500 (right). A second order Markovian text model estimated from the human genome is used. By using the assumption that _shift_\({}^{A,p}(w)=m-\xi^{A,p}(w)+1\), we obtain  
\[n\leq m-1+\sum_{i=1}^{k}\left(m-\xi^{A,p}(w_{i})+1\right)<n+m\] \[\Longleftrightarrow n\leq m-1+k(m+1)-\xi^{A,p}(s)<n+m\] \[\Longleftrightarrow k(m+1)<\xi^{A,p}(s)+n+1\leq k(m+1)+m\]  
which means that \(\xi^{A,p}(s)+n+1\) lies strictly between \(k\)-times and \((k+1)\)-times \(m+1\) and thus cannot be a multiple of \(m+1\). \(\Box\)  
The probability that one pattern matching algorithm is faster than another depends on the pattern. Using the technique introduced in Section 6, we can quantify the strength of this effect. Figure 4 shows distributions of cost _differences_ for different patterns and algorithms. That means, the probability that the first algorithm is faster is represented by the area under the curve left of zero. For the pattern ACCCCC and a random text of length 100, for example, there is a 53.9% probability that [PERSON]'s algorithm needs fewer character accesses than B(N)DM (for the same second order Markovian model as used before), while for ACGTAC, the probability is only 0.0016%. Figure 4: Exact distributions of differences in character access counts for different patterns using a second order Markovian text model estimated from the human genome and random texts of lengths 100. Worth noting and perhaps surprising is the fact that there is a non-zero probability of BOM being faster than B(N)DM although, _shift_\({}^{\text{B(N)DM},p}(w)\geq\textit{shift}^{\text{BOM},p}(w)\) for all window contents \(w\).