# Motif detection using a Hidden Markov Model¶

## Introduction¶

This notes started as an adaptation of Rabiner’s tutorial to Profile HMM.

## Problem description¶

We have a sequence of length \(n\) over some alphabet \(\pmb{A}\). This sequence is generated by a random process, so the sequence is a random variable \(\pmb{X}\):

As said before the range of each \(X_i\) is the alphabet:

We will call each element of \(\pmb{A}\) a symbol. The size of the alphabet is \(|\pmb{A}|\).

We assume that each \(X_i\) can be part either of some repeating motif of length \(W\) or be just background noise. When considering repeating motifs we allow to be gaps and deletions on the motif. For example consider the following sequences made of the letters A,B,C,D,E (spaces added to aid the reader):

Repeating motif

`ABCDE ABCDE ABCDE ABCDE ABCDE`

With some baground noise between motif repetitions

`ABCDE AB ABCDE BB ABCDE C ABCDE CCCC ABCDE`

With deletions

`ABDE AB ABCDE BB BCDE C ABCDE CCCC ABDE`

With gaps

`ABAACDE ABCDE A ACCCBCDE C ABCDE ABCE`

## Model¶

To account for background noise, deletions and gaps we model the generation of the sequence with a Profile Hidden Markov Model (PHMM). In a PHMM the hidden process generating the sequence changes between states according to the following state diagram, where each node represents an state and the process jumps randomly from one state to another state following the arrows:

There are three types of states:

Background states

\[\pmb{S}^B=\left\{b_1,...,b_W\right\}\]Motif states

\[\pmb{S}^M=\left\{m_1,...,m_W\right\}\]Delete states

\[\pmb{S}^D=\left\{d_1,...,d_W\right\}\]

When the process jumps to a background state it emits a letter of the sequence according to the background distribution. We assume that all background states follow the same categorical distribution where each symbol \(a \in \pmb{A}\) is emitted with probability \(f^B_a\).

When the process jumps to a motif state it emits a letter of the sequence according to the motif distribution. We assume that the emission probability depends on which motif state we are in, and so if we are in state \(m_j\) each symbol \(a\) is emitted with probability \(f^M_{ja}\).

When the process jumps to a deletion state it emits nothing. These are silent states introduced only for the purpose of allowing jumps between motifs \(m_j\) and \(m_k\) for \(k>j+1\).

Notice that the state diagram has loops. This is because it models the motif, which is allowed to repeat.

The above diagram is incomplete if we don’t specify the probabilites of state transitions. The following table gives them for direct transitions between states:

To state | |||||

\(b_j\) | \(b_{j+1}\) | \(m_{j+1}\) | \(d_{j+1}\) | ||

From state | \(b_j\) | b(j) | 0 | 1 - b(j) | 0 |

\(m_j\) | 0 | \(m_b\) | \(m\) | \(m_d\) | |

\(d_j\) | 0 | 0 | 1 - d | d |

To avoid introducing too much parameters we have assumed that the transition probabilities are stationary, the only exception being:

Now let’s define the random variable \(Z_i\) as the state of the process when emitting symbol \(X_i\). Then the range of \(Z_i\) is:

With these variables we have the familiar HMM. Notice that although similar to the graph of the PHMM this one has different meaning. The former was an state diagram and this one is a Bayesian network. Each node is now a random variable instead of a concrete state:

We are capable of computing the transition probabilities between the emitting states \(Z_i\). For this we must consider any possible path that connects the two states, compute the probability of each path and sum all the probabilities. To make this more concrete consider the case of motif width \(W=6\), where we start from state \(m_2\):

We can see the pattern in the above formulas. If we consider the path going from \(m_j\) to \(m_k\) the number of delete states we must cross is:

Then the probability of the path is:

Where \([k=j+1]\) is the Iverson bracket, which takes the value 1 only when the condition inside the brackets is true, and zero otherwise.

Notice that given the value of \(j\) and \(L_{jk}\) we can recover \(k\) as:

To compute the final probability we need to take into account the cases where we make several loops over all the delete states. Each loop has probability \(d^W\), and \(l\) loops then \((d^W)^l\). The following figure shows the possible paths between two states depending on the number of loops:

The final probability is then:

Making the summation we get we get the final transition probabilities when starting from state \(m_j\):

The behavior of \(F(l, d)\) near the boundaries is:

The following figure shows a plot for \(W=6\):

We can see in the above graph that lower values of \(d\) concentrate the probabilities on the state two steps ahead, and higher values spread the probabilities more evenly on all the states.

The transitions starting from a background states are trivial:

The emission probabilities:

### Manual annotations¶

We extend the model with a random variable \(U_i\) for each \(Z_i\):

These random variables are direct observations on the state variables that flag whether or not a hidden state is part of a motif:

We can use this to aid in detecting motifs. For example, a user can manually annotate where motifs are by specifying the value of \(U_i\).

## Parameter estimation¶

### Expectation-Maximization (EM)¶

For convenience let’s aggregate all the model parameters into a single vector:

