## 6 Analysis of the Algorithm
### Randomized Algorithms for Motif Detection
#### 6.5.2. Sublinear Time Algorithm for a \(\frac{1}{(\log n)^{2+\mu}}\) Mutation Rate  
In this section, we give an algorithm for the case with at most \(\alpha=\frac{1}{(\log n)^{2+\mu}}\) mutation rate. The performance of the algorithm is stated in Theorem 2. **Definition 43**. : A position, \(p\), in the motif region, \(\aleph(S)\), of an input sequence, \(S\), is _damaged_ if there exists at least one mutation in \(S[p,p+d_{0}\log n-1]\), where \(d_{0}\) is defined in item (xvii) in Definition 8. **Lemma 44**. : _Assume that \(\alpha L=(\log n)^{1+\Omega(1)}\). With a probability of at most \(e^{-(\log n)^{1+\Omega(1)}}\), there are more than \(\frac{M_{1}(L)}{(\log n)^{\Omega(1)}}\) positions that are from the \(M(L)\) (see Definition 10 for \(M(. )\) and \(M_{1}(. )\)) sampled positions that are damaged in an interval of a length pf \(L\)._  
**Proof:** By Theorem 16, with a probability of at most \(P_{1}=2^{-\alpha L}\) (let \(\delta=2\)), there are more than \(3\alpha L\) mutations in an interval of a length of \(L\). Therefore, with a probability of at most \(2^{-\alpha L}=e^{-(\log n)^{1+\Omega(1)}}\), there are more than \(3\alpha L\log n\) positions that are damaged. Therefore, each random position in an interval of a length of \(L\) has at most a probability of \(\frac{3\alpha L\log n}{L}=3\alpha\log n\) to be damaged. Since \(\alpha=(\frac{1}{(\log n)^{2+\Omega(1)}})\) and \(M(L)\) positions are sampled, by Theorem 16, with a probability of at most \(P_{2}=2^{-(3\alpha\log n)M(L)}=e^{-(\log n)^{1+\Omega(1)}}\) (let \(\delta=2\)), the number of damaged positions sampled in an interval of a length of \(L\) is more than \(((1+\delta)3\alpha\log n)M=(9\alpha\log n)M(L)=\frac{M_{1}(L)}{(\log n)^{ \Omega(1)}}\). Thus, with a total probability of at most \(P_{1}+P_{2}=e^{-(\log n)^{1+\Omega(1)}}\), there are more than \(\frac{M_{1}(L)}{(\log n)^{\Omega(1)}}\) damaged positions that are from the \(M(L)\) sampled positions in an interval of a length of \(L\). **Definition 45**. : Let \(A\) be a set of positions in an input sequence, \(S\), with \(\aleph(S)=S[i,j]\). Let \(A(S,\aleph(S))=\{x-i+1|x\in A\cap[i,j]\}\). In other words, \(A(S,\aleph(S))\) contains all the positions of \(A\) in \(\aleph(S)\). **Lemma 46**. : _Let algorithm-type=RANDOMIZED-SUBLINEAR. Assume that \(|G|<\frac{(\log n)^{3+\tau}}{100}\) and \(L\) is an integer with \(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}=\text{Point-Selection}(S_{1},L,I_{1})\), \(U_{2}=\text{Point-Selection}(S_{2},L,I_{2}])\) and \((L_{S_{1}},R_{S_{1}},L_{S_{2}},R_{S_{2}})=\text{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_ \(|G|/4\) _distance from_ \(\mathrm{LB}(S_{1})\) _and the left rough boundary,_ \(L_{S_{2}}\)_, has at most a_ \(|G|/4\) _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_ \(|G|/4\) _distance from_ \(\mathrm{RB}(S_{1})\) _and the right boundary of_ \(R_{S_{2}}\) _has at most a_ \(|G|/4\) _distance from_ \(\mathrm{RB}(S_{2})\)_._  
**Proof:** For two sequences, \(S_{1}\) and \(S_{2}\), it is easy to see that there is a common position in both motif regions of the two sequences, such that there is no mutation in the next \(d_{0}\log n\) characters with a high probability. This is because that mutation probability is small.