## 5 Deterministic Algorithm  
In this section, we give a deterministic algorithm, which is a simplified version of the unified algorithm described before in Section 4.2. It is simpler than the randomized versions. 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. We still let:  
\[\omega\textsc{Deterministic-superquadratic}=\beta. \tag{19}\]  
**Collision-Detection\((S_{1},S_{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[1,|S_{1}|]\). Let \(D_{2}\) be all subsequences, \(S_{2}[b,b+d_{0}\log n-1]\), of \(S_{2}\) of a length of \(d_{0}\log n\) with \(b\in[1,|S_{2}|]\). Find two subsequences, \(X_{1}=S_{1}[a_{1},a_{1}+d_{0}\log n-1]\in D_{1}\) and \(X_{2}=S_{2}[b_{1},b_{1}+d_{0}\log n-1]\in D_{2}\), such that \(a_{1}\) is the least and \(\mathrm{diff}(X_{1},X_{2})\leq\omega_{\textsc{Deteterministic-superquadratic}}\). Find two subsequences, \(X_{1}^{\prime}=S_{1}[a_{1}^{\prime},a_{1}^{\prime}+d_{0}\log n-1]\in D_{1}\) and \(X_{2}^{\prime}=S_{2}[b_{1}^{\prime},b_{1}^{\prime}+d_{0}\log n-1]\in D_{2}\), such that \(a_{1}^{\prime}\) is the largest and \(\mathrm{diff}(X_{1}^{\prime},X_{2}^{\prime})\leq\omega_{\textsc{Deteterministic-superquadratic}}\). Find two subsequences, \(Y_{1}=S_{1}[f_{1},f_{1}+d_{0}\log n-1]\in D_{1}\) and \(Y_{2}=S_{2}[e_{1},e_{1}+d_{0}\log n-1]\in D_{2}\), such that \(e_{1}\) is the least and \(\mathrm{diff}(Y_{1},Y_{2})\leq\omega_{\textsc{Deteterministic-superquadratic}}\). Find two subsequences, \(Y_{1}^{\prime}=S_{1}[f_{1}^{\prime},f_{1}^{\prime}+d_{0}\log n-1]\in D_{1}\) and \(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_{\textsc{Deteterministic-superquadratic}}\). Return \((a_{1},a_{1}^{\prime},e_{1},e_{1}^{\prime})\). **End of Collision-Detection. **  
Function **Point-Selection\((S_{1},S_{2},L)\)** is not used in the deterministic algorithm. **Improve-Boundaries\((S_{1},a_{l},a_{r},S_{2},f_{l},f_{r},L)\)** is the same as that in the randomized algorithms. **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 \((L_{S_{1}},R_{S_{1}},L_{S_{2}},R_{S_{2}})=\)Collision-Detection\((S_{1},S_{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+\tau}}{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. **  
**Motif-Length-And-Boundaries(\(Z_{1}\))** is the same as that before. **Match\((G_{l},G_{r},S_{i})\)** is the same as that for the randomized algorithm. **Extract\((G_{l},G_{r},Z_{2}\))** is the same as that for the randomized algorithm. The following is Extract-Phase of algorithm Recover-Motif. It extracts the motif regions of another set, \(Z_{2}\), of input sequences. **Extract-Phase(\(S^{\prime},Z_{2}\))** is the same as that for the randomized algorithm. **Voting-Phase\((G_{1}^{\prime\prime},G_{2}^{\prime\prime},\cdots,G_{k_{2}}^{\prime\prime})\)** is the same as that for the randomized algorithm.