Alignement multiple

Le contexte
Lorsque lon compare une squence contre une banque par BLAST, un grand nombre de squences similaires peuvent tre donnes en sortie. Cela nous permet de poser des hypothses sur notre squence inconnue (Fonction, ): On peut ensuite regarder les alignements 2 2 entre les squences similaires trouves dans la banque et la squence query:

Le contexte
Mais, comment comparer toutes ces squences et tudier leur relations ?

Comparer les squences en une seule fois : Alignement multiple

Un alignement multiple permet dtudier un groupe de protines ou de gnes apparents, afin dtablir des relations dvolution et mettre en vidence des motifs communs, jouant un rle dans la fonction ou la structure de ces protines homologues.

But de l'alignement multiple

Trouver des protines caractristiques communes une famille de

Relier la squence la structure et la fonction Caractriser les rgions conserves et le rgions variables Dduire des contraintes de structures pour les ARN Diffrencier entre gnes orthologues et gnes paralogues Construire larbre considres phylogntique des squences homologues

Exemple dalignement multiple

Permet rapidement de retrouver les acides amins strictement conservs dans toutes les squences homologues, jouant souvent un rle direct dans la fonction.

Un alignement multiple se conoit partir de 3 squences et peut concerner jusqu plusieurs centaines de squences.
5

Dfinition de lalignement multiple

Entre : k squences (pas forcement la mme longueur) *************** ********** ************ *********** Sortie: un tableau contenant les k squences, avec des indels ***********-**** ***--**-**-**-** ***-********--** *****---**-*****

Dmarche
Alignement 2 2
2 squences quelconques Dtecter une similarit syntaxique

Il y a-t-il une fonction commune ?

Alignement multiple
Famille de squences avec la mme fonction

A quelle conservation syntaxique cela correspond-il ?

7

Exemple:
Voici un alignement multiple de squences protiques:
TYY1_HUMAN TF3B_BUFAM ZN77_HUMAN ZN76_HUMAN P44_XENBO TSH_DROME XFIN_XENLA EVI1_HUMAN TRA1_CAEEL TF3A_BUFAM SRYC_DROME ZG2-9_XENL ZG58_XENLA YKQ8_CAEEL BASO_HUMAN SUHW_DROAN ZN10_HUMAN P43_XENBO IKAR_MOUSE YVCPFDGCNKKFAQSTNLKSHIL--THYRCPRENCDRTYTTKFNLKSHIL--TFH YTCPEPHCGRGFTSATNYKNHVR--IHFRCGYKGCGRLYTTAHHLKVHER--AHYRCSYEDCQTVSPTWTALQTHLK--KHFRCVW--CKQSFPTLEALTTHMKDSKHFRCSE--CSRSFTHNSDLTAHMR--KHYRCKY--CDRSFSISSNLQRHVRN-IHYKCEFADCEKAFSNASDRAKHQNR-THCKCETENCNLAFTTASNMRLHFKR-AHFKCNY--CPRDFTNFPNWLKHTRR-RHFVCTV--CGKTYKYKHGLNTHLHS-H-FVCTE--CNLSFAGLANLRSHQHL-H-YKCTV--CRKDISSSESLRTHMFK-QHH FQCDI--CKKTFKNACSVKIHHKN-MHYACKI--CGKDFTRSYHLKRHQKY-SSC YKCNQ--CGIIFSQNSPFIVHQI--AHLKCSVPGCKRSFRKKRALRIHVS--EHFECNM--CGYHSQDRYEFSSHITRGEH25 26 25 25 25 25 23 24 26 26 24 23 23 25 24 25 23 25 25

Exemple:
Regardons les rsidus totalement conservs:
TYY1_HUMAN TF3B_BUFAM ZN77_HUMAN ZN76_HUMAN P44_XENBO TSH_DROME XFIN_XENLA EVI1_HUMAN TRA1_CAEEL TF3A_BUFAM SRYC_DROME ZG2-9_XENL ZG58_XENLA YKQ8_CAEEL BASO_HUMAN SUHW_DROAN ZN10_HUMAN P43_XENBO IKAR_MOUSE YVCPFDGCNKKFAQSTNLKSHIL--THYRCPRENCDRTYTTKFNLKSHIL--TFH YTCPEPHCGRGFTSATNYKNHVR--IHFRCGYKGCGRLYTTAHHLKVHER--AHYRCSYEDCQTVSPTWTALQTHLK--KHFRCVW--CKQSFPTLEALTTHMKDSKHFRCSE--CSRSFTHNSDLTAHMR--KHYRCKY--CDRSFSISSNLQRHVRN-IHYKCEFADCEKAFSNASDRAKHQNR-THCKCETENCNLAFTTASNMRLHFKR-AHFKCNY--CPRDFTNFPNWLKHTRR-RHFVCTV--CGKTYKYKHGLNTHLHS-H-FVCTE--CNLSFAGLANLRSHQHL-H-YKCTV--CRKDISSSESLRTHMFK-QHH FQCDI--CKKTFKNACSVKIHHKN-MHYACKI--CGKDFTRSYHLKRHQKY-SSC YKCNQ--CGIIFSQNSPFIVHQI--AHLKCSVPGCKRSFRKKRALRIHVS--EHFECNM--CGYHSQDRYEFSSHITRGEH25 26 25 25 25 25 23 24 26 26 24 23 23 25 24 25 23 25 25

