© Dunod – Toute reproduction non autorisée est un délit.
51
5.2 • Comparaison de protéines homologues (algorithme global)
Ensuite, on part de la case de plus fort score (ici la dernière case en bas à droite du
tableau 5.1) et on suit les mouvements dans la table des chemins qui ont été suivis
pour maximiser les scores pour remonter à l’origine (« backtracking »). Il suffit de suivre
les cases grisées pour générer automatiquement l’alignement. Cependant, la case (N10,
I9) présente une égalité de score selon que l’on procède d’abord à une insertion ou à une
délétion. Cela indique que deux chemins sont possibles pour donner le score maximum
de cette case. Cela signifie qu’il y a deux alignements optimaux équivalents :
• si à la case de la double flèche on choisit la flèche horizontale, l’alignement
suivant est obtenu et le chemin suit les cases sur fond gris ;
MP-RCLCQR-INCYA
| || | | | | |
-PYRCKC-RNI-CIA
• si à la case de la double flèche on choisit la flèche verticale, localement le chemin
passe par les cases sur fond noir :
MP-RCLCQRIN-CYA
| || | | | | |
-PYRCKC-R-NICIA
Les deux alignements présentent le même nombre d’identités (8), d’indels (5) et de substitutions (2). Le score de chaque alignement est égal 12 = (8 × 3)+(5 × –2)+(2 × –1). Cet
algorithme garantit qu’il n’y a pas de meilleur alignement que ceux proposés, mais
dans cet exemple, il existe deux alignements équivalents alternatifs. Pour choisir entre
des alignements équivalents alternatifs, le biologiste peut avoir recours à une séquence
d’une autre espèce. La plupart des programmes d’alignement fournissent un seul alignement sans indiquer à l’utilisateur s’il y a des alignements équivalents.
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 = -2
/*PARAMETRES */
SUBSTITUT = -1
IDENT = 3
pour j=0 jqa M faire
{
pour i=0 jqa N faire
{
Matrice[i][0] = (i x INDEL)
/* initialization ligne 1 */
Matrice[0][j] = (j x INDEL)
/* 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
51
5.2 • Comparaison de protéines homologues (algorithme global)
Ensuite, on part de la case de plus fort score (ici la dernière case en bas à droite du
tableau 5.1) et on suit les mouvements dans la table des chemins qui ont été suivis
pour maximiser les scores pour remonter à l’origine (« backtracking »). Il suffit de suivre
les cases grisées pour générer automatiquement l’alignement. Cependant, la case (N10,
I9) présente une égalité de score selon que l’on procède d’abord à une insertion ou à une
délétion. Cela indique que deux chemins sont possibles pour donner le score maximum
de cette case. Cela signifie qu’il y a deux alignements optimaux équivalents :
• si à la case de la double flèche on choisit la flèche horizontale, l’alignement
suivant est obtenu et le chemin suit les cases sur fond gris ;
MP-RCLCQR-INCYA
| || | | | | |
-PYRCKC-RNI-CIA
• si à la case de la double flèche on choisit la flèche verticale, localement le chemin
passe par les cases sur fond noir :
MP-RCLCQRIN-CYA
| || | | | | |
-PYRCKC-R-NICIA
Les deux alignements présentent le même nombre d’identités (8), d’indels (5) et de substitutions (2). Le score de chaque alignement est égal 12 = (8 × 3)+(5 × –2)+(2 × –1). Cet
algorithme garantit qu’il n’y a pas de meilleur alignement que ceux proposés, mais
dans cet exemple, il existe deux alignements équivalents alternatifs. Pour choisir entre
des alignements équivalents alternatifs, le biologiste peut avoir recours à une séquence
d’une autre espèce. La plupart des programmes d’alignement fournissent un seul alignement sans indiquer à l’utilisateur s’il y a des alignements équivalents.
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 = -2
/*PARAMETRES */
SUBSTITUT = -1
IDENT = 3
pour j=0 jqa M faire
{
pour i=0 jqa N faire
{
Matrice[i][0] = (i x INDEL)
/* initialization ligne 1 */
Matrice[0][j] = (j x INDEL)
/* 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