|
Analyse
bioinformatique des séquences
La méthode de programmation dynamique Le temps de comparaison de deux séquences de longueur équivalente N est proportionnel à N². L'exploration de chaque position de chaque séquence pour la détermination éventuelle d'une insertion augmente d'un facteur 2N le temps de calcul. La programmation dynamique est un moyen qui permet de limiter cette augmentation pour conserver un temps de calcul de l'ordre de N². Elle est basée sur le fait que tous les événements sont possibles et calculables mais que la plupart sont rejetés en considérant certains critères. Needleman et Wunsch (1970) ont introduit les premiers ce type d'approche pour un problème biologique et leur algorithme reste une référence dans le domaine. L'algorithme de Needleman et Wunsch Cet algorithme a été développé initialement pour aligner deux séquences protéiques. Soit A et B deux séquences de longueur m et n. L'algorithme construit un tableau à deux dimensions (m,n) que l'on appelle matrice de comparaison. L'équation suivante résume le principe de calcul d'une case de cette matrice : S (i, j) = se (i, j) + MAX ((S (i+1,j+1)),(S (x, j+1) - P) ;(S (i+1, y) - P)) où S(i,j) est le score somme de la case d'indice i et j, se le score élémentaire de la case d'indice i et j de la matrice initiale et P la pénalité donnée pour une insertion  Le but est ensuite de trouver le meilleur alignement global, à partir de la matrice transformée. Pour cela, on établit dans la matrice un chemin qui correspond au passage des scores sommes les plus élevés, ceci en s'autorisant trois types de mouvements possibles et en prenant comme point de départ le score maximum présent dans la matrice transformée. Needleman et Wunsch nomment ce passage le chemin des scores maximum.  Les mouvements autorisés pour tracer le chemin sont : a) le mouvement diagonal qui correspond au passage de la case (i,j) à la case (i+1,j+1). C'est le mouvement que l'on privilégie. b) le mouvement vertical qui correspond au passage de la case (i,j) à la case (i,j+1), ce qui donne une insertion sur la séquence en i. c) le mouvement horizontal qui correspond au passage de la case (i,j) à la case (i+1,j), ce qui donne une insertion dans la séquence en j. Dans notre exemple, on ne considère pas de pénalités pour les insertions mais il est possible bien sûr d'incorporer celles-ci dans la méthode. Pour cela il suffit de soustraire dans le calcul de chaque score somme une pénalité en fonction de la position du score "max S(x,y)" considéré. Ainsi l'équation (3) prend la forme suivante:  où S(i,j) est le score somme de la case d'indice i et j, se le score élémentaire de la case d'indice i et j de la matrice initiale et P la pénalité donnée pour une insertion. De nombreux programmes sont déduits de ce genre d'alignement, le programme ALIGN (Dayhoff et al., 1979) en est une application directe avec l'utilisation de pénalités à deux paramètres (dépendant et indépendant de la longueur). Cependant, surtout pour les séquences nucléiques, il peut exister plusieurs chemins possibles donnant un alignement optimal. On doit alors faire un choix arbitraire car l'algorithme ne conserve qu'un pointeur de chemin pour chaque position de la matrice de comparaison. Ceci est fait généralement en privilégiant les insertions les plus courtes. Le programme GAP du logiciel GCG (Devereux et al., 1984) permet de sauvegarder des pointeurs équivalents et ainsi peut palier à ce genre de problème. |