On peut tablir une carte par position des rsidus conserves : WebLogo : http://weblogo.berkeley.edu/logo.cgi
9

Notion de squence consensus

A partir de lalignement multiple, on peut dterminer la squence consensus: On attribut chaque position lacide amin ou le nuclotide qui est le plus souvent retrouv (totalement conserv ou partiellement).
130 140 150 160 170 180 | | | | | | TILGPPGSVYEGGVFFLDITFSSDYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TILGPPGSVYEGGVFFLDIHFSPEYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGAFFLTIDFPTEYPFKPPKVEFTTRIYHPNVNSNGSICLDILRSQWSP TIMGPPDSAYQGGVFFLTVHFPTDYPFKPPKIAFTTKIYHPNINSNGSICLDILRSQWSP TIMGPPDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPGDSPYSGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP TIMGPSDSPYAGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP VIFGPDDTPWDGGTFKLTLQFTEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP IIFGPQETPFEDGTFKLSLEFTEEYPNKPPTVKFISKMFHPNVYADGSICLDILQNRWSP VIFGPEGTPFEDGTFKLVIEFSEEYPNKPPTVRFLSKMFHPNVYADGSICLDILQNRWSP VIIGPSDTPFEDGTFRLLLSFDEQYPNKPPQVKFISEMFHPNVYASGELCLDILQNRWSP VIIGPADTPFEDGTFKLVLSFDEQYPNKPPLVKFVSTMFHPNVYANGELCLDILQNRWSP *:** : : .*.* * : * :** *** : * : ::* *: :.* :*****:..***

UB2E3_MOUSE UBCD2_DROME UB2D2_HUMAN UB2D3_HUMAN UB2D4_RAT UB2D1_HUMAN UBCD1_DROME UBC1_COLGL UBC1_MAGGR UBC2_ARATH UBC2_MEDSA UBC1_ARATH UBC2_WHEAT UBC1_CAEEL UBE2B_HUMAN UBC2_CANAL UBC2_SCHPO

10

Notion de squence consensus

A partir de lalignement multiple, on peut dterminer la squence consensus: On attribut chaque position lacide amin ou le nuclotide qui est le plus souvent retrouv (totalement conserv ou partiellement).
130 140 150 160 170 180 | | | | | | TILGPPGSVYEGGVFFLDITFSSDYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TILGPPGSVYEGGVFFLDIHFSPEYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGAFFLTIDFPTEYPFKPPKVEFTTRIYHPNVNSNGSICLDILRSQWSP TIMGPPDSAYQGGVFFLTVHFPTDYPFKPPKIAFTTKIYHPNINSNGSICLDILRSQWSP A cette position, on TIMGPPDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP trouve 9 T, 7 V et 1 TIMGPGDSPYSGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP TIMGPSDSPYAGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP I, T est donc la VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP lettre consensus VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP (majoritaire) VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP VIFGPDDTPWDGGTFKLTLQFTEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP IIFGPQETPFEDGTFKLSLEFTEEYPNKPPTVKFISKMFHPNVYADGSICLDILQNRWSP VIFGPEGTPFEDGTFKLVIEFSEEYPNKPPTVRFLSKMFHPNVYADGSICLDILQNRWSP VIIGPSDTPFEDGTFRLLLSFDEQYPNKPPQVKFISEMFHPNVYASGELCLDILQNRWSP VIIGPADTPFEDGTFKLVLSFDEQYPNKPPLVKFVSTMFHPNVYANGELCLDILQNRWSP *:** : : .*.* * : * :** *** : * : ::* *: :.* :*****:..***

UB2E3_MOUSE UBCD2_DROME UB2D2_HUMAN UB2D3_HUMAN UB2D4_RAT UB2D1_HUMAN UBCD1_DROME UBC1_COLGL UBC1_MAGGR UBC2_ARATH UBC2_MEDSA UBC1_ARATH UBC2_WHEAT UBC1_CAEEL UBE2B_HUMAN UBC2_CANAL UBC2_SCHPO Prim.cons.

11

Notion de squence consensus

