Chapitre 5 • Alignement de séquences
52
SUBS[S1[i],S2[j]]=SUBSTITUT si S1[i]<>S2[j]*/
| Matrice[i-1][j] + INDEL
}
}
Cet algorithme présente une complexité en O(n 2 ).
5.3 MEILLEUR
SÉQUENCES
CHEVAUCHEMENT ENTRE
(ALGORITHME LOCAL)
Au lieu de considérer chaque séquence globalement, cet algorithme compare des
segments de toutes longueurs (suffixes de
dans les deux séquences) et retient
i et j
celui qui maximise le score de similitude sur les segments. La solution du problème
de l’alignement local consiste à trouver le score maximal des suffixes sur tous les
indices i et j des deux séquences. La première ligne et la première colonne sont
initialisées à 0 permettant ainsi à l’alignement de commencer n’importe où sur une
des deux séquences. Un alignement local sera représenté par un chemin dans le
tableau qui continue tant que le score est positif.
tableaux : S1[N], S2[M], Matrice[N][M]
S1 <-- séquence 1
/* N caractères d’indice i */
S2 <-- séquence 2
/* M caractères d’indice j */
INDEL = -1
/* PARAMETRES */
SUBSTITUT = 0
IDENT = 2
pour j=0 jqa M faire
{
pour i=0 jqa N faire
{
Matrice[i][0] = 0)
/* initialization ligne 1 */
Matrice[0][j] = 0
/* initialization colonne 1 */
}
}
pour j=1 jqa M faire
{
pour i=1 jqa N faire
{
| Matrice[i][j-1]
+ INDEL
Matrice[i][j] <- MAX| Matrice[i-1][j-1] + SUBS[S1[i]],[S2[j]]
/*SUBS[S1[i],S2[j]]=IDENT si S1[i]=S2[j] ou
SUBS[S1[i],S2[j]]=SUBSTITUT si S1[i]<>S2[j]*/
| Matrice[i-1][j]
+ INDEL
}
}
Soit les deux séquences : LIBRESEQENCE SEQANCELIBRE.
et