## 1 Introduction  
Motif discovery is an important problem in computational biology and computer science. For instance, it has applications in coding theory [1, 2], locating binding sites and conserved regions in unaligned sequences [3; 4; 5; 6], genetic drug target identification [7], designing genetic probes [7] and universal PCR primer design [7; 8; 9; 10]. This paper focuses on the application of motif discovery to find conserved regions in a set of given DNA, RNA or protein sequences. Such conserved regions may represent common biological functions or structures. Many performance measures have been proposed for motif discovery. Let \(C\) be a subset of \(0\)-\(1\) sequences of length \(n\). The _covering radius_ of \(C\) is the smallest integer, \(r\), such that each vector in \(\{0,1\}^{n}\) is at a distance at most \(r\) from a string in \(C\). The decision problem associated with the covering radius for a set of binary sequences is NP-complete [1]. The similar closest string and substring problems were proven to be NP-hard [1; 7]. Some approximation algorithms have been proposed. [PERSON] _et al._[11] gave an approximation scheme for the closest string and substring problems. The related consensus patterns problem is that given \(n\) sequences \(s_{1},\cdots,s_{n}\), find a region of length \(L\) in each \(s_{i}\) and a string, \(s\), of length \(L\), so that the total Hamming distance from \(s\) to these regions is minimized. Approximation algorithms for the consensus patterns problem were reported in [12]. Furthermore, a number of heuristics and programs have been developed [13; 14; 15; 16; 17]. In many applications, motifs are faint and may not be apparent when two sequences alone are compared, but may become clearer when more sequences are compared together [18]. For this reason, it has been conjectured that comparing more sequences together can help with identifying faint motifs. This paper is a theoretical approach with a rigorous probabilistic analysis. We study a natural probabilistic model for motif discovery. In this model, there are \(k\) background sequences, and each character in the background sequence is a random character from an alphabet, \(\Sigma\). A motif \(G=g_{1}g_{2}\ldots g_{m}\) is a string of \(m\) characters. In each background sequence is implanted a probabilistically-generated approximate copy of \(G\). For a probabilistically-generated approximate copy \(b_{1}b_{2}\ldots b_{m}\) of \(G\), every character, \(b_{i}\), is probabilistically generated, such that the probability for \(b_{i}\
eq g_{i}\), which is called a _mutation_, is at most \(\alpha\). This model was first proposed in [13] and has been widely used in experimentally testing motif discovery programs [14; 15; 16; 17]. We note that a mutation in our model converts a character, \(g_{i}\), in the motif into a different character, \(b_{i}\), without probability restriction. This means that a character, \(g_{i}\), in the motif may not become any character \(b_{i}\) in \(\Sigma-\{g_{i}\}\) with equal probability. We develop three algorithms for which, under the probabilistic model, one can find the implanted motif with high probability via a tradeoff between computational time and the probability of mutation. Each algorithm has a preprocessing phase and the voting phase. We use a pair of functions, \((t_{1}(n,k),t_{2}(n,k))\), to describe the computational complexity of the motif detection algorithm, where \(n\) is the largest length of the input sequence and \(k\) is the number of sequences. Function \(t_{1}(n,k)\) is the time complexity for the part for preprocessing, and \(t_{2}(n,k)\) is the time complexity for recovering one character for the motif after preprocessing. The total time is \(O(t_{1}(n,k)+t_{2}(n,k)|G|)\).