## 6 Analysis of the Algorithm
### Analysis of Boundary-Phase of Algorithm Recover-Motif
: _Assume that:_  
* \(l_{motif}\in[|G|-2(v+u_{1}),|G|+2(v+u_{1})]\)_;_
* \(S\) _contains both a left half and a right half stable motif region and_ \(\mathrm{roughLeft}_{S}\in[\mathrm{LB}(S)-(v+u_{1}),\mathrm{LB}(S)]\) _and_ \(\mathrm{roughRight}_{S}\in[\mathrm{RB}(S),\mathrm{RB}(S)+(v+u_{1})]\) _(see Definition_ 8 _for_ \(u_{1}\) _and_ \(v\)_); and_
* _for each_ \(L\) _with_ \((v+u_{1})<L\leq\frac{|G|}{2}\)_, if_ \(S_{1}\) _has_ \(\mathrm{roughLeft}_{S_{1}}\in[\mathrm{LB}_{S_{1}}-L,\mathrm{LB}_{S_{1}}+L]\) _and_ \(\mathrm{roughRight}_{S_{1}}\in[\mathrm{RB}_{S_{1}}-L,\mathrm{RB}_{S_{1}}+L]\)_, then with a probability of at most_ \(\varsigma(n)\)_,_ \(L_{S^{\prime\prime}_{i}}\
ot\in[\mathrm{LB}_{S^{\prime\prime}_{i}}-2L, \mathrm{LB}_{S^{\prime\prime}_{i}}+2L]\) _for_ \(i=1,2\)_, where_ \((L_{S_{1}},R_{S_{1}},L_{S^{\prime\prime}_{i}},R_{S^{\prime\prime}_{i}})=\)___Collision-Detection (_\(S_{1},U_{1},S^{\prime\prime}_{i},U_{2}\)_),_ \(U_{1}=\)__Point-Selection_\((S_{1},L,[\mathrm{roughLeft}_{S_{1}}-2L,\mathrm{roughLeft}_{S_{1}}+2L])\cup\)__Point-Selection_\((S_{1},L,[\mathrm{roughRight}_{S_{1}}-2L,\mathrm{roughRight}_{S_{1}}+2L])\) _and_ \(U_{2}=\)__Point-Selection_\((S^{\prime\prime}_{i},L,[1,|S^{\prime\prime}_{i}|])\)_._
* _The rough boundaries for all sequences,_ \(S^{\prime\prime}_{i}\in Z_{2}\)_, are computed via_ \((L_{S},R_{S},L_{S^{\prime\prime}_{i}},R_{S^{\prime\prime}_{i}})=\)__\(\text{Collision-Detection}(S,U_{S},S^{\prime\prime}_{i},U_{S^{\prime\prime}_{i}})\) _and_ \((L_{S},R_{S},\mathrm{roughLeft}_{S^{\prime\prime}_{i}},\mathrm{roughRight}_{S ^{\prime\prime}_{i}})=\)__\(\text{Improve-Boundaries}(S,L_{S},R_{S},S^{\prime\prime}_{i},L_{S^{\prime\prime}_{i}},R_{S^{ \prime\prime}_{i}},2L)\)_._  
_Then, with a probability of at most \(e^{-\frac{\epsilon^{2}k_{2}}{3}}\), there are more than \((2(\varsigma(n)+(v+u_{1})\frac{e^{v+u}}{1-c}+\frac{e^{v}}{1-c})+\epsilon)k_{2}\) sequences \(S^{\prime\prime}_{i}\) in \(\{S^{\prime\prime}_{1},\cdots,S^{\prime\prime}_{k_{2}}\}\) with \(\mathrm{roughLeft}(S^{\prime\prime}_{i})\
ot\in[\mathrm{LB}(S^{\prime\prime}_ {i})-(v+u),\mathrm{LB}(S^{\prime\prime}_{i})]\) or \(\mathrm{roughRight}(S^{\prime\prime}_{i})\
ot\in[\mathrm{RB}(S^{\prime\prime}_ {i}),\mathrm{RB}(S^{\prime\prime}_{i})+(v+u)]\)._  
* According to the condition of this lemma, with a probability of at most \(P_{1}=\varsigma(n)\), \(L_{S^{\prime\prime}_{i}}\
ot\in[\mathrm{LB}_{S^{\prime\prime}_{i}}-2L, \mathrm{LB}_{S^{\prime\prime}_{i}}+2L]\), where \((L_{S},R_{S},L_{S^{\prime\prime}_{i}},R_{S^{\prime\prime}_{i}})=\)Collision-Detection(\(S,U_{1},S^{\prime\prime}_{i},U_{2}\)) and \((U_{1},U_{2})=\)__Point-Selection\((S,S^{\prime\prime}_{i},L)\). For a fixed pattern from \(S\), by Lemma 19, with a probability of at most \(\sum_{y=v+u}^{\infty}c^{y}=\frac{e^{v+u}}{1-c}\), it has a distance of more than \(v+u\) to the true left boundary. As we need to deal with \(v+u_{1}\) possible patterns from \(S\), with a probability of at most \(P_{2,l}=(v+u_{1})\cdot\frac{e^{v+u}}{1-c}\), \(\mathrm{roughLeft}_{S^{\prime\prime}_{i}}<\mathrm{LB}(S^{\prime\prime}_{i})-(v+u)\). Similarly, with a probability of at most \(P_{2,r}=(v+u_{1})\frac{c^{v+u}}{1-c}\), \(\mathrm{roughRight}_{S^{\prime\prime}_{i}}>\mathrm{RB}(S^{\prime\prime}_{i})+(v+u)\). Let \(P_{2}=P_{2,l}+P_{2,r}\). With a probability of at most \(P_{3,l}=\frac{c^{v}}{1-c}\), \(S^{\prime\prime}_{i}\) does not contain a left half stable motif region by Lemma 20. Similarly, with a probability of at most \(P_{3,r}=\frac{c^{v}}{1-c}\), \(S^{\prime\prime}_{i}\) does not contain a right half stable motif region. Let \(P_{3}=P_{3,l}+P_{3,r}\). Although, \(S\) is involved in searching the left boundary with all other sequences. The non-missing condition is to let each sequence not change too many characters in the motif region. Therefore, this is an independent event for each sequence. It is safe to use the Chernoff bound to deal with it.