Recherche en Bioinformatique - Exemple d'alignement par paires avec gap affine

Exemple 1:

Dans cet exemple d'application, on montre comment procéder afin d'obtenir un alignment global des séquences avec gap affine :
On choisit la matrice des scores suivante : ainsi que les paramètres suivants pour les gaps : 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 T G G G T C A T i
- 0 -3 -4 -5 -6 -7 -8 -9 -10 -11 0
G -3 1 -2 0 -1 -2 -5 -6 -7 -8 1
C -4 -2 2 -1 1 0 -1 -1 -4 -5 2
A -5 0 -1 3 0 2 1 0 3 0 3
T -6 -3 4 1 4 1 6 3 2 7 4
j 0 1 2 3 4 5 6 7 8 9  
 
S/T - A T G G G T C A T i
- x 0
G 1
C 2
A 3
T 4
j 0 1 2 3 4 5 6 7 8 9  
Matrice des scores optimaux M   Matrice des directions Dir


Le meilleur alignement possède un score de M[4,9]=7.

A partir de la matrice des directions on identifie le chemin (figuré en rouge) qui correspond au meilleur alignement global.

S/T - A T G G G T C A T
- x
G
C
A
T
 
----G-CAT
ATGGGTCAT
  
Score :

- - - - G - C A T  
A T G G G T C A T  
-3 -1 -1 -1 +4 -3 +4 +4 +4 = 7

Exemple 2:

Dans cet exemple d'application, on montre comment procéder afin d'obtenir un alignment global des séquences avec gap affine :
On choisit la matrice des scores suivante : ainsi que les paramètres suivants pour les gaps : 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 A T A A i
- 0 -3 -4 -5 -6 -7 0
A -3 4 1 0 -1 -2 1
A -4 1 8 2 4 3 2
j 0 1 2 3 4 5  
 
S/T - A A T A A i
- x 0
A 1
A 2
j 0 1 2 3 4 5  
Matrice des scores optimaux M   Matrice des directions Dir
 
S/T - A A T A A i
- 0 -3 -4 -5 -6 -7 0
A -3 -6 -7 -8 -9 -10 1
A -4 1 -2 -3 -4 -5 2
j 0 1 2 3 4 5  
S/T - A A T A A i
- 0 -3 -4 -5 -6 -7 0
A -3 4 1 -3 -1 -2 1
A -4 1 8 2 4 3 2
j 0 1 2 3 4 5  
S/T - A A T A A i
- 0 -3 -4 -5 -6 -7 0
A -3 -6 1 0 -1 -2 1
A -4 -7 -2 5 4 3 2
j 0 1 2 3 4 5  
Matrice des verticales V Matrice des diagonales D Matrice des horizontales H


Il existe 3 alignements de score optimum M[2,5]=3 :
AA---
AATAA
A---A
AATAA
---AA
AATAA

Exemple 3:

Dans cet exemple d'application, on montre comment procéder afin d'obtenir un alignment global des séquences avec gap affine :
On choisit la matrice des scores suivante : ainsi que les paramètres suivants pour les gaps : 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 C A G C A C C T G T i
- 0 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 0
A -3 4 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 1
T -4 1 5 2 1 0 -1 -2 -3 -4 -2 -5 -4 2
G -5 0 2 6 3 5 2 2 0 -1 -2 2 -1 3
T -6 -1 1 3 7 4 6 3 2 1 3 0 6 4
j 0 1 2 3 4 5 6 7 8 9 10 11 12  
Matrice M
S/T - A C C A G C A C C T G T i
- x 0
A 1
T 2
G 3
G 4
Matrice des directions Dir
S/T - A C C A G C A C C T G T i
- 0 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 0
A -3 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 1
T -4 1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 2
G -5 0 2 -1 -2 -3 -4 -5 -6 -7 -5 -8 -7 3
T -6 -1 1 3 0 2 -1 -2 -3 -4 -5 -1 -4 4
j 0 1 2 3 4 5 6 7 8 9 10 11 12  
Matrice des verticales V
S/T - A C C A G C A C C T G T i
- 0 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 0
A -3 4 -2 -3 -1 -5 -6 -4 -8 -9 -10 -11 -12 1
T -4 -2 5 2 1 0 -1 -2 -3 -4 -2 -6 -4 2
G -5 -3 2 6 3 5 1 0 -1 -2 -3 2 -4 3
T -6 -4 1 3 7 4 6 3 2 1 3 -1 6 4
j 0 1 2 3 4 5 6 7 8 9 10 11 12  
Matrice des diagonales D
S/T - A C C A G C A C C T G T i
- 0 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 0
A -3 -6 - 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 1
T -4 -7 -2 2 1 0 -1 -2 -3 -4 -5 -5 -6 2
G -5 -8 -3 -1 3 2 2 1 0 -1 -2 -3 -1 3
T -6 -9 -4 -2 0 4 3 3 2 1 0 0 -1 4
j 0 1 2 3 4 5 6 7 8 9 10 11 12  
Matrice des horizontales H


Il existe 1 alignement de score optimum M[4,12]=6 mais l'algorithme permet d'identifier 2 autres alignements mais de cout inferieur :

A--------TGT
ACCAGCACCTGT
---A-----TGT
ACCAGCACCTGT
------A--TGT
ACCAGCACCTGT
Score 6 Score 4 Score 4

Jean-Michel Richer, 2004