Question

Local sequence alignment. Often two DNA sequences are significantly different, but contain regions that are very similar and are highly conserved. Design an algorithm that takes an input two strings $\mathit{x}\left[1Kn\right]$and $\mathit{y}\left[1Km\right]$and a scoring matrix $\delta$(as defined in Exercise 6.26), and outputs substrings $\mathit{x}\mathbf{\text{'}}\mathbf{}\mathit{a}\mathit{n}\mathit{d}\mathbf{}\mathit{y}\mathbf{\text{'}}$of x and y respectively, that have the highest-scoring alignment over all pairs of such substrings. Your algorithm should take time $\mathit{O}\left(mn\right)$.

Short answer

The complexity of the program is $O\left(mn\right)$

Step-by-step solution

Local Sequence Alignment

The total scoring alignment is the cost of editing the strings using insertion, deletion, or gap penalties.

Suppose the given strings are $x=x_1,x_2,K{x}_{n}andy=y_1,y_2,K{y}_m$.

The first step is to determine the similarity score of the elements$\delta \left(a,b\right)$ and the gap penalty of length k.

In the next step the first row and column of the scoring matrix M of size role="math" localid="1658918665081" $\left(n+1\right)$times $\left(m+1\right)$to zero Then in the next step, the scoring matrix is filled.

Then tracing back from the highest score to zero in the scoring matrix gives the best alignment.

Step 2:Give Algorithm

Algorithm:

The algorithm can be written as given below:

$\delta \left(a,b\right)$- score

$G_k$- gap penalty of length k

$M\left[n+1\right]\left[m+1\right]$- scoring matrix

for $o=0ton$

$M\left[0\right]\left[1\right]=0$

for o=0 to m

$M\left[1\right]\left[0\right]=0$

for o=1 to n

for p=1 to n

$$\begin{gathered} M\left[o\right]\left[p\right]=max\left[1\right] \\ M\left[o-1\right]\left[p-1\right]+\delta \left(a_o,b_p\right) \\ max\left\{k_1,M\left[o-k\right]\left[p\right]-G_k\right\} \\ max\left\{l_1,M\left[o\right]\left[p-1\right]-G_k\right\} \end{gathered}$$

Traceback from highest alignment score to 0.

Step 3:Explain Algorithm

Explanation:

$M\left[o\right]\left[p\right]$is a optimal score of aligning.

There are only a polynomial number of subproblems.

Every subproblems can be solved easily by solving smaller subproblems.

See, in step-7 we have three cases. first case is $x_o=y_p$second case is, $x_o$ aligns to a gap and, third case is $y_p$aligns to a gap.

The calculated scoring matrix is of size

So, the complexity of the program is $O\left(nm\right)o=$