Using EM each step takes the form, where \(\pmb{\theta}^0\) and \(\pmb{\theta}^1\) are the current and next estimates of the parameters respectively:

\(\pmb{x}^D\) is the training data, a particular realization of \(\pmb{X}\).

\(P(\pmb{\theta})\) are the prior probabilities on the parameters. We are going to consider priors only on \(\pmb{f}^M\).

### EM on a HMM¶

Taking into account that in a HMM the joint probability distribution factors as:

We expand the expectation in the EM step as:

Interchanging the summations:

Defining the set \(\pmb{C}_i=\left\{Z_{i-1}, Z_i\right\}\) we can always do:

Now the summation over \(\pmb{Z}\) can be decomposed as:

Of course:

And so we finally get:

### Computing \(P(Z_{i-1}, Z_i|\pmb{X},\pmb{\theta})\)¶

To unclutter a little let’s call:

Notice that:

And so we just need to compute \(\xi_i\). To compute it we first apply Bayes theorem:

Now, thanks to the Markov structure of the probabilities we can factor things:

Renaming things a bit again:

We get that:

We compute the first values of \(\alpha\) to see the pattern:

In general:

Following the same process but starting from the end of the HMM we get:

We can take into account in this step any information the user has provided about the states. If we know that:

And of course renormalize:

And also we do the same with \(\beta\).

### Re-estimation equations¶

We now separate the expectation in two independent parts:

We can continue splitting into independent parts:

And also:

We have now 4 independent maximization problems:

### Estimation of \(\pmb{f}^B\)¶

We need to solve:

With the constraint:

We will enforce the constraints using Lagrange multipliers, and taking derivatives:

From this we get the closed form solution:

### Estimation of \(\pmb{f}^M\)¶

We need to solve:

With the constraint:

We will enforce the constraints using Lagrange multipliers, and taking derivatives:

If we use Dirichlet distribution over the symbols of each \(\pmb{f}^M_j\). The log-probability of the prior is then:

And the derivative:

From this we get the closed form solution:

Where \(\varepsilon_0\) is called the concentration parameter and it’s:

### Estimation of \(b\)¶

We need to solve:

Taking derivatives we get:

### Estimation of \(\pmb{t}^M\)¶

We need to solve:

Subject to the constraint:

Trying to solve the above problem using Lagrange multipliers gives as a result a set of highly non-linear equations in \(d\), and since the rest of the parameters are coupled to \(d\) either directly or trough the constraint it is not possible to find a closed form solution. Because of this we throw away the Lagrange multipliers and solve the maximization problem numerically.

Let’s recap the shape of our problem:

We rewrite the summation as:

Since we are going to solve the problem numerically it is possible that we reach a local maximum. As long as we improve the starting point it is enough.

## Time Complexity¶

The time complexity of the parameter estimation problem is dominated by the estimation of \(\alpha\), \(\beta\) and \(\xi\). We have a triple loops of this form:

```
for i in range(n):
for s in range(2*W):
for t in range(2*W):
xi[s, t, i] = alpha[s, i - 1]*beta[t, i]*pT[s, t]
```

In the above code the math symbols have been rewriten as numpy arrays:

Math | Python |
---|---|

\(\xi_i(s, t)\) | `xi[s, t, i]` |

\(\alpha_i(s)\) | `alpha[s, i]` |

\(\beta_i(s)\) | `beta[s, i]` |

\(P(Z_{i+1}=t|Z_i=s)\) | `pT[s, t]` |

Time complexity is therefore \(O(nW^2)\). We can speed up the
above triple loop by noticing that a lot of entries in the `pT`

matrix are zeros:

Taking only the non-zero entries into account we could move complexity from \(4nW^2\) to \(nW(W+3)\), which would divide time almost by a factor of 4.

The reason that the lower right part of the matrix, that is the transition probabilities between motif states, is full is that the possibility of deleting states of the motif means that we can jump from any motif state to any other motif state. If on the other hand we didn’t allow deletions the state transition diagram would look as:

Transition probabilities from the background states would remain unchanged and transition probabilities from the motif states would simply be:

Now the matrix of transition probabilities has the following non-zero entries:

And time complexity is just \(4nW\). This simplified model is actually a very good approximation of the more complex one. The following plot shows how the values of the full model are distributed inside the transition matrix for typical parameters:

To see how fast probabilities decay away from the diagonal consider the following plot showing the values around state 60 (motif state 20):

We can make a compromise between the fully diagonal model and a model where only \(w\) elements away from the diagonal are retained. The transition matrix would look like:

Time complexity would be then \(nW(3 + w)\). Let’s call \(\tilde{P}(\pmb{X}, \pmb{Z})\) the probability distribution of the sequence under this new approximate transition matrix. We can get a modified EM algorithm:

The EM algorithm proceeds as usual but with a modified function to maximize:

The only modification in the forward-backward algorithm is that there are more zeros now on the transition matrix. We get halfway to a variational approach like the one in Factorial hidden Markov models.