7. Local alignment (without gaps) and Longest common subsequence

7. Local alignment (without gaps) and Longest common subsequence

Similarity matrix

Let X, Y be two finite alphabets, A similarity matrix for X and Y is a matrix of size \(|X|\times|Y|\), with elements from \(\mathbb{R}\cup \{-\infty\}\)

\(X=Y=\{a,b\}\), \(S_{1} =\left(\begin{array}{ccc}1 & -\infty \\ -\infty & 1 \end{array}\right)  \)

\(X=\{a,b\},Y=\{a,b,*\}\), \(S_{2} =\left(\begin{array}{ccc}1 & -\infty & 1\\ -\infty & 1 & 1\end{array}\right)  \)

The similarity of x and y with respect to a similarity matrix S for X and Y is:$$\sigma(x,y)=\sum_{i=1}^l S(x_{i},y_{i})$$

e.g. \(\sigma_{1}(aba,baa)=S_{1}(a,b)+S_{1}(b,a)+S_{1}(a,a) = -\infty\)

Local alignment (without gaps)

Given two strings \(x = x_{1},x_{2} … x_{n}\) and \(y = y_{1},y_{2}… y_{m}\), we wish to find the length of their longest common substring, that is, the largest k for which there are indices i and j with \( x_{i},x_{i+1}…x_{i +k−1}= y_{j},y_{j +1}…y_{ j +k−1}\) . Show how to do this in time \(O(mn)\).

 

e.g. \(X = \{smike\}, Y = \{milk\}\)

前两个loop

最后一个loop:

Longest common subsequence