Recherche Bioinformatique Alignement

Recherche en Bioinformatique - Alignement

Alignement local

L'alignement local est un cas particuler de l'alignement global qui consiste à trouver le meilleur alignement d'un segment S avec une séquence T. Il peut être réalisé par Programmation Dynamique :

Alignement Local par Programmation Dynamique

Soient deux séquences S et T de longueurs respectives N et P (avec N < P). La recherche d'un alignement local 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] = 0 pour tout i de 1 à N

M[0,j] = 0 pour tout j de 1 à P
calcul du score optimal :

M[i,j] = max

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

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

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

0

où M[i,j] représente le score de l'alignement de S[1..i] avec T[1..j] et w est une matrice de score maximisante.

La matrice des directions est obtenue par les mêmes formules que celles définies pour l'alignement global.

Pour obtenir la position de la séquence T qui correspond au meilleur alignement possible de S avec T, on recherche la position j_max telle que la valeur M[N,j_max] = max M[N,j] en partant de j=0.
On peut alors créer un alignement local de S avec T en partant de M[N,j_max] jusqu'à obtenir une valeur M[i,j]=0.
Exemple d'application

Alignement avec gap affine

Dans la plupart des cas considérer que l'insertion d'un gap possède un coût constant ne correspond pas à un modèle réaliste. On préférera un modèle pour lequel un gap de longueur k est plus probable que k gaps de longueur 1. On utilise le modèle de gap affine car il n'augmente pas la complexité du problème d'alignement :

Modèle de gap	Formule	Complexité
linéaire :	g(k) = g.k	O(n²)
affine :	g(k) = g_op + g_ext * k	O(n²)
quelconque :	g(k) = ...	O(n³)

où g_op est la pénalité d'ouverture d'un gap et g_ext la pénalité d'extension d'un gap déjà existant. On prendra des valeurs négatives dans le cas d'un probleme de maximisation. On choisira généralement g_ext plus grand que g_op

Remarque : certains auteurs considèrent que le premier caractère composant un gap possède une pénalité de g_op + g_ext. Dans les exemples qui suivent nous considérons que le premier caractère d'un gap possède une pénalité de g_op, le suivant une pénalité de g_op + g_ext. La fonction g(k) s'écrit alors : g(k) = g_op + (k-1) . g_ext

On utilise alors 4 matrices pour le calcul du meilleur alignement :

M la matrice des coûts des meilleurs alignements qui dépend des 3 autres matrices suivantes :
D la matrice des coûts des meilleurs alignements entre x_i et y_j,
V la matrice des coûts des meilleurs alignements entre x_i et un gap
H la matrice des coûts des meilleurs alignements entre y_j et un gap

Alignement Global avec Gap Affine par Programmation Dynamique

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

initialisation :

M[0,0] = D[0,0] = H[0,0] = V[0,0] = 0

D[i,0] = H[i,0] = g_op + (i-1). g_ext pour tout i de 1 à N

D[0,j] = V[0,j] = g_op + (j-1). g_ext pour tout j de 1 à P

calcul du score optimal :

M[1,1] = max

D[1,1] = D[0,0] + w(x_i,y_j)

V[1,1] = V[0,j] - g_op

H[1,1] = H[0,j] - g_op

pour tout j >= 2, M[1,j] = max

D[1,j] = D[0,j-1] + w(x₁,y_j)

V[1,j] = V[0,j] + g_op

H[1,j] = max

V[1,j-1] + g_op

D[1,j-1] + g_op

H[1,j-1] + g_ex

pour tout i >= 2, M[i,1] = max

D[i,1] = D[i-1,0] + w(x_i,y₁)

H[i,1] = H[i,0] + g_op

V[i,1] = max

H[i-1,1] + g_op

D[i-1,1] + g_op

V[i-1,1] + g_ex

pour tout
i, j >= 2, M[i,j] = max

D[i,j] = max

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

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

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

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

V[i,j] = max

H[i-1,j] + g_op

D[i-1,1] + g_op

V[i-1,1] + g_ex

H[i,j] = max

V[i,j-1] + g_op

D[i,j-1] + g_op

H[i,j-1] + g_ex

La matrice des directions est obtenue par une technique nettement plus complexe que celle employée dans le cas de gaps linéaires.
Remarque : la majorité des algorithmes que j'ai pu trouver expliquent comment calculer M mais pas comment obtenir la matrice des directions, ce qui semble le plus important pour générer un alignement.

Exemple d'application

Problèmes liés aux gaps affines
Dans certains cas l'utilisation de gaps affine pose quelques problèmes, notamment en ce qui concerne l'alignement en début et fin de séquence mais aussi la génération d'un alignement à partir de la matrice des directions.

Supposons que nous voulions aligner les séquences suivantes :

S = { ATGT }
T = { ACCAGCTGT }

Si on utilise les paramètres :

w(a,a) = 4
w(a,b) = w(a,-) = w(-,a) = 1
pénalité d'ouverture de gap : -3
pénalité d'extension de gap : -1

on obtient l'alignement de gauche alors que celui de droite semblerait préférable. L'alignement de gauche est obtenu car il ne présente qu'un seul gap de coût -6 alors que dans le cas de droite on a deux gaps d'un coût total de -9.

Alignement généré avec les paramètres choisis car de coût supérieur à celui de droite. Alignement qui semble le plus approprié mais de coût inférieur à celui de gauche.

A-----TGT

ACCAGCTGT

---A--TGT

ACCAGCTGT

`A`	`-`	`-`	`-`	`-`	`-`	`T`	`G`	`T`
`A`	`C`	`C`	`A`	`G`	`T`	`T`	`G`	`T`

`+4`	`-3`	`-1`	`-1`	`-1`	`-1`	`+4`	`+4`	`+4`	= 9

`-`	`-`	`-`	`A`	`-`	`-`	`T`	`G`	`T`
`A`	`C`	`C`	`A`	`G`	`T`	`T`	`G`	`T`

`-3`	`-1`	`-1`	`+4`	`-3`	`-1`	`+4`	`+4`	`+4`	= 7

Supposons que nous voulions aligner les séquences suivantes :
- S = { A }
- T = { TTT }
Si on utilise les paramètres :
- w(a,a) = 4
- w(a,b) = w(a,-) = w(-,a) = 1
- pénalité d'ouverture de gap : -3
- pénalité d'extension de gap : -1

Sommaire

Jean-Michel Richer, 2004