Chapitre 5 • Alignement de séquences
56
méthodologie est que l’algorithme est de type glouton (« greedy ») car les alignements
déjà effectués ne sont pas réévalués pendant l’agrégation. La conséquence de cette
procédure est que la tendance générale est de dégrader progressivement l’alignement
en incorporant de plus en plus d’indels. C’est d’ailleurs pour cela que l’incorporation
de séquences divergentes (qui peuvent être des séquences intruses) est retardée au
maximum dans le processus.
Les méthodes les plus récentes utilisent un alignement itératif, dans lequel l’alignement est construit de manière itérative en optimisant progressivement le score global.
Les itérations peuvent être obtenues par des techniques stochastiques de type tirage
par Monte Carlo.
Le biologiste s’interroge parfois sur le
d’alignement multiple
choix du programme
à utiliser. Il n’y a pas de réponse générique à cette question car aucun programme n’est
optimal au sens informatique. Le meilleur programme est celui qui fourni un alignement pertinent dans un temps raisonnable. Un des critères est la rapidité d’exécution
qui sera prédominante si le nombre de séquences est élevé (~400). À titre d’illustration,
un alignement de 400 séquences de sous-unités d’ATP synthase de longueur moyenne
500 acides aminés prend 2 minutes à 3 minutes avec Muscle sur un ordinateur portable.
Un autre critère est la proximité des séquences à aligner. Si les séquences sont très
proches (>80% Id) et ne présentent pas de difficulté d’alignement (famille homogène),
rien ne sert d’utiliser un programme très sophistiqué (par exemple T-COFFEE qui
prend en compte les structures et qui sera donc plus lent). Le tableau 5.6 est une comparaison qualitative de différents programmes d’alignement multiple.
ANTHEPROT 6.2.62 by G. Deléage (g.deleage@ibcp.fr), IBCP, 7 passage du Vercors, 69367 Lyon cedex, FRANCE
Alignment : C:\anthepro\Data\atp.mus using Muscle
Matrix
Amino acids identity 100% >= 75 <= 50 < 50
Gap opening penalty 10 Gap extension penalty .05 Number of perfect matches 117 Identity : 20.242 %
10
20
30
40
50
60
70
|
|
|
|
|
|
|
1 GNLSPA1A3 MAELT DPT
K
I
TIR AL E E Y
D FV S KPSDTPTQEV
AT
GYV AG
V
DGIAH TGL
M N
PGC A ELL E G
TF D --- L L
T G AF D
NL ARE
2 GNLSPA0LS MSELT RPE
I
EIR AL E
A E F S TPDVASREEV
VS Y
G
DG
G
R
G
V A
TE
IARIE LPS A
TM NELL E G
RF D --- L L
T G AL D
NL VRE
3 GNLSPA0R2 MAELT SAA
I
DIE AI D
G E Y S SAD-TEREEI
VS F
G
DG
G
T
G
V A
ID
IAHVE LPS T
VM QELL P G
EF G --- L V
V G AL D
NL EHS
4 GNLSPA0PU MAELT SAN
S
I
DIQ AI E G F
E YV S TSD-TSREEV
VD
GTV AG
V
DGIAH EGL
M Q
PSV T ELL P G
EF G --- L V
V G AL D
NL EHS
5 GNLSPA0QC MAELT SAD
I
DIQ AI E
S E Y S TSD-TSREEV
VG F
G
DG
G
T
G
V A
VD
IAHVE LPS T
VM QELL P G
EF G --- L V
V G AL D
NL EHS
6 GNLSPA1E9 --MAT RVD
L
EIN IL E
K R R Q NRK-VGIENI
IE Y
G
DG
G
R
G
V V
VQ
IARII LGE S
IM GELV A G
EF E --- R I
T G ALNLESKN
7 GNLSPA1EA --MAT RVD
K
L
EIH IL E E Y
R RI Q NRK-VGIENI
VQ
GRV VG
I
DGIAR IGL
M G
GEI S ELV A G
EF E --- R I
T G AL E
NL SKN
8 GNLSPA0A3 --MVT RAD
I
EIS II E
N R R Q NRE-VKIVNT
IE Y
G
DG
G
T
G
V V
LQ
IARIH LDE A
VM GELV E G
EF E --- I I
T G AL E
NL SNN
9 GNLSPA0ZZ --MVT RAD
I
EIS II E
N R R Q NRE-VKIVNT
IE Y
G
DG
G
T
G
V V
LQ
IARIH LDE A
VM GELV E G
EF E --- I I
T G ALNLESNN
10 GNLSPA0T0 --MIN RPD
S
I
EIS IIR Q K DQD-VKVDNI
LQ
E IE Y
GTV VGDG
G
IARVY L
M G
DQV S ELL E K
EF D --- I I
T G AL E
NL NDN
11 GNLSPA0T0 --MIN RPD
I
EIS II E
S R Q Q DQD-VKIDNI
IE Y
G
DG
G
T
G
V V
LQ
IARVY LDQ S
VM GELL E K
EF D --- I I
T G AL E
NL NDN
12 GNLSPA1AX ---MQ NAH
L
EIS LI K
D K Q G DFD-AEVRTE
IE F
G
DG
G
S
S
V V
VS
IVRIH LAD F
VQ GEML P N
EF N --- F M
T G ALNLEQNS
13 GNLSPA0L2 ---MQ NST
D
L
EIS LIKQR Q EVV-SESRNE
IE F
GT
S
I V
VA DGIIR
L
IHG AD Q
VM GEMI P S
EL G --- F I
R A AL E
NL RDS
14 GNLSPA1JT ---MQ NST
L
EIS LI Q
E K R Q NVV-SEAHNE
IA F
G
DG
G
T
S
I V
VS
IIRVH LAD Q
VM GEMIALP N
R
G --- Y I
A AL E
NL RDS
15 GNLSPA0Q8 ---MQ SPS
L
EIS LI Q
G K R K DNS-VELKSE
IE F
G
DG
G
T
A
I V
VS
IVTIY LND A
VA GEMI P D
KL G --- Y L
V G ALNLNTDS
16 GNLSPA0K2 ---MQ NPS
L
EISE K R
LI S IQG EAS-ADVRNQ
IS
L
GTV V
IVR
L
TDG
IHG SDVM G
Q EML P N
EF G --- F L
T G AL E
NL RDS
17 GNLSPA1K1 ---MQ NPS
D
L
EIS LIK R N QLA-ATSRNE
VS
S IQ L
GTV VTDG
G
ITRIH L
M G
TDV Q EML P N
EF G --- F L
T G AL E
NL RDS
18 GNLSPA0LL ---ME RAE
I
EIS II E
Q R Q D EKQ-VELSET
IK Y
G
DG
G
R
G
V V
LS
IARVY VEK S
CM MELL P E
EF T HGV Y L
V G ALNLEEDN
19 GNLSPA0Q2 ---MN KPE
V
EIT II K
S K Q S EHK-IQTVDS
IE Y
G
DG
G
T
G
I I
IQ
IARVY IED E
CM GELL P D
EF N --- Y M
V G AL E
NL QDN
20 GNLSPA0RL ---MS RAE
A
I
EIS LIK Q N QSE-IEVSDV
IQ
Q IE Y
GTV VGDG
G
IARAH L
M G
DNV A ELV S G
EF N --- M L
V G AQ E
NL ENN
21 GNLSPA0RR -MSVK KAD
L
EIS II E
S K R N NLS-VDIEET
IE Y
G
DG
G
K
A
V V
IS
VANVY LKN A
VM GEMV E G
EF T --- K M
E G ALNLEESS
22 GNLSPA1BJ -MSTT RPD
V
EVS IL K
S R Q G ESE-ADVYDV
LA F
G
DG
G
T
G
V V
LQ
IARVY LSK A
AA GELL P K
EF N --- M M
V G AL E
NL EDN
23 GNLSPA0LD ---MQ SVA
V
EIS IL K
G K Q E GKE-AEVSEV
IA Y
G
DG
G
E
G
V V
IA
IARAY LDN A
VM GEMV E G
EF D --- Q M
T G ALNLEEDN
24 GNLSPA1B8 ---MG QAA
A K
I
EIS IL D K F
QI N GQD-AEVAEV
LS
GQV VGDG
G
IARVY L
Q G
DKV A EMV P G
EF G --- R M
I G VLNLETDN
Figure 5.3 – Alignement multiple de séquences de sous-unités d’ATP synthase.
56
méthodologie est que l’algorithme est de type glouton (« greedy ») car les alignements
déjà effectués ne sont pas réévalués pendant l’agrégation. La conséquence de cette
procédure est que la tendance générale est de dégrader progressivement l’alignement
en incorporant de plus en plus d’indels. C’est d’ailleurs pour cela que l’incorporation
de séquences divergentes (qui peuvent être des séquences intruses) est retardée au
maximum dans le processus.
Les méthodes les plus récentes utilisent un alignement itératif, dans lequel l’alignement est construit de manière itérative en optimisant progressivement le score global.
Les itérations peuvent être obtenues par des techniques stochastiques de type tirage
par Monte Carlo.
Le biologiste s’interroge parfois sur le
d’alignement multiple
choix du programme
à utiliser. Il n’y a pas de réponse générique à cette question car aucun programme n’est
optimal au sens informatique. Le meilleur programme est celui qui fourni un alignement pertinent dans un temps raisonnable. Un des critères est la rapidité d’exécution
qui sera prédominante si le nombre de séquences est élevé (~400). À titre d’illustration,
un alignement de 400 séquences de sous-unités d’ATP synthase de longueur moyenne
500 acides aminés prend 2 minutes à 3 minutes avec Muscle sur un ordinateur portable.
Un autre critère est la proximité des séquences à aligner. Si les séquences sont très
proches (>80% Id) et ne présentent pas de difficulté d’alignement (famille homogène),
rien ne sert d’utiliser un programme très sophistiqué (par exemple T-COFFEE qui
prend en compte les structures et qui sera donc plus lent). Le tableau 5.6 est une comparaison qualitative de différents programmes d’alignement multiple.
ANTHEPROT 6.2.62 by G. Deléage (g.deleage@ibcp.fr), IBCP, 7 passage du Vercors, 69367 Lyon cedex, FRANCE
Alignment : C:\anthepro\Data\atp.mus using Muscle
Matrix
Amino acids identity 100% >= 75 <= 50 < 50
Gap opening penalty 10 Gap extension penalty .05 Number of perfect matches 117 Identity : 20.242 %
10
20
30
40
50
60
70
|
|
|
|
|
|
|
1 GNLSPA1A3 MAELT DPT
K
I
TIR AL E E Y
D FV S KPSDTPTQEV
AT
GYV AG
V
DGIAH TGL
M N
PGC A ELL E G
TF D --- L L
T G AF D
NL ARE
2 GNLSPA0LS MSELT RPE
I
EIR AL E
A E F S TPDVASREEV
VS Y
G
DG
G
R
G
V A
TE
IARIE LPS A
TM NELL E G
RF D --- L L
T G AL D
NL VRE
3 GNLSPA0R2 MAELT SAA
I
DIE AI D
G E Y S SAD-TEREEI
VS F
G
DG
G
T
G
V A
ID
IAHVE LPS T
VM QELL P G
EF G --- L V
V G AL D
NL EHS
4 GNLSPA0PU MAELT SAN
S
I
DIQ AI E G F
E YV S TSD-TSREEV
VD
GTV AG
V
DGIAH EGL
M Q
PSV T ELL P G
EF G --- L V
V G AL D
NL EHS
5 GNLSPA0QC MAELT SAD
I
DIQ AI E
S E Y S TSD-TSREEV
VG F
G
DG
G
T
G
V A
VD
IAHVE LPS T
VM QELL P G
EF G --- L V
V G AL D
NL EHS
6 GNLSPA1E9 --MAT RVD
L
EIN IL E
K R R Q NRK-VGIENI
IE Y
G
DG
G
R
G
V V
VQ
IARII LGE S
IM GELV A G
EF E --- R I
T G ALNLESKN
7 GNLSPA1EA --MAT RVD
K
L
EIH IL E E Y
R RI Q NRK-VGIENI
VQ
GRV VG
I
DGIAR IGL
M G
GEI S ELV A G
EF E --- R I
T G AL E
NL SKN
8 GNLSPA0A3 --MVT RAD
I
EIS II E
N R R Q NRE-VKIVNT
IE Y
G
DG
G
T
G
V V
LQ
IARIH LDE A
VM GELV E G
EF E --- I I
T G AL E
NL SNN
9 GNLSPA0ZZ --MVT RAD
I
EIS II E
N R R Q NRE-VKIVNT
IE Y
G
DG
G
T
G
V V
LQ
IARIH LDE A
VM GELV E G
EF E --- I I
T G ALNLESNN
10 GNLSPA0T0 --MIN RPD
S
I
EIS IIR Q K DQD-VKVDNI
LQ
E IE Y
GTV VGDG
G
IARVY L
M G
DQV S ELL E K
EF D --- I I
T G AL E
NL NDN
11 GNLSPA0T0 --MIN RPD
I
EIS II E
S R Q Q DQD-VKIDNI
IE Y
G
DG
G
T
G
V V
LQ
IARVY LDQ S
VM GELL E K
EF D --- I I
T G AL E
NL NDN
12 GNLSPA1AX ---MQ NAH
L
EIS LI K
D K Q G DFD-AEVRTE
IE F
G
DG
G
S
S
V V
VS
IVRIH LAD F
VQ GEML P N
EF N --- F M
T G ALNLEQNS
13 GNLSPA0L2 ---MQ NST
D
L
EIS LIKQR Q EVV-SESRNE
IE F
GT
S
I V
VA DGIIR
L
IHG AD Q
VM GEMI P S
EL G --- F I
R A AL E
NL RDS
14 GNLSPA1JT ---MQ NST
L
EIS LI Q
E K R Q NVV-SEAHNE
IA F
G
DG
G
T
S
I V
VS
IIRVH LAD Q
VM GEMIALP N
R
G --- Y I
A AL E
NL RDS
15 GNLSPA0Q8 ---MQ SPS
L
EIS LI Q
G K R K DNS-VELKSE
IE F
G
DG
G
T
A
I V
VS
IVTIY LND A
VA GEMI P D
KL G --- Y L
V G ALNLNTDS
16 GNLSPA0K2 ---MQ NPS
L
EISE K R
LI S IQG EAS-ADVRNQ
IS
L
GTV V
IVR
L
TDG
IHG SDVM G
Q EML P N
EF G --- F L
T G AL E
NL RDS
17 GNLSPA1K1 ---MQ NPS
D
L
EIS LIK R N QLA-ATSRNE
VS
S IQ L
GTV VTDG
G
ITRIH L
M G
TDV Q EML P N
EF G --- F L
T G AL E
NL RDS
18 GNLSPA0LL ---ME RAE
I
EIS II E
Q R Q D EKQ-VELSET
IK Y
G
DG
G
R
G
V V
LS
IARVY VEK S
CM MELL P E
EF T HGV Y L
V G ALNLEEDN
19 GNLSPA0Q2 ---MN KPE
V
EIT II K
S K Q S EHK-IQTVDS
IE Y
G
DG
G
T
G
I I
IQ
IARVY IED E
CM GELL P D
EF N --- Y M
V G AL E
NL QDN
20 GNLSPA0RL ---MS RAE
A
I
EIS LIK Q N QSE-IEVSDV
IQ
Q IE Y
GTV VGDG
G
IARAH L
M G
DNV A ELV S G
EF N --- M L
V G AQ E
NL ENN
21 GNLSPA0RR -MSVK KAD
L
EIS II E
S K R N NLS-VDIEET
IE Y
G
DG
G
K
A
V V
IS
VANVY LKN A
VM GEMV E G
EF T --- K M
E G ALNLEESS
22 GNLSPA1BJ -MSTT RPD
V
EVS IL K
S R Q G ESE-ADVYDV
LA F
G
DG
G
T
G
V V
LQ
IARVY LSK A
AA GELL P K
EF N --- M M
V G AL E
NL EDN
23 GNLSPA0LD ---MQ SVA
V
EIS IL K
G K Q E GKE-AEVSEV
IA Y
G
DG
G
E
G
V V
IA
IARAY LDN A
VM GEMV E G
EF D --- Q M
T G ALNLEEDN
24 GNLSPA1B8 ---MG QAA
A K
I
EIS IL D K F
QI N GQD-AEVAEV
LS
GQV VGDG
G
IARVY L
Q G
DKV A EMV P G
EF G --- R M
I G VLNLETDN
Figure 5.3 – Alignement multiple de séquences de sous-unités d’ATP synthase.