Introduction to Motifs and Motif Finding

Biologically speaking, a motif in DNA or RNA (or protein) sequence is a short functional sequence element.

Examples found in genomic DNA include

We will be strongly tempted to talk about conserved DNA sequence motifs. But we must be careful to recognize that many motifs, especially short transcription factor binding sites, are known to arise convergently. Hence, the various instances of a motif, while similar in appearance, may not actually be homologs. Don’t say "conserved" unless you mean it!

A motif is a short sequence element that is repeated, perhaps with variation, multiple times in a collection of sequences.

Typical motif lengths are five to a few tens of bases.

What does "repeated with variation" mean? We need to define this idea more precisely in order to build motif-finding algorithms.

Given a putative motif, we would like to reject the null hypothesis that it is just a bunch of unrelated sequences.

More precisely, we typically assume a background model for sequences that are not part of the motif, and we want to reject the hypothesis that the putative motif’s sequences are unrelated samples from this background.

Intuitively, a putative motif whose instances display less variation should be more interesting, since the instances are more similar than would be expected for unrelated sequences drawn from the background.

Often, the background is assumed to consist of i.i.d. (independent and identically distributed) random DNA bases, with each base chosen according to some fixed multinomial distribution.

We will sketch quantitative measures of interest for motifs, but how to turn these measures into \(p\)-values is beyond the scope of this talk. Different programs use different approaches.

Let \(C\) be a "Platonic ideal" sequence of the motif. For example, for a transcription factor binding site, \(C\) might be the sequence that most strongly binds its target protein domain.

Every instance of the motif is assumed to be a variant of \(C\). Instances might deviate from \(C\) by some number of differences (substitutions, insertions, and/or deletions).

For example, if \(C\) is "agtagc", the actual instances of the motif might be, e.g., "agcagc", "attac", and "agtggc".

We call \(C\) the motif’s consensus sequence.

A putative motif instance can be aligned to \(C\) using the Smith-Waterman algorithm to determine how many differences separate it from \(C\).

To infer a model \(C\) from a collection of instances, we (multiple-) align them and then let each position of the aligned sequences "vote" on what base should be given in the consensus.

We can describe degenerate consensus positions using IUPAC ambiguity symbols. For example, "R" represents a purine (a or g).

Inferring \(C\) is trivial if motif instances can differ from it only by substitution. If they can have insertions and deletions, finding the "best" \(C\) is computationally hard but can be approximated.

One useful measure of interest for a motif in the consensus model is the radius: if we align all instances of the motif against its consensus \(C\), the motif’s radius is the smallest \(r\) such that every instance differs from \(C\) by at most \(r\) differences.

We also need to know the proposed motif’s length to measure interest, since 2 differences in 5 is a lot less interesting than 2 differences in 20.

Finally, we need to know how many instances exist. A motif with 100 close instances in a given amount of sequence is a lot more interesting than one with just 3.

To turn this multi-part measure of interest into a \(p\)-value, a program must compute the chance that a set of putative motif instances would all arise independently by chance in a given amount of background sequence.

Not every position of a motif may be equally variable. For example, eukaryotic splice donor sites have an almost invariant "gt" at the intron boundary, but the surrounding sequence, while not invariant, exhibits more similarity across splice sites than would be expected by chance.

Not all differences from the consensus may be equally likely. IUPAC ambiguity symbols cannot capture an arbitrary set of base frequencies in a particular position.

A WMM for a motif of length \(\ell\) is a \(4\ \times\ \ell\) matrix \(W\) of probabilities. The four rows of \(W\) are labeled with the four DNA bases, while the columns are labeled \(1 ... \ell\)

\(W(c, i)\) is the probability that position i of a motif instance is the base \(c\).

Instances of the motif are assumed to be drawn uniformly at random from \(W\) . More precisely, the \(i\)th base of an instance is drawn independently from the multinomial distribution \(W(*,i)\).

Here’s an example \(W\) of a WMM with \(\ell=6\):

Given a collection of putative instances of common length n, we can infer a motif model \(W\) by setting the probabilities directly from the counts of each base at each position.

That is,

Let \(W\) be a motif inferred from \(n\) putative instances \(s_1... s_n\).

For any \(s_j\), we can compare \(Pr(s_j\ |\ W)\) to the chance \(Pr(s_j\ |\ B)\) that \(s_j\) arose from some background base distribution \(B\).

The quantity \(log \frac {Pr(S_j|W)} {Pr(S_j|B)}\) is the log-likelihood ratio (LLR) for comparing hypotheses \(W\) and \(B\) given \(s_j\). If this quantity is greater than 0, \(s_j\) is more likely to have come from the motif \(W\) than from \(B\). If it is less than 0, the opposite is true.

Our measure of interest for \(W\) is the total LLR score

Note that the total LLR of a collection of putative instances is the sum of the LLR for each; equivalently, it is the log of the product of the probability ratios for the instances.

