1
$\begingroup$

I am having trouble understanding the affine gap penalty in the following example -

Waterman-Smith-Beyer Algorithm:

\begin{align*} D_{0,0} &= 0\\ D_{0,j} &= g(j)\\ D_{i,0} &= g(i)\\ \forall i,j > 0,~ S_{i,j} &= \min \begin{Bmatrix} \min_{1 \leq k \leq j}{(D_{i,j-k} + g(k))}\\ D_{i-1,j-1} + w(a_i,b_j)\\ \min_{1 \leq k \leq j}{(D_{i-k,j} + g(k))}\\ \end{Bmatrix} \end{align*} where $g(k)$ is the gap penalty function and $w$ is the similarity score.

enter image description here

The affine gap penalty here is $g(k) = 1 + k$ and the mismatch score is $1$ and the match score is $0$.

I am not sure where the 3 and 4 come from or the 4 and 5 in cells 1,3 and 2,4. I'm not understanding how the affine gap penalty works here. I understand how the linear gap penalty worked in the Needlemen_Wunsch but not this. Is k the gaps before hand?

Improve this question
$\endgroup$
6
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Commented Oct 3, 2017 at 15:01
  • $\begingroup$ You don't have to understand where the formula comes from -- just apply it. Note how $k$ is bound by the $\min$ operator. $\endgroup$
    – Raphael
    Commented Oct 3, 2017 at 15:02
  • $\begingroup$ @Raphael No I mean I dont understnad how to apply them when it comes to the affine gap penalty. $\endgroup$
    – H5159
    Commented Oct 3, 2017 at 15:23
  • 1
    $\begingroup$ Then I don't understand your query. Up to a typo ($D_{i,j}$?), you have given a recurrence. Calculate $D_{m,n}$ with $m = |a|$ and $n=|b|$, following the formula. That's what's happening here. If you want a more specific answer, you'll have to show your work and ask a more specific question. $\endgroup$
    – Raphael
    Commented Oct 3, 2017 at 17:07
  • $\begingroup$ FWIW, I don't understand the table you have included a picture of (attribution, btw?), either. Without context, it's not clear what the individual cells contain. $\endgroup$
    – Raphael
    Commented Oct 3, 2017 at 17:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.