A partir de lalignement multiple, on peut dterminer la squence consensus: On attribut chaque position lacide amin ou le nuclotide qui est le plus souvent retrouv (totalement conserv ou partiellement).
130 140 150 160 170 180 | | | | | | TILGPPGSVYEGGVFFLDITFSSDYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TILGPPGSVYEGGVFFLDIHFSPEYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGAFFLTIDFPTEYPFKPPKVEFTTRIYHPNVNSNGSICLDILRSQWSP TIMGPPDSAYQGGVFFLTVHFPTDYPFKPPKIAFTTKIYHPNINSNGSICLDILRSQWSP TIMGPPDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPGDSPYSGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP A cette position, on TIMGPSDSPYAGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP trouve 17 P donc P VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP est le consensus VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP (unanimit) VIFGPDDTPWDGGTFKLTLQFTEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP IIFGPQETPFEDGTFKLSLEFTEEYPNKPPTVKFISKMFHPNVYADGSICLDILQNRWSP VIFGPEGTPFEDGTFKLVIEFSEEYPNKPPTVRFLSKMFHPNVYADGSICLDILQNRWSP VIIGPSDTPFEDGTFRLLLSFDEQYPNKPPQVKFISEMFHPNVYASGELCLDILQNRWSP VIIGPADTPFEDGTFKLVLSFDEQYPNKPPLVKFVSTMFHPNVYANGELCLDILQNRWSP *:** : : .*.* * : * :** *** : * : ::* *: :.* :*****:..*** TIMGP

UB2E3_MOUSE UBCD2_DROME UB2D2_HUMAN UB2D3_HUMAN UB2D4_RAT UB2D1_HUMAN UBCD1_DROME UBC1_COLGL UBC1_MAGGR UBC2_ARATH UBC2_MEDSA UBC1_ARATH UBC2_WHEAT UBC1_CAEEL UBE2B_HUMAN UBC2_CANAL UBC2_SCHPO Prim.cons.

12

Notion de squence consensus

A partir de lalignement multiple, on peut dterminer la squence consensus: On attribut chaque position lacide amin ou le nuclotide qui est le plus souvent retrouv (totalement conserv ou partiellement).
130 140 150 160 170 180 | | | | | | TILGPPGSVYEGGVFFLDITFSSDYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TILGPPGSVYEGGVFFLDIHFSPEYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGAFFLTIDFPTEYPFKPPKVEFTTRIYHPNVNSNGSICLDILRSQWSP TIMGPPDSAYQGGVFFLTVHFPTDYPFKPPKIAFTTKIYHPNINSNGSICLDILRSQWSP TIMGPPDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP A cette position, on TIMGPGDSPYSGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP TIMGPSDSPYAGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP trouve 4 P, 3 N, 4 VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP D, 2 S, 1 Q, E et A VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP Pas de consensus qui VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP sort VIFGPDDTPWDGGTFKLTLQFTEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP IIFGPQETPFEDGTFKLSLEFTEEYPNKPPTVKFISKMFHPNVYADGSICLDILQNRWSP VIFGPEGTPFEDGTFKLVIEFSEEYPNKPPTVRFLSKMFHPNVYADGSICLDILQNRWSP VIIGPSDTPFEDGTFRLLLSFDEQYPNKPPQVKFISEMFHPNVYASGELCLDILQNRWSP VIIGPADTPFEDGTFKLVLSFDEQYPNKPPLVKFVSTMFHPNVYANGELCLDILQNRWSP *:** : : .*.* * : * :** *** : * : ::* *: :.* :*****:..*** TIMGP2

UB2E3_MOUSE UBCD2_DROME UB2D2_HUMAN UB2D3_HUMAN UB2D4_RAT UB2D1_HUMAN UBCD1_DROME UBC1_COLGL UBC1_MAGGR UBC2_ARATH UBC2_MEDSA UBC1_ARATH UBC2_WHEAT UBC1_CAEEL UBE2B_HUMAN UBC2_CANAL UBC2_SCHPO Prim.cons.

13

Notion de squence consensus

A partir de lalignement multiple, on peut dterminer la squence consensus:
130 140 150 160 170 180 | | | | | | TILGPPGSVYEGGVFFLDITFSSDYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TILGPPGSVYEGGVFFLDIHFSPEYPFKPPKVTFRTRIYHCNINSQGVICLDILKDNWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPNDSPYQGGAFFLTIDFPTEYPFKPPKVEFTTRIYHPNVNSNGSICLDILRSQWSP TIMGPPDSAYQGGVFFLTVHFPTDYPFKPPKIAFTTKIYHPNINSNGSICLDILRSQWSP TIMGPPDSPYQGGVFFLTIHFPTDYPFKPPKVAFTTRIYHPNINSNGSICLDILRSQWSP TIMGPGDSPYSGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP A cette position, on TIMGPSDSPYAGGVFFLAIHFPTDYPFKPPKVNFTTRIYHPNINSNGSICLDILRDQWSP trouve 13 S, 2 V et VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP 2 E, donc S est la VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP lettre consensus VIFGPDDTPWDGGTFKLSLQFSEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP VIFGPDDTPWDGGTFKLTLQFTEDYPNKPPTVRFVSRMFHPNIYADGSICLDILQNQWSP IIFGPQETPFEDGTFKLSLEFTEEYPNKPPTVKFISKMFHPNVYADGSICLDILQNRWSP VIFGPEGTPFEDGTFKLVIEFSEEYPNKPPTVRFLSKMFHPNVYADGSICLDILQNRWSP VIIGPSDTPFEDGTFRLLLSFDEQYPNKPPQVKFISEMFHPNVYASGELCLDILQNRWSP VIIGPADTPFEDGTFKLVLSFDEQYPNKPPLVKFVSTMFHPNVYANGELCLDILQNRWSP *:** : : .*.* * : * :** *** : * : ::* *: :.* :*****:..*** TIMGP2DSPYEGG2FFLTIHFPEDYPFKPPKVRFTTRIYHPNINSNGSICLDILQNQWSP

