We consider a precise version of the motif discovery problem in computational biology as discussed in [1,2]. The planted (l, d) motif problem [2] considered in this paper is described as follows: Suppose there is a fixed but unknown nucleotide sequence M(the motif) of length l. The problem is to determine M, given t sequences with ti being the length of the ith sequence and each containing a planted variant of M. More precisely, each such planted variant is a substring that is M with exactly d point substitutions (see Fig. 1). More details about the complexity of the motif finding problem is given in [3]. A detailed assessment of different motif finding algorithms was published recently in [4].