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\}$$