Question

Alignment with gap penalties. The alignment algorithm of Exercise 6.26 helps to identify DNA sequences that are close to one another. The discrepancies between these closely matched sequences are often caused by errors in DNA replication. However, a closer look at the biological replication process reveals that the scoring function we considered earlier has a qualitative problem: nature often inserts or removes entire substrings of nucleotides (creating long gaps), rather than editing just one position at a time. Therefore, the penalty for a gap of length 10 should not be 10 times the penalty for a gap of length 1, but something significantly smaller.

Repeat Exercise 6.26, but this time use a modified scoring function in which the penalty for a gap of length k is c₀ + c₁k, where c₀ and c₁ are given constants (and c₀ is larger than c₁).

Short answer

The alignment algorithm with a modified scoring function is as follows,

$$\begin{gathered} s(i,j,0)=\underset{0\le k<a}{max}\left(s\left(i-1,j-1,k\right)+\delta \left(x\left[i\right],y\left[j\right]\right)\right) \\ s(i,j,1)=max\left(\begin{array}{c}s(i,j-1,0)-(c_0+\_c_1)\\ s(i,j-1,1)-c_1\\ s(i,j-1,2)-(c_0+\_c_1)\end{array}\right)+\delta \left(-,y\left[j\right]\right) \\ s(i,j,2)=max\left(\begin{array}{c}s(i,j-1,j,0)-(c_0+\_c_1)\\ s(i,j-1,j,1)-(c_0+\_c_1)\\ s(i,j-1,j,2)-c_1\end{array}\right)+\delta \left(x\left[i\right],-\right) \end{gathered}$$

Step-by-step solution

Explain Alignment with gap penalties:

An array alignment provides a way of identifying the regions of similarities between the strings. The matrix M of size n x m is constructed to find the best aligning score of the given strings. The given case can occur for any two characters of the strings.The first case is to align the sequence with no gaps. The match or miss is determined by the given scoring function. The other case is to align the sequence with gaps.

Give the alignment algorithm with a modified scoring function

Consider the alignment algorithm of Exercise 6.26 as follows,

$s(i,j)=max\left(\begin{array}{c}s(i-1,j)+\delta \left(x\left[i\right],-\right)\\ s(i,j-1)+\delta (-,y\left[j\right])\\ s(i-1,j-1)+\delta \left(x\left[i\right],y\left[j\right]\right)\end{array}\right)$

Redefine the subproblem as, s(i,j,k) where,$k\in \left\{0,12\right\}$ corresponding to the three matches at the las position:

$x\left[i\right]\leftrightarrow y\left[j\right],-\leftrightarrow y\left[j\right],x\left[i\right]\leftrightarrow -$, So by adding the modified scoring function the alignment algorithm can be provided as follows,

$$\begin{gathered} s(i,j,0)=\underset{0\le k<a}{max}\left(s\left(i-1,j-1,k\right)+\delta \left(x\left[i\right],y\left[j\right]\right)\right) \\ s(i,j,1)=max\left(\begin{array}{c}s(i,j-1,0)-(c_0+\_c_1)\\ s(i,j-1,1)-c_1\\ s(i,j-1,2)-(c_0+\_c_1)\end{array}\right)+\delta \left(-,y\left[j\right]\right) \\ s(i,j,2)=max\left(\begin{array}{c}s(i,j-1,j,0)-(c_0+\_c_1)\\ s(i,j-1,j,1)-(c_0+\_c_1)\\ s(i,j-1,j,2)-c_1\end{array}\right)+\delta \left(x\left[i\right],-\right) \end{gathered}$$

Therefore, The alignment algorithm with modified scoring function has been provided.