MEME outputs its results primarily as an HTML file named meme.html. MEME also outputs a machine-readable XML file and a plain-text versions of its results, named meme.xml and meme.txt, respectively.

These files are placed in a directory named meme_out. You can select for the directory to have a different name using the --o or --oc options.

MEME gives each motif it discovers a name, which is a consensus sequence that approximately describes the motif. Motif names are intended to be mnemonic only, and are not intended to be used for searching sequences for matches; use the position-specific probability matrix (PSPM) contained in each of the MEME output file formats for that purpose via programs such as FIMO and MAST.

MEME uses an objective function on motifs to select the "best" motif. The objective function is based on the statistical significance of the log likelihood ratio (LLR) of the occurrences of the motif. The E-value of the motif is an estimate of the number of motifs (with the same width and number of occurrences) that would have equal or higher log likelihood ratio if the input sequences had been generated randomly according to the (0-order portion of the) background model.

MEME searches for the motif with the smallest E-value. It searches over different motif widths, numbers of occurrences, and positions in the input sequences for the motif occurrences. The user may limit the range of motif widths and number of occurrences that MEME tries. In addition, MEME trims the motif (using a dynamic programming multiple alignment) to eliminate any positions where there is a gap in any of the occurrences.

The log likelihood ratio of a motif is llr = log (Pr(sites | motif) / Pr(sites | back)) and is a measure of how different the sites are from the background model. Pr(sites | motif) is the probability of the occurrences given the a model consisting of the position-specific probability matrix (PSPM) of the motif. Pr(sites | back) is the probability of the occurrences given the background model. The background model is an n-order Markov model. By default, it is a 0-order model consisting of the frequencies of the letters in the input sequences. A different 0-order Markov model or higher order Markov models can be specified to MEME using the -bfile option.

The E-value reported by MEME is actually an approximation of the E-value of the log likelihood ratio (an approximation is used because it is far more efficient to compute). The approximation is based on the fact that the log likelihood ratio of a motif is the sum of the log likelihood ratios of each column of the motif. Instead of computing the statistical significance of this sum (its p-value), MEME computes the p-value of each column and then computes the significance of their product. Although not identical to the significance of the log likelihood ratio, this easier to compute objective function works very similarly in practice.

The motif significance is reported as the E-value of the motif. The statistical significance of a motif is computed based on:

1. the log likelihood ratio,
2. the width of the motif,
3. the number of occurrences,
4. the 0-order portion of the background model,
5. the size of the input sequences, and
6. the type of model (oops, zoops, or anr, which determines the number of possible different motifs of the given width and number of occurrences).

MEME searches for motifs by performing Expectation Maximization (EM) on a motif model of a fixed width and using an initial estimate of the number of sites. It then sorts the possible sites according to their probability according to EM. MEME then calculates the E-values of the first n sites in the sorted list for different values of n. This procedure (first EM, followed by computing E-values for different numbers of sites) is repeated with different widths and different initial estimates of the number of sites. MEME outputs the motif with the lowest E-value.

Once a candidate motif has been found the multiple alignment method performs a separate pairwise alignment of the site with the highest probability and each other possible site (the alignment includes width/2 positions on either side of the sites).

The pairwise alignments are then combined and the method determines the widest section of the motif with no insertions or deletions. If this alignment is shorter than min w, it tries to find an alignment allowing up to one insertion/deletion per motif column. This continues (allowing up to 2, 3 ... insertions/deletions per motif column) until an alignment of width at least min w is found.

The switches -nomatrim, -wg, -ws and -noendgaps control trimming of motifs using the multiple alignment method. Specifying the -nomatrim option causes MEME to skip trimming altogether. The -wg and -ws options set the costs of including gaps in the alignments and the -noendgaps allows gaps at the beginning and end to be treated specially.

After trimming, the number of occurrences is then adjusted to maximize the motif E-value, and then the motif width is further shortened to optimize the E-value.

The search for good EM starting points can be improved by using branching search.

Branching search begins with a fixed-sized heap of best EM starts identified during the search of subsequences from the dataset. These starts are also called "seeds". The fixed-sized heap of seeds is used as the "branch_heap" during the first iteration of branching search.

For each iteration of branching search, all seeds in the current branch_heap are considered. All seeds in the ball within hamming distance 1 of a given seed are evaluated and added to a new heap. The ball of new seeds is generated by mutating each character of the initial seed to each alternative character in the alphabet.

After the ball for every branch_heap seed has been evaluated, the seeds in the resulting new heap are added to the heap of best EM starts. The new heap is then used as the branch_heap for the next iteration of branching search.

