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 :
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) |
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 :
|
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 :
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. |
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.
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Jean-Michel Richer, 2004