## 1 Introduction  
Motifs are patterns found in biological sequences. These common patterns in different sequences help in understanding gene functions, and lead to the design of better drugs to combat diseases. Several versions of the motif search problem have been studied in the literature. In this paper, we consider the version known as the _Planted Motif Search_ (PMS), or \((l,d)\) motif search problem. In PMS, given \(n\) input strings and two integers \(l\) and \(d\), we aim to find all the strings \(M\) of length \(l\) (also referred to as \(l\)-mers) that are substrings of every input sequence (We use the terms sequence and string interchangeably in this paper) with at most \(d\) mismatches. The \(d\)-neighborhood of an \(l\)-mer \(s\) is defined to be the set of all the strings that differ from \(s\) in at most \(d\) positions. So, for an \(l\)-mer \(M\) to be motif for \(n\) input strings, there has to be a substring in each of those \(n\) input strings that is in the \(d\)-neighborhood of \(M\). The PMS problem is known to be NP-hard [2]. Consequently, PMS is often solved by approximation algorithms that do not guarantee to produce every motif present in the input. Exact algorithms for PMS, on the other hand, have exponential worst-case complexity but find every motif. MEME (Multiple EM for Motif Elicitation) [3], which is one of the most popular approximation algorithms for PMS, is based on the expectation minimization technique. MEME outputs the probability that each character is present in each motif and one can take the characters with highest probability in each position to construct the desired motif with an acceptable range of error. GibbsDNA [4] also calculates the same probability matrix of each character in different motif positions using Gibbs sampling. CONSENSUS [5] first aligns the input sequences using statistical measures and then tries to extract the motifs. Randomized algorithms are also proposed for PMS. [PERSON] and [PERSON] [6] proposed an algorithm where they group the input \(l\)-mers based on \(k\) randomly chosen positions out of the total \(l\) positions. With a high probability, many instances of the desired motif belong to the group that has a large number of these \(k\)-mers. Local search strategies such the one proposed by [PERSON] _et al_. [7], which searches \(d\)-neighborhood of some \(l\)-mers from the input, also have been used to find motifs. MULTIPROFILER [8] and ProfileBranching [7] are two algorithms that use local search. Some approximation algorithms for PMS first map the PMS problem to a graph problem and then apply well-studied approximation techniques to solve that graph problem. The WINNOWER algorithm [9], proposed by [PERSON] and [PERSON], constructs a graph in which each node represents an \(l\)-mer and two nodes are connected by an edge iff those two \(l\)-mers differ in at most \(2d\) positions. The problem of finding motifs then reduces to that of finding large cliques in this graph. Although exact algorithms have worst-case exponential complexity, for many small instances of interest they are able to find all motifs within a reasonable amount of time using a modern computer. MITRA [10] is an exact algorithm for PMS that uses a modified trie called Mismatch trie to spell out the motifs one character at a time. SPELLER [11], SMILE [12], RISO [13], and RISOTTO [14] all use some form of suffix tree to direct motif discovery with RISOTTO being the fastest of these. CENSUS [15] first creates a trie with all \(l\)-mers from the input. The trie is then traversed keeping track of the number of mismatches with the currently generated motif in the nodes. Entire branches of the trie can be pruned off if the number of mismatches becomes more than \(d\). Voting algorithms such as [16] use an indicator array of size equal to the number of all possible strings of length \(l\). For each \(l\)-mer in the \(d\)-neighborhood of every \(l\)-mer from the input, the corresponding entry in the array is set.