## 4 Algorithm Recover-Motif
### Description of Algorithm Recover-Motif
#### 4.2.1. Boundary-Phase of Algorithm Recover-Motif  
The first phase of Algorithm Recover-Motif finds the rough motif boundaries of all input sequences. It first detects the rough motif boundaries of one sequence via comparing two input sequences. Then, the rough boundaries of the first sequence are used to find the rough motif boundaries of other input sequences. Three algorithms share most of the functions. We have a unified approach to describe them. A special variable, \"algorithm-type\", selects one of the three algorithms, respectively. **Definition 12**. : Let algorithm-type represent one of the three algorithm types, \"RANDOMIZED-SUBLINEAR\", \"RANDOMIZED-SUBQUADRATIC\" and \"DETERMINISTIC-SUPERQUADRATIC\". **Definition 13**. : Assume that \(A_{1}\) is a set of positions in a \(\Theta(n,G,\alpha)\) sequence, \(S_{1}\), and \(A_{2}\) is a set of positions in a \(\Theta(n,G,\alpha)\) sequence, \(S_{2}\). If there are positions \(a_{1}\in A_{1}\) and \(a_{2}\in A_{2}\), such that for some position, \(j\), with \(1\leq j\leq|G|\), \(a_{1}\) is the position of \(\aleph(S_{1})[j]\) in \(S_{1}\) and \(a_{2}\) is the position of \(\aleph(S_{2})[j]\) in \(S_{2}\), then \(A_{1}\) and \(A_{2}\) have a _collision_ at \((a_{1},a_{2})\). In the following function, Collision-Detection, the parameter, \(\omega\leq\beta\), is defined below in the three algorithms. \[\omega_{\mbox{algorithm-type}} = \left\{ \begin{array}{ll}0&\mbox{if \ algorithm-type=RANDOMIZED-SUBLINEAR;}\\ \beta&\mbox{if \ algorithm-type=RANDOMIZED-SUBQUADRATIC;}\\ \beta&\mbox{if \ algorithm-type=DETERMINISTIC-SUPERQUADRATIC.}\end{array} \right. \tag{17}\]  
**Collision-Detection\((S_{1},U_{1},S_{2},U_{2})\)**  
**Input:** a pair of \(\Theta(n,G,\alpha)\)-sequences, \(S_{1}\) and \(S_{2}\); \(U_{i}\) is a set of locations in \(S_{i}\) for \(i=1,2\). **Output:** the left and right rough boundaries of two sequences. Let \(D_{1}\) be all subsequences \(S_{1}[a,a+d_{0}\log n-1]\) of \(S_{1}\) of a length of \(d_{0}\log n\) with \(a\in U_{1}\). \(Y_{2}^{\prime}=S_{2}[e_{1}^{\prime},e_{1}^{\prime}+d_{0}\log n-1]\in D_{2}\), such that \(e_{1}^{\prime}\) is the largest and  
\(\mathrm{diff}(Y_{1}^{\prime},Y_{2}^{\prime})\leq\omega_{\mathrm{algorithm-type}}\). Return \((a_{1},a_{1}^{\prime},e_{1},e_{1}^{\prime})\). **End of Collision-Detection. **  
Let \([a,b]\) be an interval with two integers boundaries, \(a\) and \(b\), and \(l\) be a positive integer parameter. Define an \(l\)-partition of \([a,b]\) to be \(l\)-\(P([a,b])\), which contains the intervals \([a_{1},b_{1}],[a_{2},b_{2}],\cdots,[a_{r},b_{r}]\), such that \(a_{1}=a,b_{r}=b,a_{i+1}=b_{i}+1,b_{i}=a_{i}+l-1\) for \(i=1,2,\cdots,r-1\) and \(a_{r}\leq b_{r}\leq a_{i}+l-1\). **Point-Selection\((S,L,I)\)**  
**Input:** a pair of \(\Theta(n,G,\alpha)\)-sequences, \(S\), a size parameter, \(L\), of partition and a set of intervals, \(I\), of positions in \(S\). **Output:** a set, \(U\), of positions from \(S\), respectively. **Steps:**  
Let \(U=\emptyset\). If algorithm-type=RANDOMIZED-SUBLINEAR or RANDOMIZED-SUBQUADRATICand  
if \((L\geq\frac{(\log n)^{3+r}}{100})\):  
for each interval, \(I^{\prime}\), in \(I\), obtain its \(L\)-partition in \(L\)-\(P(I^{\prime})\) and for each interval, \(J\), in \(L\)-\(P(I^{\prime})\),  
sample \(M(L)\) (see Definition 3.2) random positions in \(J\) and put them into \(U\). Else,  
put every position of \(I\) into \(U_{1}\). If algorithm-type=DETERMINISTIC-SUPERQUADRATIC,  
put every position of \(I\) into \(U\). Return \(U\). **End of Point-Selection. **  
The function, **Improve-Boundaries\((S_{1},a_{l},a_{r},S_{2},f_{l},f_{r},L)\)**, is used to improve the existing rough left and right boundaries, \(a_{l}\) and \(a_{r}\), of \(S_{1}\), respectively, and to improve the existing rough left and right boundaries, \(f_{l}\) and \(f_{r}\), of \(S_{2}\), respectively.