## 6 Analysis of the Algorithm
### Randomized Algorithms for Motif Detection
#### 6.5.2.
By Theorem 16, with a probability of at most \(P_{l}=2^{-\alpha|G|/4}\) (let \(\delta=2\)), there are more than \(3\alpha\frac{|G|}{4}\) mutated characters in the interval \(\aleph(S_{i})[1,\frac{|G|}{4}]\) for \(i=1,2\). Since the mutation probability is \(\alpha=(\frac{1}{(\log n)^{2+\alpha(1)}})\), with a probability of at most \(2^{-\alpha|G|/4}=e^{-(\log n)^{1+\alpha(1)}}\), there are more than \(3\alpha\cdot\frac{|G|}{4}d_{0}\log n\) positions to be damaged in \(\aleph(S_{i})[1,\frac{|G|}{4}]\). Similarly, we have a probability of at most \(P_{r}=e^{-(\log n)^{1+\alpha(1)}}\) that there are more than \(((3\alpha d_{0}\log n)\cdot\frac{|G|}{4})=\frac{|G|}{(\log n)^{\alpha(1)}}\) damaged positions in \(\aleph(S_{i})[\frac{3|G|}{4}-1,|G|]\). Now, we assume that left side has more than \(((3\alpha d_{0}\log n)\cdot\frac{|G|}{4})=\frac{|G|}{(\log n)^{\alpha(1)}}\) damaged positions and the right side, more than \(((3\alpha d_{0}\log n)\cdot\frac{|G|}{4})=\frac{|G|}{(\log n)^{\alpha(1)}}\) damaged positions in \(\aleph(S_{i})[\frac{3|G|}{4}-1,|G|]\). Since each position in each interval of a length of \(L\) is selected in \(\text{Point-Selection}(S_{1},S_{2},L)\), it is easy to verify the conclusions of this lemma. **Lemma 47**. : _Let algorithm-type=RANDOMIZED-SUBLINEAR. Assume that \(|G|\geq\frac{(\log n)^{3+\tau}}{100}\) and \(d_{0}\log n\leq L\leq|G|/2\). Let \(I_{1}\) be a set of intervals of the positions of \(S_{1}\) that satisfy \([\mathrm{LB}(S_{1})-L,\mathrm{LB}(S_{1})+L]\cup[\mathrm{RB}(S_{1})-L,\mathrm{ RB}(S_{1})+L]\subseteq\cup_{I^{\prime}\in I_{1}}I^{\prime}\). Let \(I_{2}\) be a set of intervals of the positions of \(S_{2}\) that satisfy \([\mathrm{LB}(S_{2})-L,\mathrm{LB}(S_{2})+L]\cup[\mathrm{RB}(S_{2})-L,\mathrm{ RB}(S_{2})+L]\subseteq\cup_{I^{\prime}\in I_{2}}I^{\prime}\). Let \(U_{1}=\)Point-Selection\((S_{1},L,I_{1})\), \(U_{2}=\)Point-Selection\((S_{2},L,I_{2}])\) and \((L_{S_{1}},R_{S_{1}},L_{S_{2}},R_{S_{2}})=\)Collision-Detection\((S_{1},U_{1},S_{2},U_{2})\). Then:_  
* _with a probability of at most_ \(\frac{1}{2^{\kappa}n^{3}}\)_, the left rough boundary,_ \(L_{S_{1}}\)_, has at most a_ \(2L\) _distance from_ \(\mathrm{LB}(S_{1})\) _and the left rough boundary,_ \(L_{S_{2}}\)_, has at most a_ \(2L\) _distance from_ \(\mathrm{LB}(S_{2})\)_._
* _With a probability of at most_ \(\frac{1}{2^{\kappa}n^{3}}\)_, the right rough boundary,_ \(R_{S_{1}}\)_, has at most a_ \(2L\) _distance from_ \(\mathrm{RB}(S_{1})\) _and the right boundary of_ \(R_{S_{2}}\) _has at most a_ \(2L\) _distance from_ \(\mathrm{RB}(S_{2})\)_._  
**Proof:** We prove the following two statements, which imply the lemma. * With a probability of at most \(\frac{1}{2^{\kappa}n^{3}}\), there are no intervals, \(A_{i}\) from \(S_{1}\) and \(B_{j}\) from \(S_{2}\), such that: (1) \(||A_{i}(S_{1},\aleph(S_{1}))\cap B_{j}(S_{2},\aleph(S_{2}))||\) is at least \(\frac{L}{2}\)* with a probability of at most \(\frac{1}{2^{x}n^{3}}\), there are no intervals, \(A_{i}\) from \(S_{1}\) and \(B_{j}\) from \(S_{2}\), such that: (1) \(||A_{i}(S_{1},\aleph(S_{1}))\cap B_{j}(S_{2},\aleph(S_{2}))||\) is at least \(\frac{L}{2}\); (2) the right boundary of \(S_{1}\) has at most a \(2L\) distance from \(A_{i}\); (3) the right boundary of \(S_{2}\) has at most a \(2L\) distance from \(B_{j}\); and (4) there is a collision between the sampled positions in \(A_{i}\) and \(B_{j}\). We only prove statement i. The proof for statement ii is similar to that for statement i. Assume that \(L\) satisfies the condition of this lemma. Select \(A_{i}\) from \(S_{1}\) and \(B_{j}\) from \(S_{2}\) to be the first pair of intervals of a size of \(L\) with \(||A_{i}(S_{1},\aleph(S_{1}))\cap B_{j}(S_{2},\aleph(S_{2}))||\geq\frac{L}{2}\). This is because when a leftmost interval of a length of \(L\) is fully inside the motif region of the first sequence, we can always find the second interval from the second sequence with an intersection of a length of at least \(\frac{L}{2}\).