Motifs with higher total LLR scores look less like the background and more like their most plausible common WMM!

Greater similarity among instances makes the probability distributions in \(W\) more sharply peaked and hence raises LLR scores.

To assign a \(p\)-value to a putative motif, a program must compute the probability of seeing a motif with total LLR of at least some \(\sigma\) in a given amount of background sequence.

The models described above provide ways to quantify how interesting a motif is if we know its instances and the background in which it occurs.

In the motif-finding problem, we are given some sequences that are believed to contain a motif, but we do not know which parts of the sequences are motif instances and which are background.

There are two main variants of this problem: either the sequences are assumed to be unrelated to each other, or they are assumed to be homologous (and hence alignable). The algorithms used for these two cases are quite different.

Consider, for example, searching for a transcription factor binding site that occurs in the promoters of several different genes. These promoter regions are not usefully homologous, so we treat them as unrelated background sequences.

We hypothesize that there exists a common motif with instances in some or all of these promoter sequences, though we don’t know where the instances are.

Our goal is to find the most plausible motif — a set of putative instances matching a motif that is as unlike the background (high total LLR, or small radius for length) as possible.

Such a motif (hopefully) explains its putative instances significantly better than does the null hypothesis.

In the consensus model, we typically fix a motif length \(\ell\), a minimum instance count \(k\), and a radius \(r\), then seek sets of at least \(k\) instances that are all within radius \(r\) of some common consensus.

Algorithms that do this search are often enumerative — they enumerate all possible consensus sequences \(C\) and check whether there is a good motif (as defined above) in the data matching each \(C\).

Many sneaky tricks can be used to speed up this enumerative search, but its cost is fundamentally exponential in the motif length \(\ell\) and/or the input sequence length.

For the WMM, we fix a motif length \(\ell\) and seek a set of putative instances that maximize total LLR of their best WMM vs. the background (which is assumed to consist of all sequence not part of a motif instance).

We may make any of several assumptions as to how motif instances are distributed in each input sequence — one instance per sequence, at most one instance per sequence, multiple instances per sequence, etc.

While enumerative search can be used here as well, a more common approach is local search: guess an initial WMM \(W_0\) matching a set \(S_0\) of instances present in the input, then progressively make small changes to \(S_0\) and \(W_0\) so as to improve the motif’s total LLR.

There are two well-known, principled strategies for local search: expectation maximization and Gibbs sampling. They are guaranteed to find the best motif in the "neighborhood" of the original guess.

These approaches can yield good (though not necessarily globally optimal) answers much faster than enumeration. They are the basis for well-known programs like MEME and GibbsDNA.

Because a motif is a functional sequence element, it is subject to evolutionary pressures, in particular conservation against change.

As with any functional feature, we expect that a motif instance will be more strongly conserved against mutation than the surrounding sequence (assuming the latter is not itself functional!).

Hence, if we have several homologous sequences, each of which contains a motif instance at the same location, aligning them should cause the motif to stand out as better conserved than its surroundings.

Using this approach to locate motifs is called phylogenetic footprinting — the motif leaves a "footprint" of higher-than-normal conservation in the alignment.

An example of this approach is the EvoPrinter tool.

First, the input sequences must be globally alignable with high confidence; otherwise, errors due to incorrect placement of indels could result in instances of the motif not being aligned at all!

Second, the motif should appear at the same place in each of the sequences being aligned. Recall that motifs can arise convergently; they can also "disappear" from one place in a promoter or enhancer region and arise independently elsewhere in the same region.

Hence, it’s important to align homologous sequences that diverged on a time scale shorter than that of motif instance migration.

Third, it must be possible to distinguish the enhanced conservation of the motif from the background. But the null model for homologous background sequences is different from that for unrelated sequences.

Hence, we are looking for "somewhat more" (motif) vs. "somewhat less" (background) conserved regions, which means the signal-to-noise ratio is reduced.

Measures of interest are still useful, but they use a weak null hypothesis (unrelated background sequences) that is not right for footprinting.

Alternatively, estimate a "null" level of conservation from the background and show that the motif is better conserved than that.

The sophistication of this approach can range from low (estimate the typical information content of each alignment column in the background) to high (use a known phylogenetic tree on the sequences to estimate relative rates of evolution at motif vs. background positions).

Some tools offer \(p\)-values or \(E\)-values for putative motifs; others do not. For each tool, know what null model is being tested by the \(p\)-value calculation. Is it strong enough?

Motif finding works best when the search is restricted to a small region, on the order of a few thousand bases or less, and can survey a large number of motif-containing sequences (5–20 would be nice).

As the region gets larger and the number of instances smaller, the desired signal may be drowned out by noise. Algorithms will not find motifs, and those that are found will receive poor \(p\)-values.

You can use footprinting to identify regions of high conservation that are larger than a single motif (say, tens to hundreds of bases), then search just these regions using a traditional motif finder for unrelated sequences. This approach has much higher power than searching long sequences without first filtering for conservation.