UB2E3_MOUSE UBCD2_DROME UB2D2_HUMAN UB2D3_HUMAN UB2D4_RAT UB2D1_HUMAN UBCD1_DROME UBC1_COLGL UBC1_MAGGR UBC2_ARATH UBC2_MEDSA UBC1_ARATH UBC2_WHEAT UBC1_CAEEL UBE2B_HUMAN UBC2_CANAL UBC2_SCHPO Prim.cons.

Mais on ne conserve pas en mmoire le rsultat de "l'lection" (courte majorit ou plbiscite) !

14

Dmarche
Il est tout fait envisageable d'utiliser des algorithmes optimaux (de type Needleman-Wunsch) pour faire des alignements non plus 2 2 mais n squences. Mais si on veut aligner 10 squences d'une longueur d'environ 300 lettres, il faudra un espace mmoire de 515 Giga-Octets !!! Seules des mthodes heuristiques sont pour l'instant disponibles pour faire des alignements multiples.

15

Alignement multiple:
Alignement deux deux de toutes les paires de squences
Les scores sont stocks dans des matrices de scores

Tri des squences

Du plus similaire par exemple

Calcul d'un arbre guide

Mise en vidence relations de proximits des

Alignement des squences par ordre croissant

Les deux plus proches puis la suivante, etc

Alignement des groupes les plus proches

L'arbre sert de support pour choisir les squences qui seront agrges.

Stratgie itrative

Stratgie progressive
16

Alignement multiple: principe

Lapproche la plus courante consiste aligner progressivement des paires de squences. Les diffrentes approches se distinguent par: La faon de choisir la paire initiale de squences Pour progresser dans lalignement, les programmes vont: Soit aligner chaque squence les unes aprs les autres un alignement unique enrichi chaque tape. Soit crer des sous-familles de squences dabord alignes au sein de ces familles puis entre les familles. La mthode de pondration des alignements individuels des paires de squences et des alignements cumuls.
17

Alignement bas sur un arbre (progressif)

Ide: reconstruire lalignement multiple partir dun arbre guide (clusters) feuilles : squences noeuds: alignements Partir des feuilles puis remonter dans larbre Utilisation de la technique de profil alignement -> produire un seul alignement multiple avec deux.

CLUSTer + ALignement

CLUSTAL
Thompson et al. 1994

18

ClustalW EBI
ClustalW est lun des lalignement progressif.

http://www.ebi.ac.uk/Tools/msa/clustalw2/ programmes les plus utiliss pour

Etape 1: Alignements globaux 2 2 Etape 2: Regroupements des alignements (clusters), construction arbre guide Etape 3: Alignement multiple obtenu par combinaisons des alignements 2 2 (profils)

19

ClustalW exemple

4 squences s1 s2 s3 s4 cgatgagtcattgtgactg cgagccattgtagctactg cgaccattgtagctacctg cgatgagtcactgtgactg

Jeu de score: Indel= -2 Substitution=-1 Identit= 1

20

ClustalW tape 1: Calcul des scores

Les alignements de toutes les paires de squences sont raliss puis le programme gnre une matrice de distances dcrivant leur taux de similitude.
s1 s2 s1 s3 s1 s4 cgatgagtcattgt-g--actg ||| | |||||| | |||| cga-g--ccattgtagctactg cgatgagtcattg-tgactg ||| | | | | | ||| cgacca-ttgtagctacctg cgatgagtcattgtgactg |||||||||| |||||||| cgatgagtcactgtgactg s2 s3 s2 s4 s3 s4 cgagccattgtagcta-ctg ||| |||||||||||| ||| cga-ccattgtagctacctg cga-g--ccattgtagctactg ||| | || ||| | |||| cgatgagtcactgt-g--actg cgaccattgtagctacctg ||| | | | ||| cgatgagtcactgtgactg

Tableau des scores dalignement:

s1 s1 s2 s3 s4 2 0 17 14 0 -1
21

s2 2

s3 0 14

S4 17 0 -1

Pour N squences: N(N-1)/ 2 calculs

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:
s1 s1 s2 s3 s4 2 0 17 14 0 -1 s2 2 s3 0 14 S4 17 0 -1

s1 s2 s3 s4

Regroupement des squences suivant leur similitude partir de la matrice des scores 2 2.
22

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:
s1 s1 s2 s3 s4 2 0 17 14 0 -1 s2 2 s3 0 14 S4

