## 6 Analysis of the Algorithm
### Analysis of Extract-Phase and Voting-Phase of Algorithm Recover-Motif  
Lemma 27 shows that with a high probability, the left and last parts of the motif region in a \(\Theta(n,G,\alpha)\)-sequence do not change much. **Lemma 27**: _With a probability of at most \(Q_{0}\) defined in Equation (13), a \(\Theta(n,G,\alpha)\)-sequence, \(S\), does not contain a stable motif region._  
The probability is \(V_{1}=2(v-1)\alpha\) not to satisfy conditions (1) and (2) of item (iii) in Definition 25. Consider condition (3) of item (iii) in Definition 25. Since every character of \(\aleph(S)[1,m]\) (notice that \(m=|G|\)) has a probability of at most \(\alpha\) to mutate, by Corollary 18, the probability is at most \(e^{-\frac{1}{3}c^{2}r}\) that \(\mathrm{diff}(G[1,h],G^{\prime}[1,h])>\frac{\beta}{2}=\alpha+\epsilon\). Let \(V_{3}=\sum_{r=v}^{\infty}e^{-\frac{1}{3}c^{2}r}=\frac{c^{v}}{1-c}\), where \(c=e^{-\frac{1}{3}c^{2}}\), as defined in Definition 8. Therefore, the probability is at most \(V_{3}\) that \(\mathrm{diff}(G[1,h],G^{\prime}[1,h])>\frac{\beta}{2}=\alpha+\epsilon\) for some \(h\in\{v,v+1,\cdots,m\}\). Similarly, we define \(V_{4}=\sum_{r=v}^{\infty}e^{-\frac{1}{3}c^{2}r}\leq\frac{c^{v}}{1-c}\) for the probability on the right-hand side. The probability is at most \(V_{4}\) that \(\mathrm{diff}(G[m-h,m],G^{\prime}[m-h,m])>\frac{\beta}{2}=\alpha+\epsilon\) for some \(h\in\{v,v+1,\cdots,m\}\). The probability that \(S\) does not contain a stable motif region is at most \(V_{1}+V_{3}+V_{4}=Q_{0}\). Assume that \(Z_{1}=\{S^{\prime}_{1},\cdots,S^{\prime}_{2k_{1}}\}\) contains \(S^{\prime}_{2i-1}\), which contains a stable motif region. We fix such a \(S^{\prime}_{2i-1}\). * Define \(G_{L}=\aleph(S^{\prime}_{2i-1})[1,d_{0}\log n-1]\) to be the left part of the motif region, \(\aleph(S^{\prime}_{2i-1})\). * Define \(G_{R}=\aleph(S^{\prime}_{2i-1})[|G|-(d_{0}\log n)+1,|G|]\) to be the right part of the motif region, \(\aleph(S^{\prime}_{2i-1})\). Lemma 29 shows that with a high probability, Extract-Phase of algorithm Recover-Motif extracts the correct motif regions from the sequences in \(Z_{1}\). It uses \(G^{\prime\prime}\) to match \(\aleph(S)\) in another sequences, \(S\). The parameter, \(R\), gives a small probability that the matched region between \(G^{\prime\prime}\) and \(S\) is not in \(\aleph(S)\). **Lemma 29**:1. _Assume that_ \(G_{l}\) _and_ \(G_{r}\) _are fixed sequences of length_ \(d_{0}\log n\)_. Let_ \(S\) _be a_ \(\Theta(n,G,\alpha)\)_-sequence with_ \(M=\operatorname{Match}(G_{l},G_{r},S)\)_, and let_ \(w_{0}\) _be the number of characters of M that are not in the region of_ \(\aleph(S)\)_. Then, the probability is at most_ \(R\) _that_ \(w_{0}\geq 1\)_, where_ \(R\) _is defined in (_xv_) of Definition_ 8_._
2. _The probability is at most_ \(Q_{0}\) _that given a_ \(\Theta(n,G,\alpha)\)_-sequence_ \(S\)_,_ \(\operatorname{Match}(G_{L},G_{R},S)=\emptyset\)_._  
**Proof:** Assume that \(w_{0}\geq 1\). Let \(w\) be the number of characters outside of \(\aleph(S)\) on the left of \(M\), and let \(w^{\prime}\) be the number of characters outside of \(\aleph(S)\) on the right of \(M\). Clearly, \(w_{0}=w+w^{\prime}\). Since \(w_{0}\geq 1\), either \(w\geq 1\) or \(w^{\prime}\geq 1\). See Figure 1. Without loss of generality, we assume \(w\geq 1\). Statement i: There are two cases. Case (a): \(1\leq w<v\). By Lemma 19, the probability for this case is at most \(\frac{1}{t}\) for a fixed \(w\). The total probability for this case for \(1\leq w<v\) is at most \(\sum_{i=1}^{v-1}\frac{1}{t^{i}}\leq\sum_{i=1}^{\infty}\frac{1}{t^{i}}=\frac{1}{ t-1}\). Case (b): \(v\leq w\). By Lemma 19, the probability is at most \(e^{-\frac{2}{3}w}\) for a fixed \(w\). The total probability for \(v\leq w\) is at most \(\sum_{w=v}^{\infty}e^{-\frac{c^{2}}{3}w}=\frac{c^{v}}{1-c}\). The probability analysis is similar when \(w^{\prime}\geq 1\). Therefore, the probability for this case is at most \(R=(\frac{1}{t-1}+\frac{c^{v}}{1-c})\) for \(w_{0}\geq 1\).