## 6 Analysis of the Algorithm
### Analysis of Boundary-Phase of Algorithm Recover-Motif
We also have the closed form for the function \(f(x)=\frac{e^{\theta jx}}{1-e^{\theta x}}\), which implies:  
\[f^{\prime}(x) = \frac{\theta je^{\theta jx}(1-e^{\theta x})-e^{\theta jx}(-\theta e ^{\theta x})}{(1-e^{\theta x})^{2}} \tag{21}\] \[= \frac{\theta je^{\theta jx}-\theta(j-1)e^{\theta(j+1)x}}{(1-e^{ \theta x})^{2}} \tag{22}\]  
Let \(\theta=\ln a\) and \(x=1\). We have \(\sum_{i=j}^{\infty}ia^{i}=\frac{ja^{j}-(j-1)a^{j+1}}{(1-a)^{2}}<\frac{ja^{j}}{ (1-a)^{2}}\). Statement i. By Lemma 20, with a probability of at most \(\frac{2c^{v}}{1-c}\), one of the left motif first \(y\) character region of \(S_{i}\) will change \(\frac{\beta}{2y}\) characters. Therefore, with a probability of at most \(P_{1}=\frac{2c^{v}}{1-c}\), \(\mathrm{roughLeft}_{S_{i}}>\mathrm{LB}(S_{i})\). For a pair of positions, \(p\), in \(S_{1}\), and \(q\), in \(S_{2}\), without loss of generality, assume that \(p\) has a larger distance to the left boundary \(\mathrm{LB}(S_{1})\) of \(S_{1}\) than \(q\) to the left boundary \(\mathrm{LB}(S_{2})\) of \(S_{2}\). Let \(v+y\) be the distance from \(p\) to the left boundary \(\mathrm{LB}(S_{1})\) of \(S_{1}\). By Lemma 19, the probability is at most \(c^{v+y}\) that there will be a match. There are at most \((v+y)\) cases for \(q\). With a probability of at most \(P_{2}=2\sum_{y=u}^{\infty}(v+y)c^{v+y}<\frac{2(v+u)c^{v+u}}{(1-c)^{2}}\), by inequality (20), \(\mathrm{roughLeft}_{S_{1}}<LB(S_{1})-(v+u)\). For the cases that one position is in a random region and has a distance more than \(d_{0}\log n\) from the left boundary, the probability is at most \(P_{3}=n^{2}c^{d_{0}\log n}<\frac{1}{5\cdot 2^{n}}\) by inequality (14). Therefore, we have a total probability of at most \(P_{1}+P_{2}+P_{3}\) that \(\mathrm{roughLeft}_{S_{1}}\) is not in \([\mathrm{LB}(S_{1})-(v+u),\mathrm{LB}(S_{1})]\). Statement ii. One can also provide a symmetric analogous proof for this statement. Statement iii. The computation time easily follows from the implementation of Improve-Boundaries \((S_{1},L_{S_{1}},R_{S_{1}},S_{2},L_{S_{2}},R_{S_{2}})\). **Lemma 22**. : _Assume that for each \(L\) with \(0<L\leq\frac{|G|}{2}\), with a probability of at most \(\varsigma(n)\), \(L_{S_{i}}\
ot\in[\mathrm{LB}_{S_{i}}-L,\)\(\mathrm{LB}_{S_{i}}+L]\) for \(i=1,2\), where \((L_{S_{1}},R_{S_{1}},L_{S_{2}},R_{S_{2}})=\text{Collision-Detection($S_{1},U_{1},S_{2},U_{2}$)}\), \(U_{1}=\text{Point-Selection($S_{1},L$)}\) and \(U_{2}=\text{Point-Selection($S_{2},L$)}\). Then, with a probability of at most \(\varsigma(n)+\frac{2(v+u_{1})c^{v+u_{1}}}{(1-c)^{2}}+\frac{c^{v}}{1-c}+\frac{ 1}{5\cdot 2^{n}}\), Initial-Boundary($S_{1},S_{2}$) returns \((L_{S_{1}},R_{S_{1}},L_{S_{2}},R_{S_{2}})\) with \(L_{S_{i}}\
ot\in[\mathrm{LB}(S_{i})-(v+u_{1}),\mathrm{LB}(S_{i})]\) or \(R_{S_{i}}\
ot\in[\mathrm{RB}(S_{i}),\mathrm{RB}(S_{i})+(v+u_{1}))]\) for \(i=1,2\)._  
Proof. : It follows from Lemma 21:  
**Lemma 23**. : _Assume that with a probability of \(p<0.5\), each \(S^{\prime}_{2i-1}\) has its rough boundaries, \(\mathrm{roughLeft}_{S^{\prime}_{2i-1}}\
ot\in[\mathrm{LB}(S^{\prime}_{2i-1} )-u,\mathrm{LB}(S^{\prime}_{2i-1})]\) or \(\mathrm{roughRight}_{S^{\prime}_{2i-1}}\
ot\in[\mathrm{RB}(S^{\prime}_{2i-1} ),\mathrm{RB}(S^{\prime}_{2i-1})+u]\); then, with a probability of at most \(e^{-(0.5-p-c)^{k_{1}}/3}\), \(l_{motif}\) is not in \([|G|-2u,|G|+2u]\), where \(l_{motif}\) is selected as the median of \(\cup_{i=1}^{k_{1}}\{(\mathrm{roughRight}_{S^{\prime}_{2i-1}}-\mathrm{roughLeft }_{S^{\prime}_{2i-1}})\}\)._  
Proof. : If both \(\mathrm{roughLeft}_{S^{\prime}_{2i-1}}\in[\mathrm{LB}(S^{\prime}_{2i-1})-u, \mathrm{LB}(S^{\prime}_{2i-1})]\) and \(\mathrm{roughRight}_{S^{\prime}_{2i-1}}\in[\mathrm{RB}(S^{\prime}_{2i-1}), \mathrm{RB}(S^{\prime}_{2i-1})+u]\), then \((\mathrm{roughRight}_{S^{\prime}_{2i-1}}-\mathrm{roughLeft}_{S^{\prime}_{2i-1 }})\) is in \([|G|-2u,|G|+2u]\).