17
0 -1

s1 s2 s3 s4

23

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:
s1 s1 s2 s3 s4 2 0 17 14 0 -1 s2 2 s3 0 S4

17
0 -1

14

s1 s2

s3 s4

24

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:
s1 s1 s2 s3 s4 2 0 17 14 0 -1 s2 2 s3 0 S4

17
0 -1

14

s1 s2 s4

s3

25

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:
s1 s1 s2 s3 s4 2 0 17 14 0 -1 s2 2 s3 0 S4

17
0 -1

14

s4 s1

s1 s4

s3 s2

s2 s3

26

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:
s1 s1 s2 s3 s4 2 0 17 14 s2 s3 S4 17 0 -1

0
14

Alignement s1s2 est plus proche que s1s3

-1

Alignement s4s2 est plus proche que s4s3

Matrice de score -> matrice de distance

27

ClustalW tape 2: Construction arbre

A laide de la matrice de scores, un arbre guide (ou dendogramme) est ensuite construit par un algorithme dit de neighbor-joining:

s1 s1 s2 s3 s4 2 0 17

s2 2 14 0

s3 0 14 -1

S4 17 0 -1

s4

s1

s2

s3

Arbre guide construit

28

Etape 3: Construction alignement final

ClustalW aligne les squences en se servant de larbre guide: chaque paire de squences situes sur une mme branche extrieure de larbre est aligne par programmation dynamique. Les alignements partiels permettent de constituer des profils, reprsents sous forme de tableau dans lequel sont donnes pour chaque position la frquence observe de chaque lettre. Lalgorithme aligne ensuite les profils associs par un mme nud de larbre. Cet alignement de squences puis de profils se poursuit de faon rcursive jusqu lalignement final complet depuis les branches de larbre vers la racine.

29

Etape 3: Construction alignement final

Lalignement et cration des profils:
2 squences aligner globalement Alignement 2 2 avec insertion/dltion Remplissage des trous et fusion par formation dun profil

Profil aligner avec une autre squence Alignement profil et squence avec insertion/dltion

Remplissage des trous et fusion par formation dun profil

30

Etape 3: Construction alignement final

s1 s4

cgatgagtcattgtgactg |||||||||| |||||||| cgatgagtcactgtgactg

s2 s3

cgagccattgtagcta-ctg ||| |||||||||||| ||| cga-ccattgtagctacctg

s4 cgatgagtcactgtgactg

s1 cgatgagtcattgtgactg

s2 cgagccattgtagctactg

s3 cgaccattgtagctacctg

31

Etape 3: Construction alignement final

Once a gap, always a gap
s2 s3 s1 s4 cga---gccattgtagcta-ctg cga----ccattgtagctacctg cgatgagtcattgt-g--ac-tg cgatgagtcactgt-g--ac-tg

s1 s4

cgatgagtcattgtgactg |||||||||| |||||||| cgatgagtcactgtgactg

s2 s3

cgagccattgtagcta-ctg ||| |||||||||||| ||| cga-ccattgtagctacctg

s4 cgatgagtcactgtgactg

s1 cgatgagtcattgtgactg

s2 cgagccattgtagctactg

s3 cgaccattgtagctacctg

32

ClustalW
ClustalW est optimis pour les protines:
Pondration reprsentation des squences en fonction de leur sur/sous

Adaptation des matrices de similitudes au fil de lalgorithme en fonction de la divergence des squences aligner
Blosum 80 pour aligner des squences proches Blosum 50 pour aligner des squences distantes

Pnalits de gaps spcifiques chaque rsidu.

Par exemple, les Glycines sont davantage susceptible davoisiner un gap que les Valines.

Pnalits de gaps rduites dans les rgions hydrophiles

Encourage la formation de gaps dans des boucles plutt que dans des rgions structures.

Pnalits de gaps augmentes dans le voisinage dautres gaps

Evite la formation de petits gaps voisins, au profit de longs gaps. 33

ClustalW
Attention
ClustalW commencera aligner les n(n-1)/2 paires de squences, donc avec 80 squences aligner, il doit, pour remplir sa matrice de score effectuer 3160 alignements (algo mthode exacte), ce qui peut prendre pas mal de temps ! Si une squence n'appartient pas la mme famille et que toutes les autres se sont alignes par rapport elle, on aura un rsultat catastrophique. Si une squence est beaucoup plus courte que les autres, on aura un problme au niveau du score (qui sera plus bas que les autres car il y aura de nombreux gaps, donc risque de fausser l'arbre guide).

34

MultAlin

Corpet F 1988 (progressif)

Autre algorithme bas sur un arbre

Principe:
1/ calcule une matrice de similarit des paires 2/ construit un arbre de clustering hierarchique 3/ construit lalignement multiple en suivant larbre 4/ reconstruit une arbre de clustering hierarchique avec les nouveaux alignements paire paire issus de lalignement trouve 5/ ritre le processus jusqu stabilisation de larbre de clustering
35

