Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Alignement de séquences
Needleman et Wunsch, once again
Article mis en ligne le 27 mai 2008
dernière modification le 7 juin 2013

Needleman et Wunsch : le retour

Needleman et Wunsch : le retour

Laurent Bloch

Le 18 mai 2006




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
 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
 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.