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(xi,yj)
    M[i-1,j] + w(xi,-)
    M[i,j-1] + w(-,yj)
    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 jmax telle que la valeur M[N,jmax] = 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,jmax] 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(n2)
affine : g(k) = gop + gext * k O(n2)
quelconque : g(k) = ... O(n3)

gop est la pénalité d'ouverture d'un gap et gext 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 gext plus grand que gop

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

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

 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] = gop + (i-1). gext   pour tout i de 1 à N
    D[0,j] = V[0,j] = gop + (j-1). gext   pour tout j de 1 à P

  • calcul du score optimal :
    M[1,1] = max
    D[1,1] = D[0,0] + w(xi,yj)
    V[1,1] = V[0,j] - gop
    H[1,1] = H[0,j] - gop
    pour tout j >= 2,    M[1,j] = max
    D[1,j] = D[0,j-1] + w(x1,yj)
    V[1,j] = V[0,j] + gop
    H[1,j] = max
    V[1,j-1] + gop
    D[1,j-1] + gop
    H[1,j-1] + gex
    pour tout i >= 2,    M[i,1] = max
    D[i,1] = D[i-1,0] + w(xi,y1)
    H[i,1] = H[i,0] + gop
    V[i,1] = max
    H[i-1,1] + gop
    D[i-1,1] + gop
    V[i-1,1] + gex
    pour tout
    i, j >= 2,
       M[i,j] = max
    D[i,j] = max
    H[i-1,j-1] + w(xi,yj)
    D[i-1,j-1] + w(xi,yj)
    V[i-1,j-1] + w(xi,yj)
    = M[i-1][j-1] + w(xi,yj)
    V[i,j] = max
    H[i-1,j] + gop
    D[i-1,1] + gop
    V[i-1,1] + gex
    H[i,j] = max
    V[i,j-1] + gop
    D[i,j-1] + gop
    H[i,j-1] + gex

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.

Sommaire


Jean-Michel Richer, 2004