|
Recherche en Bioinformatique - Exemple d'alignement global par paires |
Dans cet exemple d'application, on étudie l'influence de deux matrices de score (la matrice identité et la matrice inverse de l'identité) sur l'alignment global des séquences :
- S = { CATTGC }
- T = { ACAGTC }
Utilisation de la matrice Identité 
La matrice des scores est telle que :
- w(a,a) = 1
- w(a,b) = w(a,-) = w(-,a) = 0
Il s'agit d'une matrice de score maximisante, on utilisera donc la fonction max pour l'algorithme de Programmation Dynamique.
Aprés calcul de la matrice des scores optimaux d'alignements et de la matrice des directions, on obtient le résultat suivant :
|
Matrices
|
| |
| S/T |
- |
A |
C |
A |
G |
T |
C |
i |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| C |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
| A |
0 |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
| T |
0 |
1 |
1 |
2 |
2 |
2 |
2 |
3 |
| T |
0 |
1 |
1 |
2 |
2 |
3 |
3 |
4 |
| G |
0 |
1 |
1 |
2 |
3 |
3 |
3 |
5 |
| C |
0 |
1 |
2 |
2 |
3 |
3 |
4 |
6 |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
| |
| S/T |
- |
A |
C |
A |
G |
T |
C |
i |
| - |
x |
 |
 |
|
|
|
|
0 |
| C |
 |
 |
 |
|
|
|
 |
1 |
| A |
|
 |
 |
|
|
|
|
2 |
| T |
|
|
|
 |
 |
|
|
3 |
| T |
|
|
|
|
|
 |
|
4 |
| G |
|
|
|
|
|
 |
|
5 |
| C |
|
|
|
|
|
|
|
6 |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
Matrice des scores optimaux M
| |
Matrice des directions Dir
|
Le score M[6,6]=4 indique que tout alignement optimal comportera 4 appariements.
A partir de la matrice des directions on peut identifier 5 chemins différents (soit 5 alignements) figurés en rouge dans la matrice des directions. Détaillons chacun de ces alignements :
- Alignement n°1 :
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
x |
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| A |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
 |
|
| G |
|
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| |
|
- Alignement n°2 :
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
x |
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| A |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| G |
|
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| |
|
- Alignement n°3 :
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
x |
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| A |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| G |
|
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| |
|
- Alignement n°4 :
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
x |
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| A |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| G |
|
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| |
|
- Alignement n°5 :
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
x |
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| A |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| G |
|
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| |
|
Utilisation de la matrice Inverse de l'Identité
La matrice des scores est telle que :
- w(a,a) = 0
- w(a,b) = w(a,-) = w(-,a) = 1
Il s'agit d'une matrice de score minimisante, on utilisera donc la fonction min pour l'algorithme de Programmation Dynamique.
Aprés calcul de la matrice des scores optimaux d'alignements et de la matrice des directions, on obtient le résultat suivant :
|
Matrices
|
| |
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
| C |
1 |
1 |
1 |
2 |
3 |
4 |
5 |
| A |
2 |
1 |
2 |
1 |
2 |
3 |
4 |
| T |
3 |
2 |
2 |
2 |
2 |
2 |
3 |
| T |
4 |
3 |
3 |
3 |
3 |
2 |
3 |
| G |
5 |
4 |
4 |
4 |
3 |
3 |
3 |
| C |
6 |
5 |
4 |
5 |
4 |
4 |
3 |
| |
| S/T |
- |
A |
C |
A |
G |
T |
C |
| - |
x |
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
| A |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| T |
|
|
|
|
|
|
|
| G |
|
|
|
|
|
|
|
| C |
|
|
|
|
|
|
|
|
|
Matrice des scores optimaux M
| |
Matrice des directions Dir
|
Le score M[6,6]=3 indique que tout alignement optimal comportera 3 subsitutions ou insertions de gaps.
On obtient ici qu'un seul alignement composé de deux insertions de gap et d'une substitution (T,G) :
Comme on peut le voir sur cet exemple :
- la matrice de score Identité maximise les appariements au détriment de la cohérence de la séquence ce qui à pour conséquence l'introduction parfois inopportune de gaps à certaines positions de la séquence. On peut remédier à ce problème en utilisant un alignement avec gap affine.
- par contre, la matrice de score Inverse de l'Identité tend à minimiser l'insertion de gaps
Jean-Michel Richer, 2004