MEME's run time is cubic with respect to the number of input sequences. Datasets with more than 1000 input sequences in OOPS mode or 1000+ sites in ZOOPS and ANR mode are intractable in terms of run time. For example, on a 3 GHz CPU, initialization of the p-value table takes about 10 min for 1000 sites/sequences in OOPS, about a day for 5000 sites, and about 1 week for 10,000 sites. Then the quadratic run time with respect to the total number of characters kicks in next.

MEME's run time is quadratic with respect to the number of characters. So when the input dataset size doubles, the run time quadruples. If a 30,000 character dataset takes 15 min on a single cpu, a 30,000,000 character dataset would take 1 million times longer (N squared), or roughly 250,000 CPU hours, or 28.5 CPU years.

The parallel version of MEME scales up to about 128 processors. Please see http://www.sdsc.edu/~tbailey/papers/cabios96.pdf for a discussion of the parallel program. You must bear in mind however, that doubling the total number of sequences input to MEME means that you will need 8 times more processors for the job to finish in the same amount of time.

The following examples use data files provided in this release of the MEME Suite (in the tests directory).

1. A simple DNA example:

   meme crp0.s -dna -mod oops -pal

   MEME looks for a single motif in the file crp0.s which contains DNA sequences in FASTA format. The OOPS model is used so MEME assumes that every sequence contains exactly one occurrence of the motif. The palindrome switch is given so the motif model (PSPM) is converted into a palindrome by combining corresponding frequency columns. MEME automatically chooses the best width for the motif in this example since no width was specified.

2. Searching for motifs on both DNA strands:

   meme crp0.s -dna -mod oops -revcomp

   This is like the previous example except that the -revcomp switch tells MEME to consider both DNA strands, and the -pal switch is absent so the palindrome conversion is omitted. When DNA uses both DNA strands, motif occurrences on the two strands may not overlap. That is, any position in the sequence given in the input sequences may be contained in an occurrence of a motif on the positive strand or the negative strand, but not both.

3. A fast DNA example:

   meme crp0.s -dna -mod oops -revcomp -w 20

   This example differs from example 1) in that MEME is told to only consider motifs of width 20. This causes MEME to execute about 10 times faster. The -w switch can also be used with protein datasets if the width of the motifs is known in advance.

4. Using a higher-order background model:

   meme INO_up800.s -dna -mod anr -revcomp -bfile yeast.nc.6.freq

   In this example we use -mod anr and -bfile yeast.nc.6.freq. This specifies that

   1. the motif may have any number of occurrences in each sequence, and,
   2. the Markov model specified in yeast.nc.6.freq is used as the background model. This file contains a fifth-order Markov model for the non-coding regions in the yeast genome.

   Using a higher order background model can often result in more sensitive detection of motifs. This is because the background model more accurately models non-motif sequence, allowing MEME to discriminate against it and find the true motifs.

5. A simple protein example:

   meme lipocalin.s -mod oops -maxw 20 -nmotifs 2

   The -dna switch is absent, so MEME assumes the file lipocalin.s contains protein sequences. MEME searches for two motifs each of width less than or equal to 20. (Specifying -maxw 20 makes MEME run faster since it does not have to consider motifs longer than 20.) Each motif is assumed to occur in each of the sequences because the OOPS model is specified.

6. Another simple protein example:

   meme farntrans5.s -mod anr -maxw 40 -maxsites 50

   MEME searches for a motif of width up to 40 with up to 50 occurrences in the entire set of input sequences. The ANR sequence model is specified, which allows each motif to have any number of occurrences in each sequence. This dataset contains motifs with multiple repeats of motifs in each sequence. This example is fairly time consuming due to the fact that the time required to initialize the motif probability tables is proportional to max width × max sites.

7. A much faster protein example:

   meme farntrans5.s -mod anr -w 10 -maxsites 30 -nmotifs 3

   This time MEME is constrained to search for three motifs of width exactly ten. The effect is to break up the long motif found in the previous example. The -w switch forces motifs to be exactly ten letters wide. This example is much faster because, since only one width is considered, the time to build the motif probability tables is only proportional to max sites.

8. Splitting the sites into three:

   meme farntrans5.s -mod anr -maxw 12 -nsites 24 -nmotifs 3

   This forces each motif to have 24 occurrences, exactly, and be up to 12 letters wide.

9. A larger protein example with E-value cutoff:

   meme adh.s -mod zoops -nmotifs 20 -evt 0.01

   In this example, MEME looks for up to 20 motifs, but stops when a motif is found with E-value greater than 0.01. Motifs with large E-values are likely to be statistical artifacts rather than biologically significant.