Question

Sequence alignment. When a new gene is discovered, a standard approach to understanding its function is to look through a database of known genes and find close matches. The closeness of two genes is measured by the extent to which they are aligned. To formalize this, think of a gene as being a long string over an alphabet $\mathbf{\sum }_{\mathbf{}}\mathbf{=}\left\{A,C,G,T\right\}$. Consider two genes (strings) $\mathit{x}\mathbf{=}\mathit{A}\mathit{T}\mathit{G}\mathit{C}\mathit{C}$and $\mathit{y}\mathbf{=}\mathit{T}\mathit{A}\mathit{C}\mathit{G}\mathit{C}\mathit{A}$. An alignment of x and y is a way of matching up these two strings by writing them in columns, for instance:

$$\begin{gathered} {}_{\mathbf{-}}\mathit{A}{\mathit{T}}_{\mathbf{-}}\mathit{G}\mathit{C}\mathit{C} \\ \mathit{T}{\mathit{A}}_{\mathbf{-}}\mathit{C}\mathit{G}\mathit{C} \end{gathered}$$

Here the “_” indicates a “gap.” The characters of each string must appear in order, and each column must contain a character from at least one of the strings. The score of an alignment is specified by a scoring matrix$\mathit{\delta }$of size $\left(\left|\sum _{}\right|+1\right)\mathbf{\times }\left(\left|\sum _{}\right|+1\right)$, where the extra row and column are to accommodate gaps. For instance the preceding alignment has the following score:

$\mathit{\delta }\left(-T\right)\mathbf{+}\mathit{\delta }\left(A,A\right)\mathbf{+}\mathit{\delta }\left(T,-\right)\mathbf{+}\mathit{\delta }\left(G,G\right)\mathbf{+}\mathit{\delta }\left(C,C\right)\mathbf{+}\mathit{\delta }\left(C,A\right)$

Give a dynamic programming algorithm that takes as input two strings X[1K n] and Y {1K m} and a scoring matrix $\mathit{\delta }$and returns the highest-scoring alignment. The running time should be O(mn) .

Short answer

The dynamic algorithm that runs in O(nm) time has been obtained.

Step-by-step solution

Explain the given problem

Consider the two strings x and y with the length n and m respectively. Define a 2-Dimension array or a matrix that stores the score of aligning the string. Each value of the matrix signifies the score of aligning the sequence .

Defining the Recursive Relation

Based on he given condition, The matrix should be constructed using the following condition:

• Align the strings as it is in input but omit the last element of these strings and then align characters $x_p$and $y_p$
• The recurrence will be:$\mathrm{S}\left(\mathrm{i},\mathrm{j}\right)=\max \left(\begin{array}{c}\mathrm{S}\left(\mathrm{i}-1,\mathrm{j}\right)+\mathrm{\delta }\left(\mathrm{x}\left[\mathrm{i}\right],-\right)\\ \mathrm{S}\left(\mathrm{i},\mathrm{j}-1,\mathrm{j}\right)+\mathrm{\delta }\left(-,\mathrm{y}\left[\mathrm{i}\right]\right)\\ \mathrm{S}\left(\mathrm{i}-1,\mathrm{j}-1\right)+0\mathrm{\delta }\left(\mathrm{x}\left[\mathrm{i}\right],\mathrm{y}\left[\mathrm{j}\right]\right)\end{array}\right)$
  

Analysis of the Recurrence Relation

Since string ${\mathrm{x}}_1{\mathrm{x}}_2{\mathrm{x}}_3\mathrm{K}{\mathrm{x}}_{\mathrm{p}}$has n characters and string ${\mathrm{y}}_1{\mathrm{y}}_2{\mathrm{y}}_3\mathrm{k}{\mathrm{y}}_{\mathrm{q}}$has characters, The recursion relation will run up to $n*m$times. Hence time complexity is: O (nm).

Therefore, the dynamic algorithm that runs in O (nm) time has been obtained.