MultAlin

http://bioinfo.genotoul.fr/multalin/multalin.html

36

MultAlin
4 squences s1 s2 s3 s4 taccatga taccata gacgacca gaccatctca

Jeu de score: Indel= -1 Substitution=-1 Identit= 1

1/ Calcul des meilleurs alignements 2 2

37

MultAlin
2/ Construction d'un arbre de clustering
s1 s1 s2 s3 s4
S1 S2

s2 6

s3 0 0

S4 2 3 4

6 0 2 0 3 taccatga
||||||| |

taccat-a

On va regrouper ces 2 squences dans le tableau des alignements 2 2 qui ont le meilleur score donc s1 et s2

38

MultAlin
2/ Construction d'un arbre de clustering
s1 s1 s2 s3 s4 6 0 2 0 3 4 s2 6 s3 0 0 S4 2 3 4 s1s2 s3 s4 0 2.5 4 s1s2 s3 0 S4 2.5 4

S1 S2

taccatga
||||||| |

taccat-a

Pour calculer les nouveaux scores avec les autres squences : moyenne des scores des squences regroupes: S1s2 avec s4 : (2+3 )/2=2.5 Mme chose pour s1s2 avec s3 = 0
39

MultAlin
2/ Construction d'un arbre de clustering
s1s2 s1s2 s3 s4
S3 S4

s3 0

S4 2.5 4 s1s2 s3s4

s1s2 1.25

s3s4 1.25

0 2.5 4

gacga-c-ca
||| | | ||

gaccatctca

Pour calculer les nouveaux scores avec les autres squences : moyenne des scores des squences regroupes: s3+s4 = (2.5+0)/2= 1.25

40

MultAlin
S1 S2 S3 S4

taccat--ga taccat---a gacga-c-ca gaccatctca

3/ Nouvelle matrice de score et on recommence

S1 S2 S3 S4

taccat--ga taccat---a gacgac--ca gaccatctca

41

Autre mthode (itratif)

A partir des alignements locaux
Ide: reprer des similitudes locales fortes entre les squences (les diagonales du dotplot par exemple) Alignements des paires de squences avec optimisation des poids des diagonales Tri des diagonales selon leur poids et leur chevauchement Reconstruction gloutonne
Insertion des diagonales par poids dcroissants Vrification de la consistance avec les diagonales dj introduites

Recommencer

DIagonal + ALIGNement
Morgenstern et al. 1996

DIALIGN

42

DIALIGN

Morgenstern et al. 1996

DIALIGN sur Pasteur: http://mobyle.pasteur.fr/cgi-bin/portal.py?form=dialign

43

DIALIGN exemple
3 squences: a) YIAFLFAWDD b) LACFIFGS c) SWEDFMFAED Etape 1 : Dtection des diagonales dans les paires de squences: Rechercher tous les fragments (suite de lettres) le plus grand possible similaires entre deux squences

YIAFLFAWDD

SWEDFMFAED LACFIFGS

44

DIALIGN exemple
3 squences: a) YIAFLFAWDD b) LACFIFGS c) SWEDFMFAED Etape 1 : Dtection des diagonales dans les paires de squences: Rechercher tous les fragments (suite de lettres) le plus grand possible similaires entre deux squences

YIAFLFAWDD

SWEDFMFAED LACFIFGS

45

DIALIGN exemple
3 squences: a) YIAFLFAWDD b) LACFIFGS c) SWEDFMFAED Etape 1 : Dtection des diagonales dans les paires de squences: Rechercher tous les fragments (suite de lettres) le plus grand possible similaires entre deux squences

YIAFLFAWDD

SWEDFMFAED LACFIFGS

46

DIALIGN exemple
Etape 2 : Slection dun ensemble cohrent de diagonales pour construire lalignement, on retient que les fragments compatibles: Pas de croisement Pas de chevauchements score maximal

YIAFLFAWDD

SWEDFMFAED
Le fragment WDD et WED est incompatible avec l'autre fragment, donc on va conserver seulement le plus grand.

47

DIALIGN exemple
Etape 2 : Tri des squences en fonction du nombre total de fragments communs entre elles.

YIAFLFAWDD

SWEDFMFAED LACFIFGS
Il y a deux fragments compatibles entre la squence a et b, donc on va commencer par ces deux squences.

yIA-FLFawdd -LAcFIFgs-48

DIALIGN exemple
Etape 2 : Alignement itratif des squences, de la premire la dernire de la liste. A chaque itration, des insertions sont ajoutes de manire ce que les diffrents rsidus soient correctement aligns

yIA-FLFAWDd -LAcFIFgs-swedFMFAED-

49

Autres mthodes
T-Coffee Notredame C et al. 2000 exemple: http://www.ebi.ac.uk/Tools/msa/tcoffee/
Il permet de tenir compte de contraintes locales lies la structure des protines -> mthode consensus T-Coffee is a multiple sequence alignment program. Its main characteristic is that it will allow you to combine results obtained with several alignment methods.

