Algorithme de Smith-Waterman

L'algorithme de Smith-Waterman est un algorithme d'alignement de séquences utilisé notamment en bioinformatique. Il est par exemple utilisé pour aligner des séquences de nucléotides ou de protéines. Cet algorithme a été inventé par Temple F. Smith et Michael Waterman en 1981. L'algorithme de Smith-Waterman est un algorithme optimal qui donne un alignement correspondant au meilleur score possible de correspondance entre les acides aminés ou les nucléotides des deux séquences. Le calcul de ce score repose sur l'utilisation de matrices de similarité ou matrices de substitution.

Alignement et score

L'algorithme de Smith et Waterman cherche à optimiser l'alignement de deux séquences biologiques qui sont traitées comme des chaînes de caractères. Pour réaliser cet alignement, on peut insérer des "trous" ou indel (symbolisés par des tirets dans l'exemple ci-dessous) dans l'une ou l'autre séquence, afin de maximiser le nombre de coïncidences de caractères entre les deux séquences. Il existe théoriquement un grand nombre possible de manières d'aligner deux séquences, ainsi que le montre l'exemple ci-dessous :

    FATCA-TY       FATCATY     FATCATY---
     || | |         || |:         |||:
    CATFAST-       CATFAST     ---CATFAST

S'agissant des séquences protéiques, il faut de plus tenir compte non-seulement des conservations strictes d'acides aminés (symbolisées par des tirets verticaux dans l'exemple ci-dessus), mais aussi des remplacements conservatifs, où un acide aminé est remplacé par un acide aminé proche sur le plan physico-chimique (symbolisés par des "deux-points" dans l'exemple ci dessus). Pour tenir compte de cela, on utilise des fonctions de score qui permettent de quantifier le résultat du remplacement de l'acide aminé a par l'acide aminé b. Ces fonctions de score sont constituées sous forme de matrices appelées matrices de similarité. Le score de l'alignement de a avec b est donné par le coefficient D(a,b) de la matrice de similarité.

Ces matrices de similarité sont complétées par une pénalité associé aux indels (insertions ou délétions) : D(a,-) = D(-,a) = Δ. Ce score Δ est négatif, pour défavoriser l'introduction d'insertions dans l'alignement. Le score d'un alignement de séquences donné est calculé à partir de la somme des scores des alignements individuels des caractères (acides aminés ou trous). L'algorithme de Smith-Waterman permet de trouver un alignement qui réalise le score optimal.

Principe et comparaison avec les autres algorithmes

Comme l'algorithme de Needleman-Wunsch auquel il est apparenté, il utilise la programmation dynamique. Contrairement à l'algorithme BLAST (Basic Local Alignment Search Tool) plus rapide, l'algorithme de Smith-Waterman garantit l'optimalité de la solution. La différence avec l'algorithme de Needleman-Wunsch est qu'alors que ce dernier recherche des alignements de séquence globaux (impliquant toute la longueur des deux séquences à aligner), l'algoritmee de Smith-Waterman recherche aussi des alignements locaux, n'impliquant que des régions ou segments des deux séquences analysées. Il permet donc par exemple de repérer des protéines qui possèdent un domaine en commun parmi d'autres domaines différents.

Comme toutes les méthodes reposant sur la programmation dynamique, l'algorithme Smith-Waterman construit la solution du problème complet sur celles de problèmes de taille plus petite. Par exemple, si on doit aligner deux séquences A et B de longueurs respectives l et n, la méthode consiste à s'appuyer sur les alignements des séquences de longueurs plus courtes. La méthode de Smith et Waterman détermine ainsi tous les meilleurs scores possibles pour les alignements des i premiers acides aminés (ou nucléotides) de A et des j premiers acides aminés (ou nucléotides) de B, pour toutes les valeurs 1 ≤ i ≤ l et toutes les valeurs 1 ≤ j ≤ n. On construit progressivement ainsi une table l x n des scores de tous les sous-alignements possibles. L'analyse de la table permet ensuite de trouver un alignement donnant le score optimal.

L'algorithme

La recherche de l'alignement optimal entre deux séquences A et B de longueurs respectives l et n se fait en deux phases distinctes :

• Le calcul de la matrice M des scores d'alignement partiel. C'est une matrice l x n, dont chaque coefficient M(i,j) donne le score de l'alignement des i premiers acides aminés (ou nucléotides) de A avec les j premiers acides aminés de B. Ce calcul se fait itérativement, à partir des scores des alignements partiels plus courts. Une fois la matrice remplie, le coefficient du coin inférieur droit de la matrice, M(l,n), donne le score de l'alignement optimal complet entre A et B.
• La construction de l'alignement à partir de la matrice M. En partant du coin inférieur droit, on remonte dans la matrice pour déterminer par quel chemin on a obtenu le score optimal. Ce chemin correspond à l'alignement optimal.

Ces deux phases sont décrites ci-dessous.

Calcul de la matrice des scores

Le principe de la construction de la matrice M(i,j) est décrit sur le schéma ci-dessous :

Principe de construction de la matrice de score dans l'algorithme de Smith-Waterman.

Le coefficient M(i,j) de la matrice correspond au score du meilleur alignement des i premiers acides aminés (ou nucléotides) de la séquence A avec les j premiers de B. On peut distinguer trois cas possibles :

• Soit le meilleur alignement se termine par la correspondance de A_i avec B_j (cas du milieu sur le schéma ci-dessus). Dans ce cas, on a M(i,j)=M(i-1,j-1)+D(A_i,B_j).
• Soit le meilleur alignement se termine par la correspondance de B_j avec un trou dans la séquence A (cas du haut sur le schéma ci-dessus). Dans ce cas on a M(i,j)=M(i,j-1)+Δ
• Soit le meilleur alignement se termine par la correspondance de A_i avec un trou dans la séquence B (cas du bas sur le schéma ci-dessus). Dans ce cas on a M(i,j)=M(i-1,j)+Δ

Avec D(A_i,B_j) le score d'alignement de l'acide aminé i de A avec l'acide aminé j de B, tiré de la matrice de similarité, et Δ, la pénalité associée à un indel.

On peut résumer la méthode de calcul de la matrice M comme suit :

$M(i,j)=\max \left\{{\begin{matrix}0\\M(i-1,j-1)+D({{A}_{i}},{{B}_{j}})\\M(i-1,j)+\Delta \\M(i,j-1)+\Delta \\\end{matrix}}\right.$

Lorsqu'il n'y a pas de régions similaires entre les deux séquences A et B, les scores obtenus sont négatifs (absence de coïncidences). Le fait de rajouter la valeur zéro comme premier terme de l'alternative permet à l'algorithme de Smith et Waterman de repérer des alignements locaux.

Construction de l'alignement

Une fois la matrice M construite, on recherche les maximums locaux dans la matrice, supérieurs à une valeur seuil, fixée par l'utilisateur. Ces maximums correspondent aux positions de fins d'alignement : Si M(x,y) est un tel maximum, cela signifie qu'il existe un alignement optimum local qui se termine par l'alignement de A_x avec B_y.

Pour déterminer cet alignement, il faut alors remonter dans la matrice M pour déterminer par quel chemin on est arrivé à ce score, c'est à dire par quelle option de l'alternative ci-dessus on a obtenu la valeur du coefficient de la matrice. Pour chaque i, j lors de la remontée :

• si on a M(i,j)=M(i-1,j-1)+D(A_i,B_j), alors on aligne A_i avec B_j et on remonte à M(i-1,j-1) ;
• si on a M(i,j)=M(i,j-1)+Δ, alors on aligne B_j avec un trou et on remonte à M(i,j-1) ;
• si on a M(i,j)=M(i-1,j)+Δ, alors on aligne A_i avec un trou et on remonte à M(i-1,j) ;
• si on a M(i,j)=0, l'alignement local est terminé.

On effectue cette remontée à partir de tous les maximums locaux M(x,y) pour obtenir tous les alignements locaux optimaux