L'algorithme de Smith&Waterman est l'un des plus usité. Il est utilisé
pour déterminer les ressemblances ou similitudes entre deux chaînes
x et y d'un même alphabet, de longueur respective m et n. Il permet d'obtenir
un alignement optimal global entre ces deux chaînes.
On utilise pour y parvenir la notion de distance entre x et y, celle-ci étant
le nombre d'opérations de substitution, insertion/suppression nécessaires
à transformer x en y. A chacune de ses opérations on associe un
coût, qui dépend du problème biologique traité.
On cherche à déterminer la transformation impliquant un nombre
d'opérations minimal, donc une distance minimale. L'algorithme présenté
est séquentiel, hors les bases de données à traiter sont
de très grande taille. Il faut souligner qu'afin d'optimiser la vitesse
de calcul, on utilise des méthodes de programmation parallèle.
On définit une fonction sub qui modélise le coût d'une
opération.
dans l'exemple, on définit sub(a,b) comme suit:
(dans notre algorithme n gaps d'affilé ont un coût de n*coût d'un gap, ce n'est pas toujours vrai, dans certains problèmes biologiques avoir plusieurs gap de suite est un cas défavorable. Le coût est alors majoré)
notons:
x=x1x2...xm
y=y1y2...yn
Cette algorithme est dynamique, on construit une matrice T des distances
entre deux chaînes x et y.
T est à deux dimensions (m+1 lignes,n+1 colonnes)
T(i,j) défini comme suit
{T(i-1,j-1)+sub(xi,yj), | |
T(i,j)=min | T(i-1,j)+sub(xi,-), |
T(i,j-1)+sub(-,yj)} |
cette algorithme à clairement une complexité en O(mn).
ex:
x=CATC
y=CGTAGTC
matrice T
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Une fois cette matrice obtenue on peut utiliser la méthode de backtracking.
Elle est employée dans la programmation dynamique afin de reconstruire
le chemin emprunté pour la résolution du problème en partant
de la fin.
On utilise l'algorithme suivant qui trace toutes les solutions :
Alignements(x,i,y,j,rep,T)=
si i!=0
alors si j!=0
alors si T(i,j)=T(i-1,j-1)+sub(xi,yj)
alors Alignements(x,i-1,y,j-1,(xi,yi)::rep,T)
si T(i,j)=T(i-1,j)+sub(xi,-)
alors Alignements(x,i-1,y,j,(xi,-)::rep,T)
si T(i,j)=T(i,j-1)+sub(-,yj)
alors Alignements(x,i,y,j-1,(-,yj)::rep,T)
sinon Alignements(x,i-1,y,0,(xi,-)::rep,T)
sinon si j!=0
alors Alignements(x,0,y,j-1,(-,yj)::rep,T)
sinon renvoie(rep)
les solutions obtenues pour x=CATC et y=CGCTAGTC :
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|