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.

Algorithme séquentiel et exemple:

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:

a et b appartenant à l'alphabet
sub(a,a)=0
sub(a,b)=1
sub(a,-)=sub(-,a)=1
 

(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)}

Pour construire cette matrice on utilise l'algorithme suivant:
creation_matrice(x,m,y,n)=
T(0,0)=0
pour j=1 à n
    { T(0,j)=T(0,j-1)+sub(-,yj)}
pour i=1 à m
    { T(i,0)=T(i-1,0)+sub(xi,-)
    pour j=1 à n
        {T(i,j)=min( T(i-1,j-1)+sub(xi,yj), T(i-1,j)+sub(xi,-), T(i,j-1)+sub(-,yj)) }
    }
renvoie t(m,n)

cette algorithme à clairement une complexité en O(mn).

ex:
x=CATC
y=CGTAGTC

matrice T

		C	G	C	T	A	G	T	C
	0	1	2	3	4	5	6	7	8
C	1	0	1	2	3	4	5	6	7
A	2	1	1	2	3	3	4	5	6
T	3	2	2	2	2	3	4	4	5
C	4	3	3	2	3	3	4	5	4

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 :
 

C	G	C	T	A	G	T	C
|				|		|	|
C	-	-	-	A	-	T	C

 
 

C	G	C	T	A	G	T	C
		|		|		|	|
-	-	C	-	A	-	T	C

 
on pourra tester cette algorithme avec les modules.