Nous nous intéressons ici a trouver un alignement optimal local entre une partie de x et une partie de y. La notion de distance n'est plus suffisante nous allons utiliser la formule de récurrence suivante:
| {T(i-1,j-1)+sub(xi,yj), | |
| T(i,j)=max | T(i-1,j)+sub(xi,-), |
| T(i,j-1)+sub(-,yj)} |
où les substitutions ont maintenant un coût négatif, de plus chaque case conserve une valeur positive.
Exemple:
x=ATCGTG ,y=ATGTCTGAC ,sub(a,a)=1, sub(a,b)=-m, gap=-m.
| A | T | G | T | C | T | G | A | C | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| T | 0 | 0 | 2 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 1 |
| C | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| T | 0 | 0 | 1 | 0 | 1 | 0 | 2 | 0 | 0 | 0 |
| G | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 3 | 0 | 0 |
Pour trouver un alignement local optimal il suffit maintenant de trouver la plus grande valeur dans la table T et d'effectuer le tracer arrière du chemin à partir de la case contenant cette valeur.
CTG est la plus grande aire de similitude entre ATCCTG et ATGTCTGAC .
Sous-chaînes de y ayant k différences
avec x :
Nous allons maintenant chercher toutes les sous-chaînes de y qui sont
à une distance plus petite ou égale à une valeur k
donner de x .
pour cela on initialise la première ligne du tableau avec 0.
(se qui signifie que l'insertion d'une lettre de y en début de x a un
coût nul ).
les réponses sont donner par la dernière ligne de T qui ont une
valeur plus petite ou égal à k.
exemple avec k=1 x=ATCT, y=ATGTCGTATGTGC
| A | T | G | T | C | G | T | A | T | G | T | G | C | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| T | 2 | 1 | 0 | 1 | 1 | 2 | 2 | 1 | 1 | 0 | 1 | 1 | 2 | 2 |
| C | 3 | 2 | 1 | 1 | 2 | 1 | 2 | 2 | 2 | 1 | 1 | 1 | 2 | 3 |
| T | 4 | 3 | 2 | 2 | 1 | 2 | 2 | 2 | 3 | 2 | 2 | 1 | 2 | 3 |
| différence | (x,m,y,n,k) | |
|
|
pour j<-0 à n faire |
|
| T(0,j)<-0 | ||
|
pour i<-0 à n faire
|
||
|
T(i,0)<-i+1
|
||
|
pour j<-1 à m faire
|
si xi=yj alors p<-0 | |
| sinon p<-1 | ||
| T(i,j)<-min{T(i-1,j-1)+p , | ||
| T(i,j-1)+1 , | ||
| T(i-1,j)+1 } | ||
| si T(n,j)<=k sinon renvoie(j) |
solutions:
on pourra tester ces algorithmes avec les modules.