91Ó°ÊÓ

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.

Consider the alignment algorithm of Exercise 6.26 as follows,

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

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

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

$$\begin{gathered} s(i,j,0)=\underset{0≤k<a}{max}\left(s\left(i-1,j-1,k\right)+\mathrm{δ}\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)+\mathrm{δ}\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)+\mathrm{δ}\left(x\left[i\right],-\right) \end{gathered}$$

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