Recherche
Bioinformatique

 
Recherche en Bioinformatique - Alignement

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
    -CATTG-C
    ACA--GTC

  • Alignement n°2 :

    S/T - A C A G T C
    - x
    C
    A
    T
    T
    G
    C
    -CAT-TGC
    ACA-GT-C

  • Alignement n°3 :

    S/T - A C A G T C
    - x
    C
    A
    T
    T
    G
    C
    		 
    -CATTGC
    ACAGT-C

  • Alignement n°4 :

    S/T - A C A G T C
    - x
    C
    A
    T
    T
    G
    C
    		 
    -CA-TTGC
    ACAG-T-C

  • Alignement n°5 :

    S/T - A C A G T C
    - x
    C
    A
    T
    T
    G
    C
    		 
    -CA-TTGC
    ACAGT--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) :

-CATTGC
ACAGT-C

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
© 2006-2024 Jean-Michel Richer
marqueur eStat\'Perso