Chapitre 5 • Alignement de séquences
54
Noter que la valeur de 10 dans la table à la fin des segments indique que
« LIBRE » dans la table est une 2
e
zone de similitude entre les deux séquences qui
conduit à l’alignement suivant la diagonale en fond noir du bas :
SEQ1 -------LIBRESEQENCE
SEQ2 SEQANCELIBRE------*****
Il faut cependant faire attention car l’alignement optimal (au sens programmation
dynamique) n’est pas obligatoirement celui qui est pertinent au niveau biologique.
Cette remarque est d’autant plus valable que les séquences ont présenté des taux
importants de mutations et que l’alignement final est peu robuste (sensibilité aux
changements de paramètres). Finalement, d’un point de vue biologique, l’alignement le plus pertinent est celui qui retrace le déroulement évolutif le plus probable.
Dans ce contexte, il est évident que la pression évolutive s’exerce sur les séquences
de façon à favoriser les mutations des bases tout en conservant les acides aminés, ce
qui traduit que le code génétique introduit un biais important dans les probabilités de
mutations des positions. Finalement en biologie, l’hypothèse d’équiprobabilité
mutationnelle des positions n’est jamais satisfaite.
5.4 ALIGNEMENTS MULTIPLES
En général, le biologiste dispose d’un grand nombre de séquences (plusieurs
centaines) et a besoin d’un alignement multiple des séquences appartenant à la
même famille afin d’identifier les résidus essentiels qui ont été préservés au cours de
l’évolution. Dans ce cas, il s’agit le plus souvent d’un alignement global qui est
recherché. La méthode de programmation dynamique peut, au moins dans le principe, s’appliquer sur N séquences. Il s’agira de calculer les scores dans un hyper
cube de dimension N. Cependant, elle est inexploitable en pratique (le nombre de
chemins menant à chaque case est égal à 2 N ) et la taille mémoire qui serait nécessaire
pour stocker les matrices deviendrait prohibitive comme le montre le tableau 5.5.
À la vue du tableau ci-dessus, il est évident que la programmation dynamique
brute n’est plus envisageable lorsque le nombre de séquences croît. Dès lors, les
alignements multiples utiliseront toujours des heuristiques conduisant à des alignements
Tableau 5.5 – Relation entre nombre (N), longueur (L) des séquences et mémoire
requise par la programmation dynamique.
Taille moyenne des séquences
N
L=100 AA
L=500 AA
L=1 000 AA
Éléments
Mémoire
Éléments
Mémoire
Éléments
Mémoire
2
100²
10 Ko
500²
250 ko
1 000²
1 Mo
3
100
3
1 Mo
500
3
125
000
Mo
1
3
1 Go
5
100 5
10 Go
500 5
30
000
Po
1
5
1 000 Po
10
100 10
100 000 Po
500 10
10 11 Po
1 000 10
10 15 Po
54
Noter que la valeur de 10 dans la table à la fin des segments indique que
« LIBRE » dans la table est une 2
e
zone de similitude entre les deux séquences qui
conduit à l’alignement suivant la diagonale en fond noir du bas :
SEQ1 -------LIBRESEQENCE
SEQ2 SEQANCELIBRE------*****
Il faut cependant faire attention car l’alignement optimal (au sens programmation
dynamique) n’est pas obligatoirement celui qui est pertinent au niveau biologique.
Cette remarque est d’autant plus valable que les séquences ont présenté des taux
importants de mutations et que l’alignement final est peu robuste (sensibilité aux
changements de paramètres). Finalement, d’un point de vue biologique, l’alignement le plus pertinent est celui qui retrace le déroulement évolutif le plus probable.
Dans ce contexte, il est évident que la pression évolutive s’exerce sur les séquences
de façon à favoriser les mutations des bases tout en conservant les acides aminés, ce
qui traduit que le code génétique introduit un biais important dans les probabilités de
mutations des positions. Finalement en biologie, l’hypothèse d’équiprobabilité
mutationnelle des positions n’est jamais satisfaite.
5.4 ALIGNEMENTS MULTIPLES
En général, le biologiste dispose d’un grand nombre de séquences (plusieurs
centaines) et a besoin d’un alignement multiple des séquences appartenant à la
même famille afin d’identifier les résidus essentiels qui ont été préservés au cours de
l’évolution. Dans ce cas, il s’agit le plus souvent d’un alignement global qui est
recherché. La méthode de programmation dynamique peut, au moins dans le principe, s’appliquer sur N séquences. Il s’agira de calculer les scores dans un hyper
cube de dimension N. Cependant, elle est inexploitable en pratique (le nombre de
chemins menant à chaque case est égal à 2 N ) et la taille mémoire qui serait nécessaire
pour stocker les matrices deviendrait prohibitive comme le montre le tableau 5.5.
À la vue du tableau ci-dessus, il est évident que la programmation dynamique
brute n’est plus envisageable lorsque le nombre de séquences croît. Dès lors, les
alignements multiples utiliseront toujours des heuristiques conduisant à des alignements
Tableau 5.5 – Relation entre nombre (N), longueur (L) des séquences et mémoire
requise par la programmation dynamique.
Taille moyenne des séquences
N
L=100 AA
L=500 AA
L=1 000 AA
Éléments
Mémoire
Éléments
Mémoire
Éléments
Mémoire
2
100²
10 Ko
500²
250 ko
1 000²
1 Mo
3
100
3
1 Mo
500
3
125
000
Mo
1
3
1 Go
5
100 5
10 Go
500 5
30
000
Po
1
5
1 000 Po
10
100 10
100 000 Po
500 10
10 11 Po
1 000 10
10 15 Po