## 4 Algorithm Recover-Motif
### Some Parameters  
**Definition 8**. :
1. Parameter \(x\) is selected to be \(10\). This parameter controls the failure probability of our algorithms to be at most \(\frac{1}{2^{x}}\). 2. The size of the alphabet is \(t\geq 4\). 3. Select a constant \(\rho_{0}\in(0,1)\) to have inequality (1): \[\rho_{0}<\frac{t-1}{2t}\] (1)
4. The constant \(\epsilon\in(0,1)\) is selected to satisfy: \[\epsilon<\min((\frac{t-1}{t}-(2\rho_{0}+2\epsilon)),\ \ \frac{1}{5}(1-\frac{2}{t-1}-\frac{4}{2^{x}}),\ \ \frac{1}{3})\] (2) The existence of \(\epsilon\) follows from inequality (1). The constant \(\epsilon\) is used to control the mutation in the motif area. It is a part of parameter \(\beta\) defined in item (xiv) of this definition. 5. Let \(c=e^{-\frac{c^{2}}{3}}\). The constant, \(c\), is used to simplify probabilistic bounds, which are derived from the applications of Chernoff bounds (see Corollary 18). 6. Define \(r(y)=(\frac{1}{t-1}+\frac{c^{y}}{1-c})\). 7. Define \(u_{1}\) to be a large constant that, for all \(v\geq 0\): \[\frac{2(v+u_{1})c^{v+u_{1}}}{(1-c)^{2}}\leq\frac{1}{5\cdot 2^{x}}\] (3)
8. Select constant \(\rho_{1}\in(0,1)\), such that: \[\frac{2}{t-1}+\frac{4}{2^{x}}+5\epsilon+\rho_{1}<1\] (4) The existence of \(\rho_{1}\) follows from \(\epsilon<\frac{1}{5}(1-\frac{2}{t-1}-\frac{4}{2^{x}})\), which is implied by inequality (2). * Select constant \(\rho_{2}\in(0,1)\) and constant positive integer \(v\) that are large enough, such that: \[\frac{6(v+u_{1})c^{v}}{1-c}+\rho_{2}<\rho_{1},\ \ \mathrm{and}\] (5) \[(\frac{1}{2^{x}}+(v+u_{1})\frac{c^{v}}{1-c}+\frac{c^{v}}{1-c}+ \frac{1}{5\cdot 2^{x}})\leq 1/2\] (6)
* Define \(\varsigma_{0}=\frac{1}{2^{x}}\), and: \(\varphi(v)=(v+u_{1})\frac{c^{v}}{1-c}+\frac{c^{v}}{1-c})\)
* Select constant \(\alpha_{0}\), such that: \[4(v-1)\alpha_{0}+\alpha_{0} < \rho_{2},\ \ \mathrm{and}\] (7) \[\alpha_{0} < \rho_{0}\] (8) Adding inequalities (4), (5) and (7), we have inequality (9): \[(\frac{2}{t-1}+\frac{4}{2^{x}}+5\epsilon)+\frac{6(v+u_{1})c^{v}}{1-c}+(4(v-1) \alpha_{0}+\alpha_{0})<1\] (9) By arranging the terms in inequality (9) and the definitions of \(r(v)\) and \(\varphi(v)\), we have inequality (10): \[2((2(v-1)\alpha_{0}+\frac{c^{v}}{1-c})+r(v)+2(\varsigma_{0}+\varphi(v))+2 \epsilon)+(\alpha_{0}+\epsilon)<1\] (10)
* The maximal mutation rate, \(\alpha\), for the second algorithm (Theorem 4) and the third algorithm (Theorem 6) are selected as \(\alpha_{0}\). Since the mutation rate of our sublinear time algorithm is bounded by \(\frac{1}{(\log n)^{2+\mu}}\), the maximal mutation rate \(\alpha\) for the first algorithm (Theorem 2) is less than \(\alpha_{0}\) when \(n\) is large enough. We always assume that all mutation rates \(\alpha\) in our three algorithms are in the range \((0,\alpha_{0}]\). * Define \(q(y)=2(v-1)\alpha+\frac{2c^{y}}{1-c}\). By inequality (10), the definition of \(q(y)\) and the fact that \(\alpha\in(0,\alpha_{0})\), we have: \[\epsilon<\min((\frac{t-1}{t}-(2\rho_{0}+2\epsilon)),\ \ \frac{1}{5}(1-\frac{2}{t-1}-\frac{4}{2^{x}}),\ \ \frac{1}{3})\]0 (11) Inequality (11) implies \(q(v)\leq\frac{1}{2}\). By inequality (6), we have that: \[\epsilon<\min((\frac{t-1}{t}-(2\rho_{0}+2\epsilon)),\ \ \frac{1}{5}(1-\frac{2}{t-1}-\frac{4}{2^{x}}),\ \ \frac{1}{3})\]1 (12)
* Let \(\beta=2\alpha+2\epsilon\). The parameter, \(\beta\), controls the similarity of \(\aleph(S)\) and the original motif, \(G\) (see Lemma 27). * Define \(R=r(v)\). * We define the following \(Q_{0}\). \[\epsilon<\min((\frac{t-1}{t}-(2\rho_{0}+2\epsilon)),\ \ \frac{1}{5}(1-\frac{2}{t-1}-\frac{4}{2^{x}}),\ \ \frac{1}{3})\]2 (13) The parameter, \(Q_{0}\), used in Lemma 27 gives an upper bound of the probability that a \(\Theta(n,G,\alpha)\)-sequence, \(S\), whose \(\aleph(S)\) will not be similar enough to the original motif, \(G\), according to the conditions in Lemma 27.