Exercise sheet 5: Probalign

Question 1

Compute the Boltzmann-weighted score for the following alignments:

(a)  x: --AGCGG          (b) x: AGCGG------
          ||:||                     :
     y: ACAGGGG              y: ----ACAGGGG

Answer

$S(a) = \sum_{x_i \sim y_j \in a} \sigma(x_i,y_j) + \sum \text{gap penalties}\\ e^{\frac{S(a)}{T}} = \Bigg(\prod_{x_i\sim y_j \in a} e^{\frac{\sigma(x_i,y_j)}{T}} \Bigg) \times e^{\frac{\sum \text{gap penalties}}{T}}\\$

Answer

For each alignment you only need to calculate $e^x$ once.

Answer

$\begin{align*} \text{(a)} &\qquad e^{\sigma(A,A)} \times e^{3\sigma(G,G)} \times e^{\sigma(C,G)} \times e^{g(2)} &&= e^2 \times e^6 \times e^{-1} \times e^{-0.5 +(-0.25\times 2)} = e^6 \\ \text{(b)} &\qquad e^{\sigma(G,A)} \times e^{g(4)} \times e^{g(6)} &&= e^{-1} \times e^{0.5 + (-0.25\times 4)} \times e^{0.5 + (-0.25\times 6)} = e^{-4.5} \end{align*}$

Answer

$\begin{align*} \text{(a)} &\qquad e^6 = 403.43\\ \text{(b)} &\qquad e^{-4.5} = 0.011 \end{align*}$

Question 2

Derive the recursion formula for $Z^{I}_{i,j}$ . Allow insertions after deletions and vice versa.

Answer

$Z^{I}_{i,j} = Z^{I}_{i,j-1} \times e^\frac{\beta}{T} + Z^{M}_{i,j-1} \times e^\frac{g(1)}{T} + Z^{D}_{i,j-1} \times e^\frac{g(1)}{T}$

Question 3

Compute the partition function Z(T) by dynamic programming for the sequences x=ACC and y=AC. Allow insertions after deletions and vice versa. In order to simplify the computations, you can round to two digits after the decimal point. Please be aware that we used exact numbers for all calculations and rounded in the end.

Answer

Initialization: $\begin{align*} Z^M_{i,0} &= Z^M_{0,j} = 0, Z^M_{0,0} = 1\\ Z^I_{i,0} &= 0\\ Z^D_{0,j} &= 0 \end{align*}$

Recursion: $\begin{align*} Z^{M}_{i,j} &= Z_{i-1,j-1} \times e^{\frac{\sigma(x_i,y_j)}{T}}\\ Z^{I}_{i,j} &= Z^{I}_{i,j-1} \times e^\frac{\beta}{T} + Z^{M}_{i,j-1} \times e^\frac{g(1)}{T} + Z^{D}_{i,j-1} \times e^\frac{g(1)}{T}\\ Z^{D}_{i,j} &= Z^{D}_{i-1,j} \times e^\frac{\beta}{T} + Z^{M}_{i-1,j} \times e^\frac{g(1)}{T} + Z^{I}_{i-1,j} \times e^\frac{g(1)}{T}\\ Z_{i,j} &= Z^{M}_{i,j} + Z^{I}_{i,j} + Z^{D}_{i,j} \end{align*}$

Question 4

Find a mapping from matrix $Z^{*}_{k,l}$ to $Z^{\prime}_{i,j}$ . Which position in matrix $Z^{*}$ corresponds to which position in matrix $Z^{\prime}$ ?

Answer

$Z^{\prime}_{i,j}$ is the partition function of the alignment $x_i ... x_{|x|}$ with $y_j ... y_{|y|}$ .

$Z^{*}_{k,l}$ is the partition function of the alignment $x_{|x|} ... x_{|x|-k+1}$ with $y_{|y|}...y_{|y|-l+1}$ .

$\begin{align*} i &= |x| -k +1 \Leftrightarrow k = |x| -i +1\\ j &= |y| -l +1 \Leftrightarrow l = |y| -j +1 \end{align*}$

Question 5

Use $Z,Z^*$ and the mapping from $Z^*$ to $Z^\prime$ to compute the probability of the alignment edges $(1,1)$ , $(2,2)$ , $(3,1)$ and $(3,2)$ between $x$ and $y$ .

Answer

$P(x_i \sim y_j | x,y) = \frac{Z_{i-1,j-1}\times e^{\frac{\sigma(x_i,y_j)}{T}} \times Z^{\prime}_{i+1,j+1}}{Z(T)}\\ Z^M_{i,j} = Z_{i-1,j-1} \times e^{\frac{\sigma(x_i,y_j)}{T}}$

Answer

Mapped positions: $\begin{align*} Z^{\prime}_{2,2} &\Longleftrightarrow Z^{\ast}_{2,1}\\ Z^{\prime}_{3,3} &\Longleftrightarrow Z^{\ast}_{1,0}\\ Z^{\prime}_{4,2} &\Longleftrightarrow Z^{\ast}_{0,1}\\ Z^{\prime}_{4,3} &\Longleftrightarrow Z^{\ast}_{0,0} \end{align*}$

Answer

Alignment edge $(1,1)$ : $P(x_1 \sim y_1 | x,y) = \frac{Z_{0,0}\times e^{\frac{\sigma(x_1,y_1)}{T}} \times Z^{\prime}_{2,2}}{Z(T)} =\frac{Z_{0,0}\times e^{\frac{\sigma(x_1,y_1)}{T}} \times Z^{\ast}_{2,1}}{Z(T)} = \frac{Z^M_{1,1} \times Z^{\ast}_{2,1}}{Z(T)} = \frac{7.39 \times 7.43}{61.90} = 0.89$ Alignment edge $(2,2)$ : $P(x_2 \sim y_2 | x,y) = \frac{Z_{1,1}\times e^{\frac{\sigma(x_2,y_2)}{T}} \times Z^{\prime}_{3,3}}{Z(T)} =\frac{Z_{1,1}\times e^{\frac{\sigma(x_2,y_2)}{T}} \times Z^{\ast}_{1,0}}{Z(T)} = \frac{Z^M_{2,2} \times Z^{\ast}_{1,0}}{Z(T)} = \frac{57.90 \times 0.47}{61.90} = 0.44$ Alignment edge $(3,1)$ : $P(x_3 \sim y_1 | x,y) = \frac{Z^M_{3,1} \times Z^{\prime}_{4,2}}{Z(T)} = \frac{Z^M_{3,1} \times Z^{\ast}_{0,1}}{Z(T)} = \frac{0.14 \times 0.47}{61.90} = 0.001$ Alignment edge $(3,2)$ : $P(x_3 \sim y_2 | x,y) = \frac{Z^M_{3,2} \times Z^{\prime}_{4,3}}{Z(T)} = \frac{Z^M_{3,1} \times Z^{\ast}_{0,0}}{Z(T)} = \frac{30.42 \times 1}{61.90} = 0.49$

Exercise sheet 5: Probalign

Exercise 1

1a)

Exercise 2

2a)

2b)

Exercise 3

3a)

3b)