exercise-sheet-5.Rmd

---
title: "Exercise sheet 5: Local Sequence Alignment"
---

---------------------------------

# Exercise 1 - Smith-Waterman

Consider the following sequences $S1$ and $S2$, a similarity scoring via $s(x,y)$ and a gap cost function $g(k)$.

\begin{align}
S1 &= TCCGA\\
S2 &= TACGCAGA\\
s(x, y) &=
  \begin{cases}
  +1 &if\ x=y\\
  0 &else
  \end{cases}\\
g(k) &= -k
\end{align}


### 1a)

Compute the local alignment matrix $S_{i,j}$ for the given sequence.



#### {.tabset}

##### Hide


```{r, include=FALSE}
sij <- read.csv("tables/sheet5_e1.csv", check.names=FALSE, sep=";")
sij_non_filled <- data.frame(sij, check.names=FALSE)
sij_non_filled[-1, c(-2, -1)] = " "
```

##### Matrix

```{r, results="asis", include=knitr::is_html_output(), echo=FALSE}
sij_non_filled_ft <- flextable(sij_non_filled)
sij_non_filled_ft <- custom_theme(sij_non_filled_ft)
index_replace(sij_non_filled_ft)
```

##### Hint: Formulae

\begin{align}
  H_{0,0} &= 0\\
  H_{i,0} &= 0\\
  H_{0,j} &= 0\\
  H_{i,j} &= max
  \begin{cases}
    H_{i-1, j-1} + s(a_i, b_j)\\
    H_{i-1,j} + s(a_i, -)\\
    H_{i, j-1} + s(-, b_j)\\
    0
  \end{cases}
\end{align}


##### Solution


```{r, results="asis", include=knitr::is_html_output(), echo=FALSE}
sij_ft <- flextable(sij)
sij_ft <- custom_theme(sij_ft)
index_replace(sij_ft)
```

#### {-}

### 1b)

Give all optimal local alignments and the according score.


#### {.tabset}

##### Hide


##### Solution

score: 3

```
TCCG    TCCGA   TCCG-A    CCGA
|:||    |:||:   |:|| |    |:||
TACG    TACGC   TACGCA    CAGA
```

#### {-}



# Exercise 2 - Affine gap costs

### 2a)

Which of these statements are correct?

#### {.tabset}

##### Statements


- [ ] Distance and similarity scores are equally useful for local alignment scoring
- [ ] Similarity scores are not suited for local alignment scoring
- [ ] Distance scores are not suited for local alignment scoring

##### Solution

- [ ] Distance and similarity scores are equally useful for local alignment scoring
- [ ] Similarity scores are not suited for local alignment scoring
- [X] Distance scores are not suited for local alignment scoring

#### {-}


### 2b)

You want to extend the Smith-Waterman algorithm for local alignment to more general gap scoring functions $g(k)$ (where $k$ denotes the gap length).

The following recursions were created analogously to the Waterman-Smith-Beyer algorithm. 
Which of these (if any) represents a variant of the Smith-Waterman algorithm that allows 
for an arbitrary gap scoring function?

$$
D_{0,0} = 0,\ D_{i,0}=0,\ D_{0,j}=0
$$

\begin{align}
  D_{i,j} &\stackrel{(i)}{=} max
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    max_{1 \leq k \leq j} D_{i,j-k} + g(1)\\
    max_{1 \leq k \leq i} D_{i-k,j} + g(1)\\
    0
  \end{cases}
   &D_{i,j} &\stackrel{(ii)}{=} max
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    max_{1 \leq k \leq j} D_{i,j-k} + g(k)\\
    max_{1 \leq k \leq i} D_{i-k,j} + g(k)\\
    0
  \end{cases}\\
  \\
  D_{i,j} &\stackrel{(iii)}{=} min
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    max_{1 \leq k \leq j} D_{i,j-k} + g(k)\\
    max_{1 \leq k \leq i} D_{i-k,j} + g(k)\\
    0
  \end{cases}
   &D_{i,j} &\stackrel{(iv)}{=} min
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    max_{1 \leq k \leq j} D_{i,j-k} + g(1)\\
    max_{1 \leq k \leq i} D_{i-k,j} + g(1)\\
    0
  \end{cases}\\
  \\
   D_{i,j} &\stackrel{(v)}{=} max
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    max_{1 \leq k \leq j} D_{i,j-k} + g(1)\\
    max_{1 \leq k \leq i} D_{i-k,j} + g(1)\\
    -1
  \end{cases}
\end{align}


#### {.tabset}


##### Hide



##### Solution

Only Formula $ii$ allows for an arbitrary gap scoring.

