Article Preview
TopIntroduction
De novo motif finding is crucial to understanding and controlling the regulatory cell processes. Motifs are short (between 6-22 base pairs) putative nucleotide sequences presumed to represent the sites where transcription factors (TF) and other regulatory proteins bind to DNA (D’haeseleer, 2006).
The problem of finding DNA motifs is NP-complete (Pevzner & Sze, 2000). The input is represented by a collection of nucleotide sequences in which one must find overrepresented unknown patterns of unknown lengths. The motifs are complex entities because they can be found on both strands of the DNA (i.e. the patterns can be complementary) and can also present mismatches (mutations). If a motif of length 
is sought (i.e. a w-mer) in 
sequences, each of size 
, then, without considering possible mutations, there are 
candidate solutions.
Motifs are represented using profile matrices or the IUPAC consensus notation. Profile matrices, also known as positional weight matrices (PWM), are the most commonly used approach and they contain the log-likelihoods of the site-specific frequency of nucleotides against a baseline pre-set background model. These matrices are used to calculate several metrics that can show how far a candidate motif is from a random sequence (Xia, 2012). Moreover, they may be utilized to generate visual representations of motifs as sequence logos, as described by Schneider and Stephens (1990).
Algorithms for motif finding that represent motifs with PWMs are called profile-based methods, while those that represent motifs using consensuses are known as word-based algorithms (Das & Dai, 2007; Zambelli, Pesole, & Pavesi, 2013).
The profile-based algorithms are search heuristics that iteratively improve an initial PWM. Examples include, but are not limited to: multiple expectation maximization for motif elicitation (MEME) by Bailey, Williams, Misleh, & Li (2006); the Gibbs Sampler by Hon and Jain (2006), and Lawrence et al. (1993) and also AlignACE by Hughes, Estep, Tavazoie, and Church (2000).
The word-based algorithms are enumeration methods that search through the space of 
candidate solutions. They scan the input sequences for motifs that match up to 
mutations. Examples include the algorithm Weeder (Pavesi, Mauri, & Pesole, 2001), the discriminative regular expression motif elicitation algorithm (DREME) (Bailey, 2011) and the oligo-analysis (van Helden, André, & Collado-Vides, 1998).
Typically, the output of de novo motif finding methods consists of a list of motifs found (presented in the PWM or the consensus format) ranked according to their significance value.