Brief theoretical introduction

Position weight matrices

Position weight matrices (PWMs), also known position specific scoring matrices (PSSM) or weighted patterns, are a simple yet powerful model for sequence signals used in bioinformatics. They can be, for example, used to model transcription factor binding sites in DNA or other binding sites.

PWMs are obtained usually from empirically observed instances of binding sites by counting occurrences of symbols in different positions, represented as count or frequency matrices. For example, a count matrix could look like this (example from JASPAR database), where each four rows specifies the counts or frequencies for nucleotides A, C, G and T, respectively:

10.00  12.00   4.00   1.00   2.00   2.00   0.00   0.00   0.00   8.00  13.00
 2.00   2.00   7.00   1.00   0.00   8.00   0.00   0.00   1.00   2.00   2.00
 3.00   1.00   1.00   0.00  23.00   0.00  26.00  26.00   0.00   0.00   4.00
11.00  11.00  14.00  24.00   1.00  16.00   0.00   0.00  25.00  16.00   7.00

MOODS by default can read matrix files in JASPAR count format (.pfm).

Log-odds scoring

By default, MOODS converts count/frequency matrices to PWMs using log-likelihood scoring that defines a score against a DNA sequence; this is then used to identify putative sites matching the motif described by the matrix. Specifically, given a $4 \times m$ count/frequency matrix $M$ and a background probability $\pi[a]$ for each nucleotide $a$, the pseudocounts are added to the matrix and the values are normalised:

$$ f[a,i]=\frac{M[a,i]+P\cdot\pi[a]}{\sum_{a}\big(M[a,i]+P\cdot\pi[a]\big)}, $$

where $P$ is the pseudocount value (default 0.01 in moods_dna.py).

The frequencies are then used to compute the PWM $L$ as

$$ L[a,i]=\log\frac{f[a,i]}{\pi[a]}. $$

For any sequence $u$ of length $m$, the PWM $L$ defines a match score as

$$ W_L(u)=\sum_{i=1}^{m}L[a,i]=\sum_{i=1}^{m}\log\frac{f[a,i]}{\pi[a]} $$

Intuitively, this score compares the probability that the model specified by the original frequency matrix $f$ generated the sequence $u$ versus the probability that the background model $\pi$ generated $u$.

Finding PWM matches

Given a PWM $L$, and a sequence $s=s_1 s_2 \ldots s_n$, the specific task we consider is finding sequence positions $i$ such that the score given by the matrix exceeds some given threshold $T$, that is,

$$ W_L(s_{j}s_{j+1}\ldots{s_{j+i-1}})=\sum_{i=1}^{m}L[s_{j+i},j]\ge{T}. $$

The idea is that these matches should correspond e.g. to putative transcription factor binding sites for the factor described by the original count matrix.

The exact choice of the threshold $T$ obviously greatly affects the results. There are a couple of options for choosing the threshold; by default, MOODS assume that the threshold is given by a $p$-value $x$, and the actual threshold $T$ is chosen so that the probability that the background distribution $\pi$ generates a sequence $u$ of length $m$ with score ${W_L}(u)\ge{T}$ is $p$. Alternatively, the score threshold can be set heuristically to some suitable value.

References

For more discussion and background, see e.g.

• https://en.wikipedia.org/wiki/Position_weight_matrix
• https://en.wikipedia.org/wiki/Additive_smoothing

For more technical details, see the following articles.

• C. Pizzi, P. Rastas and E. Ukkonen: Finding Significant Matches of Position Weight Matrices in Linear Time. IEEE/ACM Transactions on Computational Biology and Bioinformatics. (2011)
• J.H. Korhonen, K. Palin, J. Taipale and E. Ukkonen: Fast motif matching revisited: high-order PWMs, SNPs and indels. Bioinformatics. (2016)