## 6 Analysis of the Algorithm
### Deterministic Algorithm for an \(\Omega(1)\) Mutation Rate  
In this section, we give a deterministic algorithm for the case with an \(\Omega(1)\) mutation rate. The performance of the algorithm is stated in Theorem 6. **Lemma 35**: _Let algorithm-type=DETERMINISTIC-SUPERQUADRATIC. Assume that \(d_{0}\log n\leq L\leq|G|/2\) and \(c_{0}\log n\leq|G|\). Let \(I_{1}\) be a set of intervals of the positions of \(S_{1}\) that satisfies \([\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 satisfies \([\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^{2}n^{3}}\)_, the left rough boundary,_ \(L_{S_{1}}\)_, has at most_ \(d_{0}\log n\) _distance from_ \(\mathrm{LB}(S_{1})\) _and the left rough boundary_ \(L_{S_{2}}\) _has at most_ \(d_{0}\log n\) _distance from_ \(\mathrm{LB}(S_{2})\)_._
* _with a probability of at most_ \(\frac{1}{2^{2}n^{3}}\)_, the right rough boundary,_ \(R_{S_{1}}\)_, has at most_ \(d_{0}\log n\) _distance from_ \(\mathrm{RB}(S_{1})\) _and the right boundary of_ \(R_{S_{2}}\) _has at most_ \(d_{0}\log n\) _distance from_ \(\mathrm{RB}(S_{2})\)_._  
**Proof:** For two sequences, \(S_{1}\) and \(S_{2}\), let \(\aleph(S_{a})\) be the subsequence, \(S_{a}[i_{a},j_{a}]\), for \(a=1,2\). By Corollary 18, with a probability of at most \(P_{l}=2c^{d_{0}\log n}\leq\frac{2}{5\cdot 2^{2}n^{3}}\) (see inequality (8) in Definition 14), there are more than \((\alpha+\epsilon)d_{0}\log n\) mutations in \(S_{a}[i_{a},i_{a}+d_{0}\log n-1]\) for \(a=1,2\). With a probability of at most \(P_{l}\), the left boundary position is missed during the matching. We have similar \(P_{r}=P_{l}\) to miss the right boundary. Assume that \(p_{1}\) and \(p_{2}\) are two positions of \(S_{1}\) and \(S_{2}\), respectively. If one of two positions is outside the motif region and has more than \(d_{0}\log n\) distance to the motif boundary, with a probability of at most \(c^{-d_{0}\log n}\leq\frac{1}{5\cdot 2^{2}n^{3}}\) (see inequality (8) in Definition 14), for them to match requires \(\mathrm{diff}(Y_{1},Y_{2})\leq\beta\) by Lemma 19, where \(Y_{a}\) is a subsequence \(S_{a}[p_{a},p_{a}+d_{0}\log n-1]\) for \(a=1,2\). **Lemma 36**: _For the case algorithm-type=DETERMINISTIC-SUPERQUADRATIC, we have:_  
* _Collision-Detection(_\(S_{1},U_{1},S_{2},U_{2}\)_) takes_ \(t(n,||U_{1}||+||U_{2}||)=O((||U_{1}||+||U_{2}||)^{2}\log n)\) _time._
* _Point-Selection(_\(S_{1},L,[1,|S_{1}|]\)_) selects_ \(s(n,L)=O(n)\) _positions in_ \(g(n,L)=O(n)\) _time._
* \(||U_{S^{\prime}_{2i-1}}||+||U_{S^{\prime\prime}_{j}}||\) _in the algorithm Recover-Motif is no more than_ \(f(n,|G|)=O(|G|+n)\)_._
* _With a probability of at most_ \(\frac{k}{2^{2}n^{3}}\)_, the algorithm Recover-Motif does not run in computational complexity_ \((O(k(n^{2}(\log n)^{O(1)}+h^{2}\log n)),O(k))\)  
**Proof:** Statement i. The parameter, \(\omega_{\textsc{DETerministic-superquadradratic}}\), is set to be \(\beta\) in Collision-Detection. It follows from the time complexity of the brute force method. Statement ii. It follows from the implementation of Point-Selection(). Statement iii. It follows from the choice of Point-Selection(.) for the sublinear time algorithm at Recover-Motif(.). Statement iv. It follows from Lemma 34 and Statements i, ii and iii. We give the proof for Theorem 6. **Proof:** [Theorem 6] The computational time part of this theorem follows from Lemma 36. By Lemma 35, we let \(\varsigma_{1}(n)=\frac{1}{2^{s}n^{3}}\leq\varsigma_{0}\) for the probability bound, \(\varsigma_{1}(n)\), in the condition (i) of Lemma 32.