Past exam of the mathematical and Computational Biology course of the University of Cambridge / 2025 / Paper 2 / 2

With no deletion states allowed, each match state must emit once in every aligned sequence. Thus the four gap-free alignment columns,

1, 2, 5, 7

, become

M_{1}, M_{2}, M_{3}, M_{4}

. Columns

3

and

4

form one optional run, represented by a single looping insertion state

I_{2}

; column

6

requires a separate insertion state

I_{3}

after

M_{3}

. Two insertion states are sufficient and minimal in an ordered profile hidden Markov model: the two optional regions are separated by a compulsory emission and occupy different positions in the profile.

Estimate each transition probability by the number of observed uses of that transition divided by all transitions leaving its source state. The complete arrow diagram is given below; repeated labels denote the same state, so the second and third lines supply the branches of the first line. Start and End are silent:

Start 1 M_{1} 1 M_{2} 1/4 M_{3} 1/2 M_{4} 1 End, M_{2} 3/4 I_{2} 3/4 M_{3}, I_{2} 1/4 I_{2}, M_{3} 1/2 I_{3} 1 M_{4} .

(1)

Three aligned sequences visit

I_{2}

, giving three exits to

M_{3}

, while one sequence emits twice there, giving one self-transition. Thus its exit and loop probabilities are

3/4

and

1/4

, respectively. Two sequences visit

I_{3}

and two bypass it. All absent transitions have probability zero.

The probability mass functions of the emitting states, estimated from all characters assigned to each state with no added counts, are

state M_{1} M_{2} I_{2} M_{3} I_{3} M_{4} A 1/2 0 1/4 00 1/4 T 00 1/2 100 G 1/4 3/4 1/4 00 3/4 C 1/4 1/4 0010 .

(2)

In particular, pooling the two optional columns into

I_{2}

pools four emissions: two T, one A and one G. This is a generative Hidden Markov model, so it can generate other run lengths and combinations as well as the training sequences; reproducing each training column deterministically is not its purpose.

b

 0  0

Solution

 0  0

The sequence has five characters, while the four match states account for four compulsory emissions. Consequently exactly one insertion state emission is needed. An insertion at

I_{3}

would have to emit T, which has probability zero there. The only nonzero hidden path is therefore

Start, M_{1} (C), M_{2} (G), I_{2} (T), M_{3} (T), M_{4} (A), End .

(1)

Multiply its transition probabilities and emission probabilities, including the probability of exiting

I_{2}

immediately and bypassing

I_{3}

P (CGTTA) = 1 \cdot \frac{1}{4} \cdot 1 \cdot \frac{3}{4} \cdot \frac{3}{4} \cdot \frac{1}{2} \cdot \frac{3}{4} \cdot 1 \cdot \frac{1}{2} \cdot \frac{1}{4} \cdot 1 = \frac{27}{4096} \approx 0.00659180 .

(2)

Normally the forward algorithm sums over all compatible paths. Here all other paths have probability zero, so this single path gives the full sequence probability.

c

 0  0

Solution

 0  0

Use a uniform independent DNA background, so each nucleotide has probability

1/4

. Conditional on length five, its sequence probability is

4^{- 5} = 1/1024

. The requested score, often called log-odds in sequence analysis, is a log-likelihood ratio against this background:

lo g_{2} \frac{P ( CGTTA )}{4 ^{- 5}} = lo g_{2} \frac{27}{4} \approx 2.75489 bits .

(1)

Using natural logarithms instead gives

ln (27/4) \approx 1.90954

. Identically distributed independent positions do not, by themselves, require equal base frequencies. If the intended background instead has specified frequencies

q_{A}, q_{T}, q_{G}, q_{C}

, the general answer is

lo g \frac{27/4096}{q _{C} q _{G} q _{T}^{2} q _{A}} .

(2)

The numerical value above uses the conventional equal-frequency random DNA model.

Taking a logarithm only after multiplying probabilities does not prevent floating-point underflow: the product may already have rounded to zero, and its logarithm is then

- \infty

. Accumulate logarithms before forming tiny products; where alternative paths must be added, use log-sum-exp in the forward algorithm or rescale its intermediate probabilities.

d

 0  0

Solution

 0  0

For the same uniform background and base-two log-likelihood ratio, replace every emission probability

b_{i} (x)

e_{i} (x) = lo g_{2} [b_{i} (x) / (1/4)]

. The background specifies independent letters, not a competing hidden-state process. Its single emitting state has continuation factor one when scoring a fixed-length word, so each model transition contributes

s_{ij} = lo g_{2} a_{ij}

; dividing every transition by

1/4

would incorrectly count the background twice.

The complete transition-score diagram is

Start 0 M_{1} 0 M_{2} - 2 M_{3} - 1 M_{4} 0 End, M_{2} l o g_{2} (3/4) I_{2} l o g_{2} (3/4) M_{3}, I_{2} - 2 I_{2}, M_{3} - 1 I_{3} 0 M_{4} .

(1)

Every omitted transition has score

- \infty

. Silent Start and End supply no emission score. The complete table of emission scores is

state M_{1} M_{2} I_{2} M_{3} I_{3} M_{4} A 1 - \infty 0 - \infty - \infty 0 T - \infty - \infty 12 - \infty - \infty G 0 lo g_{2} 3 0 - \infty - \infty lo g_{2} 3 C 00 - \infty - \infty 2 - \infty .

(2)

For the unique nonzero path identified in (b), add the five emission scores and all transition scores:

score = emissions 0 + lo g_{2} 3 + 1 + 2 + 0 + transitions 2 lo g_{2} (3/4) - 1 = lo g_{2} 27 - 2 = lo g_{2} (27/4) .

(3)

This equals (c). For a sequence with several nonzero hidden paths, the full log-likelihood ratio is the log-sum-exp of their path scores; selecting only the largest score would instead compute a best-path approximation.