|
Recherche en Bioinformatique - Alignement
Dans cet exemple d'application, on montre comment procéder afin d'obtenir un alignment local des séquences :
- S = { TGA }
- T = { TATGAACTA }
On choisit la matrice des scores identité qui est telle que :
- w(a,a) = 1
- w(a,b) = w(a,-) = w(-,a) = 0
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 |
- |
T |
A |
T |
G |
C |
A |
C |
T |
A |
i |
| - |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| T |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| G |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
2 |
2 |
2 |
| A |
0 |
1 |
1 |
1 |
2 |
2 |
3 |
3 |
3 |
3 |
3 |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
| |
| S/T |
- |
T |
A |
T |
G |
C |
A |
C |
T |
A |
i |
| - |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
0 |
| T |
x |
 |
 |
|
|
|
|
|
|
|
1 |
| G |
x |
 |
 |
|
|
|
|
|
|
|
2 |
| A |
x |
|
|
|
|
|
|
|
|
|
3 |
| j |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
Matrice des scores optimaux M
| |
Matrice des directions Dir
|
On cherche la valeur jmax telle que
M[3,jmax] = max M[3,j], en partant de j=0.
On trouve jmax = 6 et M[3,jmax]=3
A partir de la matrice des directions on identifie le chemin (figuré en rouge) qui correspond au meilleur alignement local.
| S/T |
- |
T |
A |
T |
G |
C |
A |
C |
T |
A |
| - |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
| T |
x |
|
|
 |
|
|
|
|
|
|
| G |
x |
|
|
|
|
 |
|
|
|
|
| A |
x |
|
|
|
|
|
|
|
|
|
| |
|
|
