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 M_m,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 :

Ce qui nous donne un alignement :

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.

Cet alignement correspond à un gap dans la séquence n° 2 :

Encore une fois, le prédécesseur immédiat donne un gap dans la
séquence n° 2 :

Au bout du compte :

Il y a une autre solution possible :

qui donne l’alignement suivant :

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

This document was translated from L^AT_EX by H^EV^EA.