MUSCLE Edgar RC. 2004 exemple: http://www.ebi.ac.uk/Tools/msa/muscle/

Amlioration par des tapes de raffinement pour recalculer des arbres guides. MUSCLE stands for MUltiple Sequence Comparison by Log- Expectation. MUSCLE is claimed to achieve both better average accuracy and better speed than ClustalW2 or T-Coffee, depending on the chosen options Et MAFFT ../..
50

Comparaison
Exemple (C. Notredame)

GARFIELD THE LAST FAT CAT GARFIELD THE FAT CAT GARFIELD THE VERY FAST CAT THE FAT CAT

51

CLUSTAL vs DIALIGN vs MUSCLE

Alignement fourni par ClustalW2:

seq2 seq4 seq1 seq3

GARFIELDTHE----FAT-CAT --------THE----FAT-CAT GARFIELDTHELASTFAT-CAT GARFIELDTHEVERYFASTCAT

Alignement fourni par MUSCLE:

Alignement fourni par Dialign2:

seq1 seq3 seq2 seq4

GARFIELDTHELASTF-ATCAT GARFIELDTHEVERYFASTCAT GARFIELDTHEF-----ATCAT --------THEF-----ATCAT

seq1 seq2 seq3 seq4

1 1 1 1

GARFIELDTHELASTFA-TCAT GARFIELDTHE----FA-TCAT GARFIELDTHEVERYFASTCAT --------THE----FA-TCAT

52

Comparaison MAIS !
GARFIELD THE LAST FAT CAT THE FAT CAT GARFIELD GARFIELD THE VERY FAST CAT THE FAT CAT

53

Comparaison MAIS !
Alignement fourni par ClustalW2:

seq2 seq4 seq1 seq3

--------THE----FAT-CATGARFIELD --------THE----FAT-CAT-------GARFIELDTHELASTFAT-CAT-------GARFIELDTHEVERYFASTCAT-------*** **: ***

17 9 21 22

Alignement fourni par MUSCLE:

s3 s3 s2 s4

GARFIELDTHEVERYFASTCAT---------------THE----FA-TCATGARFIELD --------THE----FA-TCAT-------GARFIELDTHELASTFA-TCAT--------

54

Mais pourquoi faire ?

sp|P47938|THIO1_DROME sp|Q09433|THIO1_CAEEL tr|Q8T9N5|Q8T9N5_SCHMA sp|Q43636|TRXH_RICCO sp|P10599|THIO_HUMAN sp|P29451|THIO_MACMU sp|P50413|THIO_SHEEP sp|P08628|THIO_RABIT sp|P08629|THIO_CHICK sp|P29445|THIO1_DICDI sp|P29447|THIO3_DICDI sp|P42115|THIO_NEUCR sp|P0AA25|THIO_ECOLI sp|P52233|THIO_THIFE sp|Q05739|THIO_STRCL sp|P51225|THIO_PORPU sp|O22022|THIO_CYAME

