## 4 Algorithm Recover-Motif
### Description of Algorithm Recover-Motif
#### 4.2.1. Boundary-Phase of Algorithm Recover-Motif
We assume \(a_{l}\in[\mathrm{LB}(S_{1})-L,\mathrm{LB}(S_{1})+L]\), \(a_{r}\in[\mathrm{RB}(S_{1})-L,\mathrm{LB}(S_{1})+L]\), \(f_{l}\in[\mathrm{LB}(S_{2})-L,\mathrm{LB}(S_{2})+L]\) and \(f_{r}\in[\mathrm{RB}(S_{2})-L,\mathrm{RB}(S_{2})+L]\). After calling this function, more accurate approximate boundaries will be derived. From the probabilistic analysis, we have a good chance to get the exact motif boundaries for both \(S_{1}\) and \(S_{2}\). See the examples in Section 3.2.7..  
**Improve-Boundaries\((S_{1},a_{l},a_{r},S_{2},f_{l},f_{r},L)\)**  
**Input:** a \(\Theta(n,G,\alpha)\)-sequence, \(S_{1}\), with rough left and right boundaries, \(a_{l}\) and \(a_{r}\), a \(\Theta(n,G,\alpha)\)-sequences, \(S_{2}\) with rough left and right boundaries, \(f_{l}\) and \(f_{r}\), and an approximate distance, \(L\), to the nearest motif boundary from those rough boundaries (the parameter, \(L\), usually has the properties of \(\mathrm{LB}(S_{1})\in[a_{l}-L,a_{l}]\), \(\mathrm{RB}(S_{1})\in[a_{r},a_{r}+L]\), \(\mathrm{LB}(S_{2})\in[f_{l}-L,f_{l}]\) and \(\mathrm{RB}(S_{2})\in[f_{r},f_{r}+L]\)). **Output:** improved rough left and right boundaries for both \(S_{1}\) and \(S_{2}\). **Steps:**  
Find two subsequences, \(X_{1}=S_{1}[a_{1},a_{1}+d_{0}\log n-1]\) and \(X_{2}=S_{2}[b_{2},b_{2}+d_{0}\log n-1]\), with \(a_{1}\in[a_{l}-L,a_{l}+L]\) and \(b_{2}\in[f_{l}-L,f_{l}+L]\), such that \(\mathrm{diff}(X_{1},X_{2})\leq\beta\) and \(a_{1}\) is the least. Find two subsequences, \(X_{1}^{\prime}=S_{1}[a_{1}^{\prime},a_{1}^{\prime}+d_{0}\log n-1]\) and \(X_{2}^{\prime}=S_{2}[b_{2}^{\prime},b_{2}^{\prime}+d_{0}\log n-1]\), with \(a_{1}^{\prime}\in[a_{r}-L,a_{r}+L]\) and \(b_{2}\in[f_{r}-L,f_{r}+L]\), such that \(\mathrm{diff}(X_{1}^{\prime},X_{2}^{\prime})\leq\beta\) and \(a_{1}^{\prime}\) is the largest. Find two subsequences, \(Y_{1}=S_{1}[e_{1},e_{1}+d_{0}\log n-1]\) and \(Y_{2}=S_{2}[f_{2},f_{2}+d_{0}\log n-1]\), with \(e_{1}\in[a_{l}-L,a_{l}+L]\) and \(f_{2}\in[f_{l}-L,f_{l}+L]\), such that \(\mathrm{diff}(Y_{1},Y_{2})\leq\beta\) and \(f_{2}\) is the least. Find two subsequences, \(Y_{1}^{\prime}=S_{1}[e_{1}^{\prime},e_{1}^{\prime}+d_{0}\log n-1]\) and \(Y_{2}^{\prime}=S_{2}[f_{2}^{\prime},f_{2}^{\prime}+d_{0}\log n-1]\), with \(e_{1}^{\prime}\in[a_{r}-L,a_{r}+L]\) and \(f_{2}^{\prime}\in[f_{r}-L,f_{r}+L]\), such that \(\mathrm{diff}(Y_{1}^{\prime},Y_{2}^{\prime})\leq\beta\) and \(f_{2}^{\prime}\) is the largest. Return \((a_{1},a_{1}^{\prime},f_{2},f_{2}^{\prime})\). **End of Improve-Boundaries. **  
The function, **Initial-Boundaries\((S_{1},S_{2})\)**, detects the motif boundaries for two sequences, \(S_{1}\) and \(S_{2}\). It first detects rough motif boundaries that are controlled by parameter \(L\). The rough boundaries will be improved to exact motif boundaries via calling **Improve-Boundaries\((.)\)**. See the examples in Sections 3.2.2. -3.2.8..  
**Initial-Boundaries\((S_{1},S_{2})\)**  
**Input:** a pair of \(\Theta(n,G,\alpha)\)-sequences, \(S_{1}\) and \(S_{2}\). **Output:** rough left boundary \(\mathrm{roughLeft}_{S_{1}}\) of \(S_{1}\), right boundary \(\mathrm{roughRight}_{S_{1}}\) of \(S_{1}\), rough left boundary \(\mathrm{roughLeft}_{S_{2}}\) of \(S_{2}\) and right boundary \(\mathrm{roughRight}_{S_{2}}\) of \(S_{2}\). **Steps:**  
Let \(U_{1}=U_{2}=\emptyset\). Let \(L=n^{2/5}\). Repeat. Let \(U_{1}=\)Point-Selection\((S_{1},L,[1,|S_{1}|])\). Let \(U_{2}=\)Point-Selection\((S_{2},L,[1,|S_{2}|])\). Let \((L_{S_{1}},R_{S_{1}},L_{S_{2}},R_{S_{2}})=\)Collision-Detection\((S_{1},U_{1},S_{2},U_{2})\). If (\(L_{S_{1}}\
eq\emptyset\) and \(R_{S_{1}}\
eq\emptyset\)),  
then go to H.  
Else, \(L=L/2\),  
until \((L<\frac{1}{2}\frac{(\log n)^{3+r}}{100})\). H: Return Improve-Boundaries\((S_{1},L_{S_{1}},R_{S_{1}},S_{2},L_{S_{2}},R_{S_{2}},2L)\). **End of Initial-Boundaries. **  
If \(L_{S}\) and \(R_{S}\) are the left and right motif boundaries of a sequence, \(S\), then the motif length is \(R_{S}-L_{S}+1\).