Page de Jean-Michel Richer

Recherche

Bioinformatique

Recherche en Bioinformatique - Alignement

Alignement par paires (Pairwise Sequence Alignment)

Définition : Définition : Problème d'alignement par paires

Soient deux séquences S₁ et S₂, une matrice de score w. Le problème d'alignement par paires consiste à déterminer un alignment de coût optimal selon w.

a) Enumération exhaustive

Ainsi que nous l'avons vu précédemment, on cherche à obtenir un alignement de coût optimal. La méthode de recherche la plus simple et qui vient tout de suite à l'esprit consiste à réaliser une énumération de tous les alignments possibles et à retenir ceux de coût optimal. Malheureusement le nombre d'alignements différents de deux séquences de même longueur n est donné par la formule :

Voici un petit programme Java qui donne le nombre d'alignements par paires.

Pour deux séquences de longueur n, voici le nombre d'alignments :

n	alignements
10	1.84e5
20	1.37e11
30	1.18e17
40	1.07e23
50	1.00e29
100	9.05e58

Il n'est donc pas envisageable de se lancer dans une énumération exhaustive des différents alignements.

b) Programmation dynamique

La Programmation Dynamique est la méthode la plus intéressante pour l'alignement de deux séquences car sa complexité temporelle et spatiale est en O(n²).

La Programmation Dynamique est appliquée à des problèmes d'optimisation pour lesquels un choix doit être fait entre plusieurs solutions possibles afin d'aboutir à une solution optimale. Le terme Programmation fait ici référence à une méthode basée sur le calcul de tableaux de valeurs.

Exemple d'application

L'algorithme d'alignement global basé sur la programmation dynamique a été mis au point par Needleman et Wunsch en 1970 [1]. Une version pour l'alignement local fut ensuite introduite par Smith et Waterman en 1981 [2].

L'algorithme

Soient deux séquences S = { x₁, x₂, ... , x_N } et T = { y₁, y₂, ... , y_M } à aligner. L'algorithme d'alignement utilise deux matrices de dimensions (N+1) x (M+1) :

M[0..N,0..P] : la matrice des scores optimaux d'alignement qui stocke le coût des meilleurs alignements intermédiaires. Au final M[N,P] contient le coût du meilleur alignement global suivant w.
Dir[0..N,0..P] : la matrice des directions qui indique la suite d'opérations d'édition à réaliser afin d'obtenir un alignement optimal.

L'algorithme se déroule en 2 étapes :

calcul des matrices M et Dir
création d'un alignement optimal par lecture de la matrice des directions

Remarque : la matrice des directions n'est pas essentielle car elle peut être déduite de la matrice des scores optimaux d'alignement, mais pour des raisons de simplicité d'écriture des algorithmes on utilise généralement cette matrice.

Première étape : calcul de M et Dir

Soient deux indices i, j tels que i,j >= 1. Supposons que nous ayons aligné les préfixes suivants par rapport à une fonction de score w :
- (1) S[1..i-1] avec T[1..j-1] de score global M[i-1,j-1],
- (2) S[1..i-1] avec T[1..j] de score global M[i-1,j],
- (3) S[1..i] avec T[1..j-1] de score global M[i,j-1].
Un alignement de S[1..i] avec T[1..j] est obtenu :
- à partir de (1) suivi d'un appariement ou un remplacement de x_i-1 avec y_j-1
  de score M[i-1,j-1] + w(x_i-1,y_j-1)
- à partir de (2) suivi d'une insertion dans T : (x_i,-)
  de score M[i-1,j] + w(x_i-1,-)
- à partir de (3) suivi d'une insertion dans S : (-,y_j)
  de score M[i,j-1] + w(-,y_j-1)
On voit donc que le calcul de M[i,j] dépend de M[i-1,j-1], M[i-1,j] et M[i,j-1] comme suit :

M[i-1][j-1] M[i-1,j]

M[i,j-1] M[i,j]

Définition : Alignement par paires par programmation dynamique

Soient deux séquences S et T de longueurs respectives N et P. La recherche d'un alignement global optimal entre S et T suivant une fonction de score w est obtenu par construction d'une matrice des scores optimaux d'alignement M[0..N,0..P] telle que :

initialisation :

M[0,0] = 0

M[i,0] = M[i-1,0] + w(x_i,-) pour tout i de 1 à N

M[0,j] = M[0,j-1] + w(-,y_j) pour tout j de 1 à P
calcul du score optimal :

M[i,j] = optimise

M[i-1,j-1] + w(x_i,y_j)

M[i-1,j] + w(x_i,-)

M[i,j-1] + w(-,y_j)

où M[i,j] représente le score de l'alignement de S[1..i] avec T[1..j] et optimise est la fonction :
- maximum si w est une matrice de score maximisante
- minimum si w est une matrice de score minimisante

La matrice des directions est obtenue par les formules suivantes :

initialisation :

Dir[0,0] = x

Dir[i,0] = pour tout i de 1 à N

Dir[0,j] = pour tout j de 1 à P
calcul des directions :

Dir[i,j] = Union

si M[i,j] = M[i-1,j-1] + w(x_i,y_j)

si M[i,j] = M[i-1,j] + w(x_i,-)

si M[i,j] = M[i,j-1] + w(-,y_j)

Deuxième étape : création d'un alignement

Une fois les matrices M et Dir obtenues, il suffit pour trouver un alignment de parcourir le chemin inverse depuis M[N,P] en remontant vers M[0,0] en se déplaçant dans l'une des trois directions possibles (Nord, Ouest ou Nord-Ouest) uniquement si le mouvement est autorisé par la matrice des directions.

On obtient donc non pas un alignement unique mais un ensemble d'alignements possibles. On peut se limiter à un seul alignement en ne choisissant qu'une direction à chaque étape et en privilégiant une direction en particulier.
Exemple d'application

Remarque finale : le problème d'alignement est un problème difficile car on ne sait pas définir en terme qualitatif ce qu'est un bon alignement. L'alignement concerne la séquence primaire or pour juger de la qualité d'un alignement il faudrait pouvoir disposer d'informations supplémentaires concernant la structure secondaire (voire tertiaire) des séquences afin d'aligner des structures de même type (on peut penser qu'il est plus judicieux d'aligner une hélice alpha avec une autre hélice alpha et non pas avec un feuillet béta).

Sommaire

$marqueur eStat\'Perso$