## 6 Analysis of the Algorithm
### Analysis of Boundary-Phase of Algorithm Recover-Motif  
Lemma 19 shows that with only a small probability, a sequence can match a random sequence. It will be used to prove that when two substrings in two different \(\Theta(n,G,\alpha)\)-sequences are similar, they are unlikely not to coincide with the motif regions in the two \(\Theta(n,G,\alpha)\)-sequences, respectively. **Lemma 19**. : _Assume that \(X_{1}\) and \(X_{2}\) are two independent sequences of the same length and that every character of \(X_{2}\) is a random character from \(\Sigma\). Then:_  
1. _if_ \(1\leq|X_{1}|=|X_{2}|<v\)_, then the probability that_ \(X_{1}\) _and_ \(X_{2}\) _are matched is_ \(\leq\frac{1}{t^{|X_{1}|}}\) _(_\(t=||\Sigma||\)_); and_
2. _the probability for_ \(\operatorname{diff}(X_{1},X_{2})\leq\beta\) _is at most_ \(e^{-\frac{e^{2}|X_{1}|}{3}}\)_._  
**Proof:** The two statements are proven as follows. Statement i: For every character, \(X_{2}[j]\), with \(1\leq j<v\), the probability is \(\frac{1}{t}\) that \(X_{2}[j]=X_{1}[j]\). Statement ii: For every character, \(X_{2}[j]\), with \(1\leq j\leq|X_{2}|\), the probability is \(\frac{1}{t}\) for \(X_{2}[j]\) to equal \(X_{1}[j]\). If \(\operatorname{diff}(X_{1},X_{2})  
**Lemma 20**. : __  
1. _With a probability of at most_ \(c^{t}\)_, a_ \(\Theta(n,G,\alpha)\) _sequence,_ \(S\)_, changes more than_ \(\frac{\beta}{2}t\) _characters in its motif region,_ \(\aleph(S)[i,i+t-1]\)_, with_ \(1\leq i\leq i+t-1\leq|G|\)_, where_ \(c\) _is defined in item (v) in Definition_ 8_._
2. _With a probability of at most_ \(\frac{c^{\theta}}{1-c^{t}}\)_, a_ \(\Theta(n,G,\alpha)\) _sequence,_ \(S\)_, changes more than_ \(\frac{\beta}{2}t\) _characters in its left motif region,_ \(\aleph(S)[1,t]\)_, for some_ \(t\) _with_ \(y\leq t\leq|G|\)_, where_ \(c\) _is defined in item (v) in Definition_ 8_._  
**Proof:** Statement i: Every character in the \(\aleph(S)\) region has a probability of at most \(\alpha\) to mutate. We know that \(|\aleph(S)|=|G|\geq d\). By Corollary 18, with a probability of at most \(e^{-\frac{c^{2}}{3}t}\), \(\aleph(S)[i,i+t-1]\) has more than \((\alpha+\epsilon)t\) mutations. Statement ii: We know that \(|\aleph(S)|=|G|\geq d\). By Corollary 18, with a probability of at most \(e^{-\frac{c^{2}}{3}t}\), a sequence, \(S\), in \(Z_{1}\) has more than \((\alpha+\epsilon)t\) mutations (recall the setting for \(\beta\) in Definition 9) among the first left \(t\) characters. The total probability is at most \(\sum_{t=y}^{\infty}e^{-\frac{c^{2}}{3}t}=\frac{c^{y}}{1-c}\). Lemma 21 shows that Improve-Boundaries() has a good chance to improve the accuracy of rough motif boundaries. Note that \(\mathrm{LB}(S)\) and \(\mathrm{RB}(S)\) are the left and right motif boundaries of \(S\), respectively (see Definition 11). **Lemma 21**. : _Assume that \(\Theta(n,G,\alpha)\) sequence \(S_{i}\) has \(L_{S_{i}}\in[\mathrm{LB}(S_{i})-L,\mathrm{LB}(S_{i})+L]\) and \(R_{S_{i}}\in[\mathrm{RB}(S_{i})-L,\mathrm{RB}(S_{i})+L]\) for \(i=1,2\). Then, for \((\mathrm{roughLeft}_{S_{1}},\mathrm{roughRight}_{S_{1}},\mathrm{roughLeft}_ {S_{2}},\)\(\mathrm{roughRight}_{S_{2}})\)=Improve-Boundaries\((S_{1},L_{S_{1}},R_{S_{1}},S_{2},L_{S_{2}},R_{S_{2}},L)\), we have the following two facts:_  
1. _with a probability of at most_ \(\frac{2c^{v}}{1-c}+\frac{2(v+u)c^{v+u}}{(1-c)^{2}}+\frac{1}{5\cdot 2^{n}}\)_;_ \(\mathrm{roughLeft}_{S_{i}}\) _is not in_ \([\mathrm{LB}(S_{i})-(v+u),\mathrm{LB}(S_{i})]\) _for_ \(i=1,2\)_._
2. _with a probability of at most_ \(\frac{2c^{v}}{1-c}+\frac{2(v+u)c^{v+u}}{(1-c)^{2}}+\frac{1}{5\cdot 2^{n}}\)_,_ \(\mathrm{roughRight}_{S_{i}}\) _is not in_ \([\mathrm{RB}(S_{i}),\mathrm{RB}(S_{i})+(v+u)]\) _for_ \(i=1,2\)_._
3. _Improve-Boundaries\((S_{1},L_{S_{1}},R_{S_{1}},S_{2},L_{S_{2}},R_{S_{2}},L)\) runs in_ \(O(L^{2}\log n)\) _time._  
**Proof:** We need a bound for the following inequality:  
\[\sum_{i=j}^{\infty}ia^{i}<\frac{ja^{j}}{(1-a)^{2}} \tag{20}\]  
Let \(f(x)=\sum_{i=j}^{\infty}e^{\theta ix}\). Compute the derivative \(f^{\prime}(x)=\theta\sum_{i=j}^{\infty}ie^{\theta ix}\).