Exercise sheet 4: Sequence Alignment - affine gap costs
Exercise 1 - Waterman-Smith-Beyer traceback
Within the algorithm of Waterman, Smith and Beyer arbitrarily large gaps are considered. Thus, also the traceback has to investigate all gap sizes. This can be done following two strategies:
- check in increasing gap length (start with smallest gap)
- check in decreasing gap length (start with largest gap)
1a)
Given a gap function, are the strategies (measured in absolute runtime or number operations) expected to be equally performant or is one of them better than the other?
Hide
Possible Answers
Solution
(You still have to check all possible gap sizes)
1b)
Does the order of checking insertion and deletions change the runtime?
Hide
Possible Answers
Solution
(You still have to check all possible gaps and sizes)
Exercise 2 - Waterman-Smith-Beyer traceback
Warning
The previously uploaded recursion schema was wrong. We will either try to fix this exercise or remove it completely. Sorry for any inconvenience.
Exercise 3 - Gotoh Algorithm
Consider the following sequences \(S1\) , \(S2\) and the similarity scoring via \(s(x, y)\) and \(g(k)\).
\[\begin{align} S1 &= TCCGA\\ S2 &= TACGCAGA\\ s(x,y) &= \begin{cases} +1 & if\ x = y \\ 0 & else\\ \end{cases}\\ g(k) &= -4 - 1 * k \end{align}\]
3a)
Which optimization scheme (minimization/maximization) needs to be applied to generate a useful sequence alignment.
Hide
Solution
Maximization since we are scoring a similarity and not a distance.
3b)
Fill the dynamic programming matrices \(D_{i,j}\), \(Q_{i,j}\) and \(P_{i,j}\) using the Gotoh algorithm!
(Remember: \(D_{i,j}\) is the match/mismatch matrix. \(Q_{i,j}\) corresponds to gaps in \(S1\) whilst \(P_{i,j}\) corresponds to gaps in \(S2\))
Hide
Hint1: Init Formulae
\[\begin{align} D_{0,0} &= 0 \\ D_{0, j} &= g(j) &\forall j: 0 < j \leq n \\ D_{i, 0} &= g(j) &\forall i: 0 < i \leq n \\ Q_{i, 0} &= -\infty &\forall i: 0 < i \leq n \\ P_{0, j} &= -\infty &\forall j: 0 < j \leq n \end{align}\]
Hint2: Formulae
\[\begin{align} g(k) &= \alpha + k * \beta \\ \\ D_{i,j} &= max \begin{cases} D_{i-1, j-1} + s(a_i, b_i)\\ P_{i, j}\\ Q_{i,j} \end{cases}\\ \\ Q_{i,j} &= max \begin{cases} D_{i, j-1} + g(1)\\ Q_{i, j-1} + \beta\\ \end{cases}\\ \\ P_{i,j} &= max \begin{cases} D_{i-1, j} + g(1)\\ P_{i-1, j} + \beta\\ \end{cases} \end{align}\]
Hint3: Add the missing values
Di,j | - | T | A | C | G | C | A | G | A |
|---|---|---|---|---|---|---|---|---|---|
- |
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
| -7 | -8 | -9 | -10 |
C |
|
|
|
|
| -5 | -7 | -8 | -9 |
C |
| -5 | -4 | 2 | -3 | -4 | -5 | -6 | -7 |
G |
| -6 | -5 | -3 | 3 |
|
|
|
|
A |
| -7 | -5 | -4 | -2 |
|
|
|
|
Qi,j | - | T | A | C | G | C | A | G | A |
|---|---|---|---|---|---|---|---|---|---|
- |
|
|
|
|
|
|
|
|
|
T |
|
|
|
| -6 | -7 | -8 | -9 | -10 |
C |
|
|
|
| -5 | -6 | -7 | -8 | -9 |
C |
| -12 | -10 | -9 | -3 | -4 | -5 | -6 | -7 |
G |
| -13 | -11 | -10 |
|
|
|
|
|
A |
| -14 | -12 | -10 |
|
|
|
|
|
Pi,j | - | T | A | C | G | C | A | G | A |
|---|---|---|---|---|---|---|---|---|---|
- |
|
|
|
|
|
|
|
|
|
T |
|
|
|
| -13 | -14 | -15 | -16 | -17 |
C |
|
|
|
| -11 | -12 | -13 | -14 | -15 |
C |
| -5 | -4 | -8 | -10 | -10 | -12 | -13 | -14 |
G |
| -6 | -5 | -3 |
|
|
|
|
|
A |
| -7 | -6 | -4 |
|
|
|
|
|
Solution
Di,j | - | T | A | C | G | C | A | G | A |
|---|---|---|---|---|---|---|---|---|---|
- | 0 | -5 | -6 | -7 | -8 | -9 | -10 | -11 | -12 |
T | -5 | 1 | -4 | -5 | -6 | -7 | -8 | -9 | -10 |
C | -6 | -4 | 1 | -3 | -5 | -5 | -7 | -8 | -9 |
C | -7 | -5 | -4 | 2 | -3 | -4 | -5 | -6 | -7 |
G | -8 | -6 | -5 | -3 | 3 | -2 | -3 | -4 | -5 |
A | -9 | -7 | -5 | -4 | -2 | 3 | -1 | -3 | -3 |
Qi,j | - | T | A | C | G | C | A | G | A |
|---|---|---|---|---|---|---|---|---|---|
- | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
T | -inf | -10 | -4 | -5 | -6 | -7 | -8 | -9 | -10 |
C | -inf | -11 | -9 | -4 | -5 | -6 | -7 | -8 | -9 |
C | -inf | -12 | -10 | -9 | -3 | -4 | -5 | -6 | -7 |
G | -inf | -13 | -11 | -10 | -8 | -2 | -3 | -4 | -5 |
A | -inf | -14 | -12 | -10 | -9 | -7 | -2 | -3 | -4 |
Pi,j | - | T | A | C | G | C | A | G | A |
|---|---|---|---|---|---|---|---|---|---|
- | 0 | -inf | -inf | -inf | -inf | -inf | -inf | -inf | -inf |
T | 0 | -10 | -11 | -12 | -13 | -14 | -15 | -16 | -17 |
C | 0 | -4 | -9 | -10 | -11 | -12 | -13 | -14 | -15 |
C | 0 | -5 | -4 | -8 | -10 | -10 | -12 | -13 | -14 |
G | 0 | -6 | -5 | -3 | -8 | -9 | -10 | -11 | -12 |
A | 0 | -7 | -6 | -4 | -2 | -7 | -8 | -9 | -10 |
3c)
Calculate all optimal alignments and the corresponding score!
Hide
Solution
Score: -3
T---CCGA TCC---GA TCCG---A
| |:|| |:| || |:|| |
TACGCAGA TACGCAGA TACGCAGA3d)
Calculate the alignments using the Waterman-Smith-Beyer algorithm instead.
Hide
Solution
The same alignments as in (3c), since the same scoring function is optimized. Calculation is just less efficient.
Exercise 4 - Programming assignment
Programming assignments are available via Github Classroom and contain automatic tests.
We recommend doing these assignments since they will help you to further understand this topic.
Access the Github Classroom link: Programming Assignment: Sheet 04.
Preparing for the Exam
Below you find an interactive tool that allows you to create dynamic programming matrices to practice for the exam. You can fill in the table and check which values are correct via the Check Matrix button. Correctly filled cells will turn green. Please specify infitnity values via -inf or inf
Once you filled in the cells, you can trigger the traceback mode toggle. This will disable the input fields. However, you can now select cells that are part of a traceback. While in traceback mode you can click the Check Traceback button. If you completely marked a correct traceback it will get a green border. Else marked cells will get a red border.
Warning
This tool is in beta and might contain bugs.