## 4 Algorithm Recover-Motif
### Description of Algorithm Recover-Motif
#### 4.2.2.  
Extract-Phase of Algorithm Recover-Motif  
After a set of motif candidates, \(W\), is produced from Boundary-Phase of algorithm Recover-Motif, we use this set to match with another set of input sequences to recover the hidden motif by voting.  
**Match\((G_{l},G_{r},S^{\prime\prime}_{i})\)**  
**Input:** a motif left part, \(G_{l}\) (which can be derived from the rough left boundary of an input sequence, \(S\)), a motif right part, \(G_{r}\), and a sequence, \(S^{\prime\prime}_{i}\), from the group, \(Z_{2}\), with known rough left and right boundaries.  
**Output:** either a rough motif region of \(S^{\prime\prime}_{i}\) or an empty sequence, which means the failure in extracting the motif region, \(\aleph(S^{\prime\prime}_{i})\), of \(S^{\prime\prime}_{i}\).  
**Steps:**  
Find a position, \(a\), in \(S^{\prime\prime}_{i}\) with \(\mathrm{roughLeft}_{S^{\prime\prime}_{i}}\leq a\leq\mathrm{roughLeft}_{S^{ \prime\prime}_{i}}+(v+u_{2})\),  
such that \(G_{l}\) and \(S^{\prime\prime}_{i}[a,a+|G_{l}|-1]\) are left matched (see Definition 9).  
Find a position, \(b\), in \(S^{\prime\prime}_{i}\) with \(\mathrm{roughRight}_{S^{\prime\prime}_{i}}-(v+u_{2})\leq b\leq\mathrm{rough Right}_{S^{\prime\prime}_{i}}\),  
such that \(G_{r}\) and \(S^{\prime\prime}_{i}[b-|G_{r}|+1,b]\) are right matched (see Definition 9).  
If both \(a\) and \(b\) are found,  
then output \(S^{\prime\prime}_{i}[a,b]\).  
Else, output \(\emptyset\) (empty string).  
**End of Match.**  
If the left, \(G_{l}\), and right, \(G_{r}\), motif parts are known, we extract all the motif regions for all sequences in the set, \(Z_{2}\), by the function, **Extract\((G_{l},G_{r},Z_{2}\))**.  
**Extract\((G_{l},G_{r},Z_{2}\))**  
Input \(Z_{2}=\{S^{\prime\prime}_{1},S^{\prime\prime}_{2},\cdots,S^{\prime\prime}_{k_{ 2}}\}\) and left and right motif parts, \(G_{l}\) and \(G_{r}\) (see function **Match\((G_{l},G_{r},S_{i})\)**).  
**Steps:**  
For each \(S_{i}^{\prime\prime}\) with \(i=1,2,\cdots,k_{2}\),  
let \(G_{i}^{\prime\prime}=\mathrm{Match}(G_{l},G_{r},S_{i}^{\prime\prime})\).  
Return \((G_{1}^{\prime\prime},G_{2}^{\prime\prime},\cdots,G_{k_{2}}^{\prime\prime})\).  
**End of Extract.**  
The following is Extract-Phase of algorithm Recover-Motif. It extracts the motif regions of another set, \(Z_{2}\), of input sequences. The function is based on the condition that exact motif boundaries can be derived for most sequences. See the examples in Section 3.2.9..  
**Extract-Phase(\(S^{\prime},Z_{2}\)):**  
Input \(S^{\prime}\) is an input sequence with known \(\mathrm{roughLeft}_{S^{\prime}}\) and \(\mathrm{roughRight}_{S^{\prime}}\) for its rough left and right boundaries, respectively, and \(Z_{2}=\{S_{1}^{\prime\prime},\cdots,S_{k_{2}}^{\prime\prime}\}\) is a set of input sequences.  
**Steps:**  
For each subsequence \(G_{l}=S^{\prime}[a,a+d_{0}\log n-1]\) with \(a\in[\mathrm{roughLeft}_{S^{\prime}},\mathrm{roughLeft}_{S^{\prime}}+(v+u_ {1})]\) and \(G_{r}=S^{\prime}[b-d_{0}\log n+1,b]\), with \(b\in[\mathrm{roughRight}_{S^{\prime}}-(v+u_{1}),\mathrm{roughRight}_{S^{ \prime}}]\),  
let \((G_{1}^{\prime\prime},G_{2}^{\prime\prime},\cdots,G_{k_{2}}^{\prime\prime})\) be the output from Extract\((G_{l},G_{r},Z_{2})\).  
If the number of empty sequences in \(G_{1}^{\prime\prime},\cdots,G_{k_{2}}^{\prime\prime}\) is at most \((Q_{0}+(R+2\epsilon))k_{2}\),  
then return \((G_{1}^{\prime\prime},G_{2}^{\prime\prime},\cdots,G_{k_{2}}^{\prime\prime})\).  
Return \(\emptyset\) (empty set).  
**End of Extract-Phase.**