-------MASVRTMN---DYHKRIEAADDK--LIVLDFYATWCGPCKEME MLKRCNFKNQVKYFQS--DFEQLIRQHPEK--IIILDFYATWCGPCKAIA -------MSKLIELKQDGDLESLLEQHKNK--LVVVDFFATWCGPCKTIA ---MAAEEGQVIGCHTVEAWNEQLQKGNDTKGLIVVDFTASWCGPCRFIA ---------MVKQIESKTAFQEALDAAGDK--LVVVDFSATWCGPCKMIK ---------MVKQIESKAAFQEALDDAGDK--LVVVDFSATWCGPCKMIK ---------MVKQIESKYAFQEALNSAGEK--LVVVDFSATWCGPCKMIK ---------MVKQIESKSAFQEVLDSAGDK--LVVVDFSATWCGPCKMIK ---------MVKSVGNLADFEAELKAAGEK--LVVVDFSATWCGPCKMIK ------MSNRVIHVSSCEELDKHLR--DER---VVVDFSAVWCGPCRAIS ------MS-KVIHVTSNEELDKYLQ--HQR---VVVDFSAEWCGPCRAIA ------MSDGVKHINSAQEFANLLNTTQYV----VADFYADWCGPCKAIA -------MSDKIIHLTDDSFDTDVLKADGA---ILVDFWAEWCGPCKMIA -------MSDAILYVSDDSFETDVLKSSKP---VLVDFWAEWCGPCKMIA -------MAGVLKNVTDDTFEADVLKSEKP---VLVDFWAEWCGPCRQIA -------MS--VSQVTDASFKQEVINNDLP---VLVDFWAPWCGPCRMVS -----------MLHIDELTFENEVLQSEKL---VLVDFWAPWCGPCRMIG : : ** * *****: : STVKSLARKYSSK--AVVLKIDVDKFEELTERYKVRSMPTFVFLRQNRRL PLYKELATTHKG---IIFCKVDVDEAEDLCSKYDVKMMPTFIFTKNGDAI PLFKELSEKYDA----IFVKVDVDKLEETARKYNISAMPTFIAIKNGEKV PFLAELAKKLPN---VTFLKVDVDELKTVAHEWAVESMPTFMFLKEGKIM PFFHSLSEKYSN---VIFLEVDVDDCQDVASECEVKCMPTFQFFKKGQKV PFFHSLSEKYSN---VVFLEVDVDDCQDVASECEVKCMPTFQFFKKGQKV PFFHSLSEKYSN---VVFLEVDVDDCQDVAAECEVKCMPTFQFFKKGQKV PFFHALSEKFNN---VVFIEVDVDDCKDIAAECEVKCMPTFQFFKKGQKV PFFHSLCDKFGD---VVFIEIDVDDAQDVATHCDVKCMPTFQFYKNGKKV PVFEKLSNEFIT---FTFLHVDIDKLNVHPIVSKIKSVPTFHFYRNGSKV PVFDKLSNEFTT---FTFVHVDIDKVNTHPIVKEIRSVPTFYFYVNGAKV PMYAQFAKTFSIPNFLAFAKINVDSVQQVAQHYRVSAMPTFLFFKNGKQV PILDEIADEYQGK--LTVAKLNIDQNPGTAPKYGIRGIPTLLLFKNGEVA PILEEIADEYADR--LRVAKFNIDENPNTPPQYAIRGIPTLLLFKAGKLE PSLEAIT-EHGGQ--IEIVKLNIDQNPATAAKYGVMSIPTLNVYQGGEVV PVVDAIAEEYESS--IKVVKINTDDNPTIAAEYGIRSIPTLMIFKSGERV PILEEIAKEFN----LKVVQVNTDENPNLATFYGIRSIPTLMLFKKGQRV . : . ..: *. : :**: . AS-----FAGADEHKLTNMMAKLVKA----------EA-----LEGCVEDELRQKVLEHVSAQ---------GD-----VVGASIAKVEDMIKKFI------------DK-----VVGAKKDELQQTIAKHMATAST-------GE-----FSGANKEKLEATINELV------------GE-----FSGANKEKLEATINELV------------SE-----FSGANKEKLEATINELI------------GE-----FSGANKEKLEATINELL------------QE-----FSGANKEKLEETIKSLV------------SE-----FSGASESILRSTLEANK------------SE-----FSGANEATLRSTLEANI------------AVNGSVMIQGADVNSLRAAAEKMGRLAKEKAAAAGSS AT----KVGALSKGQLKEFLDANLA-----------AT----KVGALSKAQLTAFLDSQL------------KT----IVGAKPKAALLRPGPVPR------------DT----VIGAVPKSTLESTLNKYIS-----------DT----VIGAVPKSILIHTINKYL------------. . :

Exemple d'alignement fourni par ClustalW2

sp|P47938|THIO1_DROME sp|Q09433|THIO1_CAEEL tr|Q8T9N5|Q8T9N5_SCHMA sp|Q43636|TRXH_RICCO sp|P10599|THIO_HUMAN sp|P29451|THIO_MACMU sp|P50413|THIO_SHEEP sp|P08628|THIO_RABIT sp|P08629|THIO_CHICK sp|P29445|THIO1_DICDI sp|P29447|THIO3_DICDI sp|P42115|THIO_NEUCR sp|P0AA25|THIO_ECOLI sp|P52233|THIO_THIFE sp|Q05739|THIO_STRCL sp|P51225|THIO_PORPU sp|O22022|THIO_CYAME

sp|P47938|THIO1_DROME sp|Q09433|THIO1_CAEEL tr|Q8T9N5|Q8T9N5_SCHMA sp|Q43636|TRXH_RICCO sp|P10599|THIO_HUMAN sp|P29451|THIO_MACMU sp|P50413|THIO_SHEEP sp|P08628|THIO_RABIT sp|P08629|THIO_CHICK sp|P29445|THIO1_DICDI sp|P29447|THIO3_DICDI sp|P42115|THIO_NEUCR sp|P0AA25|THIO_ECOLI sp|P52233|THIO_THIFE sp|Q05739|THIO_STRCL sp|P51225|THIO_PORPU sp|O22022|THIO_CYAME

55

56

57

Quelles mthode utiliser

Plus les squences sont divergentes, moins le rsultat est fiable. Quand le taux didentit est suprieur 35%, toutes les mthodes sont satisfaisantes. Twilight Zone : 10-20% didentit
Aucune mthode nassure un alignement avec plus de 50% de correction.

ClustalW a tendance autoriser moins de gaps que Dialign Similitude locale : Dialign Similitude globale : ClustalW Existe dautres mthodes : Muscle, MultiAlign, Tcoffee, etc Pas de mthode universelle Pas de confiance aveugle vis--vis du rsultat obtenu
58