:::: {#explaining .message-box }
::: {#note-exp .note-header}
```{r, include=knitr::is_html_output(), echo=FALSE,}
knitr::include_graphics("figures/infoicon.svg")
```
**Note**
:::
::: {#note-exp .note-body}
Distance scores are not suited for local alignment scoring, thus all minimization 
approaches are not suitable. Further $g(1)$ does not represent an affine scoring.
:::
::::

#### {-}

### 2c)


The following recursions were created analogously to the Gotoh algorithm.
Which of these (if any) represents a variant of the Smith-Waterman algorithm 
that allows for an affine gap scoring function?


$$
D_{0,0} = 0,\ D_{i,0}=0,\ D_{0,j}=0
$$
\begin{align}
  D_{i,j} &\stackrel{(i)}{=} max
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    P_{i,j}\\
    Q_{i,j}\\
    0
  \end{cases}
  \begin{aligned}
    P_{i,j} &= max
    \begin{cases}
      D_{i-1,j} + g(1)\\
      P_{i-1, j} + \beta
    \end{cases}\\
    Q_{i,j} &= max
    \begin{cases}
      D_{i,j-1} + g(1)\\
      Q_{i, j-1} + \beta
    \end{cases}\\
  \end{aligned}\\
  \\
  D_{i,j} &\stackrel{(ii)}{=} max
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    P_{i,j}\\
    Q_{i,j}\\
    0
  \end{cases}
  \begin{aligned}
    P_{i,j} &= max
    \begin{cases}
      D_{i-1,j} + g(k)\\
      P_{i-1, j} + \beta
    \end{cases}\\
    Q_{i,j} &= max
    \begin{cases}
      D_{i,j-1} + g(k)\\
      Q_{i, j-1} + \beta
    \end{cases}\\
  \end{aligned}\\
  \\
  D_{i,j} &\stackrel{(iii)}{=} min
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    P_{i,j}\\
    Q_{i,j}\\
    0
  \end{cases}
  \begin{aligned}
    P_{i,j} &= min
    \begin{cases}
      D_{i-1,j} + g(k)\\
      P_{i-1, j} + \beta
    \end{cases}\\
    Q_{i,j} &= min
    \begin{cases}
      D_{i,j-1} + g(k)\\
      Q_{i, j-1} + \beta
    \end{cases}\\
  \end{aligned}\\
  \\
  D_{i,j} &\stackrel{(iv)}{=} min
  \begin{cases}
    D_{i-1, j-1} + s(a_i, b_j)\\
    P_{i,j}\\
    Q_{i,j}\\
    0
  \end{cases}
  \begin{aligned}
    P_{i,j} &= min
    \begin{cases}
      D_{i-1,j} + g(1)\\
      P_{i-1, j} + \beta
    \end{cases}\\
    Q_{i,j} &= min
    \begin{cases}
      D_{i,j-1} + g(1)\\
      Q_{i, j-1} + \beta
    \end{cases}\\
  \end{aligned}
\end{align}



#### {.tabset}

##### Hide


##### Solution

Only Formula $i$ allows for an affine gap scoring.

:::: {#explaining .message-box }
::: {#note-exp .note-header}
```{r, include=knitr::is_html_output(), echo=FALSE,}
knitr::include_graphics("figures/infoicon.svg")
```
**Note**
:::
::: {#note-exp .note-body}
Distance scores are not suited for local alignment scoring, thus all minimization 
approaches are not suitable. Therefore $iii$ and $iv$ don't represent the recursion.

According to the algorithm we only need to put gap introduction score into the $D$ matrix.
Thus $ii$ is also wrong.
:::
::::


#### {-}


---------------------------------

# Exercise 3 - 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 05](https://classroom.github.com/a/8mSuH5hH).

-------------------------------------------

# 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.

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 & Alignment button. If you completely marked a correct traceback it will get a green border. Else marked cells will get a red border.

It will further check whether the alignment in the alignment section below matches your traceback (only if your traceback is correct). If this is the case, the alignment will turn green else it will turn red.

:::: {#explaining .warning-box }

::: {#note-exp .warning-header}
```{r, include=knitr::is_html_output(), echo=FALSE,}
knitr::include_graphics("figures/warningicon.svg")
```
**Warning**
:::
::: {#note-exp .note-body}

This tool is in beta and might contain bugs.
:::
::::


```{r, echo=FALSE}
htmltools::includeHTML("html/smithwaterman.html")
```

```{r, echo=FALSE}
htmltools::tags$script(src = "assets/js/smithwaterman.js", type= "text/javascript")
```