## 6 Analysis of the Algorithm
### Analysis of Extract-Phase and Voting-Phase of Algorithm Recover-Motif
_For each_ \(L\) _with_ \(0<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_{2}(n)\)_,_ \(L_{S_{i}^{\prime\prime}}\
ot\in[\mathrm{LB}_{S_{i}^{\prime\prime}}-2L, \mathrm{LB}_{S_{i}^{\prime\prime}}+2L]\) _for_ \(i=1\) _or_ \(i=2\)_, where_ \((L_{S_{1}},R_{S_{1}},L_{S_{i}^{\prime\prime}},R_{S_{i}^{\prime\prime}})=\) _Collision-Detection(_\(S_{1},U_{1},S_{i}^{\prime\prime},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_{i}^{\prime\prime},L,[1,|S_{i}^{\prime\prime}|]\)_)._
3. _The inequality_ \((P_{0}+Q_{0})<c_{0}\) _holds for some constant_ \(c_{0}<1\)_, where_ \(Q_{0}\) _is defined in Equation (_13_) and_ \(P_{0}=\varsigma_{1}(n)+\frac{2(v+u_{1})c^{v+u_{1}}}{(1-c)^{2}}+\frac{c^{v}}{1-c }+\frac{1}{5\cdot 2^{\cdot 2}n}\)_._
4. _The inequality_ \(1-2(Q_{0}+V_{0}+(R+2\epsilon))-(\alpha+\epsilon)>0\) _holds, where_ \(V_{0}=(2(\varsigma_{2}(n)+(v+u_{1})\frac{c^{v+u_{2}}}{1-c}+\frac{c^{v}}{1-c})+\epsilon)\)_._  
_Then, the algorithm generates a set of at most \(k_{2}\) subsequences for voting and votes for a sequence, \(G^{\prime}\), such that:_  
_(1) with a probability of at most \(e^{-\Omega(k_{1})}+e^{-\Omega(k_{2})}\), \(|G^{\prime}|\
eq|G|\); and_  
_(2) for each \(1\leq i\leq|G|\), with a probability of at most \(e^{-\Omega(k_{1})}+e^{-\Omega(k_{2})}\), \(G^{\prime}[i]\
eq G[i]\)._Before proving Lemma 32, we note that both \(\varsigma_{1}(n)\) and \(\varsigma_{2}(n)\) are at most \(\frac{1}{2^{x}n^{3}}\) for all of the three algorithms. They will be proven by Lemma 47 and Lemma 46 for the case algorithm-type=RANDOMIZED-SUBLINEAR, Lemma 41 and Lemma 40 for the case algorithm-type=RANDOMIZED-SUBQUADRATIC, and Lemma 35 for the case algorithm-type=DETERMINISTIC-SUPERQUADRATIC. **Proof:**  
By Lemmas 22, with a probability of at most \(P_{0}=\varsigma_{1}(n)+\frac{2(v+u_{1})e^{v+u_{1}}}{(1-c)^{2}}+\frac{c^{v}}{1- c}+\frac{1}{5^{2^{x}n}}\), \(\mathrm{roughLeft}_{S^{\prime}_{2i-1}}\
ot\in[\mathrm{LB}(S^{\prime}_{2i-1}) -(v+u_{1}),\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})+(v+u_{1})]\). By Lemma 23, with a probability of at most \(P_{a}=e^{-(0.5-P_{0}-\epsilon)^{2}k_{1}/3}=e^{-\Omega(k_{1})}\), the approximate motif length, \(l_{motif}\), is not in the range \([|G|-2(v+u_{1}),|G|+2(v+u_{1})]\). Assume \(l_{motif}\in[|G|-2(v+u_{1}),\)\(|G|+2(v+u_{1})]\) in the rest of the proof of this lemma. By Lemma 27, with a probability of at most \(Q_{0}\), a \(\Theta(n,G,\alpha)\) sequence does not contain a stable motif region. Therefore, with a probability of at most \(P_{1}=(P_{0}+Q_{0})^{k_{1}}\), the following statement is false:  
(i) One of \(S^{\prime}_{2i-1}\) for \(i=1,\cdots,k_{1}\) has \(\mathrm{roughLeft}_{S^{\prime}_{2i-1}}\in[\mathrm{LB}(S^{\prime}_{2i-1})-(v+ u_{1}),\mathrm{LB}(S^{\prime}_{2i-1})]\), \(\mathrm{roughRight}_{S^{\prime}_{2i-1}}\in[\mathrm{RB}(S^{\prime}_{2i-1}), \mathrm{RB}(S^{\prime}_{2i-1})+(v+u_{1})]\) and has a stable motif region. By Lemma 26, with a probability of at most \(P_{2}=e^{-\frac{e^{2}k_{2}}{3}}\), there are more than \((2(\varsigma_{2}(n)+(v+u_{1})\frac{e^{v+u_{2}}}{1-c}+\frac{c^{v}}{1-c})+ \epsilon)k_{2}\) sequences \(S^{\prime\prime}_{i}\) with \(\mathrm{roughLeft}_{S^{\prime\prime}_{i}}\
ot\in[\mathrm{LB}(S^{\prime\prime }_{i})-(v+u_{2}),\mathrm{LB}(S^{\prime\prime}_{i})]\) or \(\mathrm{roughRight}_{S^{\prime\prime}_{i}}\
ot\in[\mathrm{RB}(S^{\prime\prime }_{i}),\mathrm{LB}(S^{\prime\prime}_{i})+(v+u_{2})]\).