# How does MEME compute the background frequency of nucleotides?

I am trying to calculate a log-odds matrix for MAST input, from a position-specific probability matrix for the motif in which I am interested.

I would like to know how MEME estimates the background frequency of nucleotides, as it does the conversion from position-specific probability matrices to log-odds matrices when you choose to run MAST on MEME output. Is it simply counting frequencies in the sequences supplied, or is there some sort of modeling going on to correct for sample size and whatnot?

EDIT: Another possibility that occurred to me is that MAST is capable of converting position-specific matrices to log-odds matrices. I'd appreciate it if someone could clarify this point for me (and I'm still interested in how the background frequencies are calculated). Also, I am specifically looking for answers with links to supporting documentation.

EDIT 2 (05/07/13): Alexander has answered the original question. Does anyone have an answer to the first edit (re: MAST)?

EDIT 3: MAST doesn't like PSPMs; it will accept the job but crash.

-
I am not sure about the exact algorithm but the wikipedia page on MEME, briefly explains the algorithm and how the weights are computed. You can refer to the original paper; they must have explained it in the supplementary info. – WYSIWYG May 6 '13 at 9:14

At the MEME server page, there's a link to upload a customized background markov model (using the command line interface, this is the -bfile option). From there, there's a link to the MEME Man Page. Under "Objective Function", it specifies:

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 training set.

So yes, it's basically the simplest possible correction: no accounting for pairwise frequencies, complements, motif width, etc. I expect this is because MEME can be applied to essentially any dataset, such as phage display bindings from a "truly" random set of short oligos. In which case making higher order assumptions about the pairwise independence would be detrimental.

Below that, I think it answers your question about the total log-odds calculation:

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.

-
Thank you for the clarification re: MEME. Do you know if MAST also does the same computation? I know it works with log-odds matrices, but I am interested in whether it also can accept position-specific matrices. – dd3 May 6 '13 at 20:15
In the couple of instances that I've used MEME, I found it sorely lacking in documentation. It seemed to make the assumption that the user was already pretty expertly trained in the field. My impression is that it should be able to handle a pretty sophisticated Markov model, but I don't know how you would construct it. I tend to work at the opposite end of the comp bio spectrum. :) – Alexander D. Scouras May 11 '13 at 9:44