Calculer un alignement d’après un graphe
Cet article est la suite de l’Algorithme de Needleman et Wunsch, où nous avions montré comment déterminer le score maximum, c’est-à-dire le coût minimum, d’alignement de deux séquences. Nous avions eu recours à une méthode de programmation dynamique, par la construction d’une matrice des scores. Ceci fait, restait à exhiber un alignement optimal : c’est l’objet du présent article. Nous obtiendrons ce résultat en remontant dans le graphe représenté par la matrice, selon un chemin qui va nous donner l’alignement. Reprenons la démarche de l’article.
Pour cela, on part de la case du tableau qui contient le score maximum, qui est Mm,n, et on considère ses voisines. Ici toutes les voisines contiennent la valeur 5. Comme la différence de scores est 1 dans tous les cas, et que le seul moyen d’avoir un accroissement de 1 est une concordance (toutes les autres situations donnent un accroissement nul), c’est que la case précédente était la voisine en diagonale :
G A A T T C A G T T A
0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 3
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 4 4 5 5 5 5
A 0 1 2 3 3 3 4 5 5 5 5 6
Ce qui nous donne un alignement :
A
|
A
Maintenant nous considérons la case courante et cherchons celle qui la précède : c’est la voisine avec le score maximum, soit celle de la même ligne.
G A A T T C A G T T A
0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 3
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 4 4 5 5 5 5
A 0 1 2 3 3 3 4 5 5 5 5 6
Cet alignement correspond à un gap dans la séquence n° 2 :
T A
|
_ A
Encore une fois, le prédécesseur immédiat donne un gap dans la séquence n° 2 :
G A A T T C A G T T A
0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 3
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 4 4 5 5 5 5
A 0 1 2 3 3 3 4 5 5 5 5 6
T T A
|
_ _ A
Au bout du compte :
G A A T T C A G T T A
0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 3
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 4 4 5 5 5 5
A 0 1 2 3 3 3 4 5 5 5 5 6
G A A T T C A G T T A
| | | | | |
G G A _ T C _ G _ _ A
Il y a une autre solution possible :
G A A T T C A G T T A
0 0 0 0 0 0 0 0 0 0 0 0
G 0 1 1 1 1 1 1 1 1 1 1 1
G 0 1 1 1 1 1 1 1 2 2 2 2
A 0 1 2 2 2 2 2 2 2 2 2 3
T 0 1 2 2 3 3 3 3 3 3 3 3
C 0 1 2 2 3 3 4 4 4 4 4 4
G 0 1 2 2 3 3 4 4 5 5 5 5
A 0 1 2 3 3 3 4 5 5 5 5 6
qui donne l’alignement suivant :
G _ A A T T C A G T T A
| | | | | |
G G _ A _ T C _ G _ _ A
Au sujet de cet algorithme on consultera avec profit le livre de Maxime Crochemore, Christophe Hancart et Thierry Lecroq, Algorithmique du texte, chez Vuibert.
Le programme
(module nw:alignment (export (alignment C match-bonus gap-penalty)) (import nw:matrices)) (define (alignment-col-set! align col . vals) (matrix:set! align 0 col (car vals)) (matrix:set! align 1 col (cadr vals)) (matrix:set! align 2 col (caddr vals))) (define (alignment C match-bonus gap-penalty) (let* ((ncol (matrix:ncols C)) (nlin (matrix:nlines C)) (line-length (+ nlin ncol (- 4))) (this-alignment (make-matrix 3 line-length #\space))) (let boucle ((i (- nlin 1)) (j (- ncol 1)) (p-align (- (+ nlin ncol) 5))) (if (and (= i 1) (= j 1)) 'fait (cond ((and (= j 1) (> i 1)) (alignment-col-set! this-alignment p-align #\_ #\space (matrix:ref C i 0)) (boucle (- i 1) j (- p-align 1))) ((and (= i 1) (> j 1)) (alignment-col-set! this-alignment p-align (matrix:ref C 0 j) #\space #\_) (boucle i (- j 1) (- p-align 1)) ) ((and (= (matrix:ref C i j) (+ (matrix:ref C (- i 1) (- j 1)) match-bonus)) (char=? (matrix:ref C i 0) (matrix:ref C 0 j))) (alignment-col-set! this-alignment p-align (matrix:ref C 0 j) #\| (matrix:ref C i 0)) (boucle (- i 1) (- j 1) (- p-align 1))) ((= (matrix:ref C i j) (matrix:ref C (- i 1) (- j 1))) (alignment-col-set! this-alignment p-align (matrix:ref C 0 j) #\x (matrix:ref C i 0)) (boucle (- i 1) (- j 1) (- p-align 1)) ) ((= (matrix:ref C i j) (+ (matrix:ref C (- i 1) j) gap-penalty)) (alignment-col-set! this-alignment p-align #\_ #\space (matrix:ref C i 0)) (boucle (- i 1) j (- p-align 1))) ((= (matrix:ref C i j) (+ (matrix:ref C i (- j 1)) gap-penalty)) (alignment-col-set! this-alignment p-align (matrix:ref C 0 j) #\space #\_) (boucle i (- j 1) (- p-align 1))) )) this-alignment)))This document was translated from LATEX by HEVEA.
Jeu de briques
Snake
Pacman
Bubble