Nadia El-Mabrouk Alignement multiple. Plan 1. Introduction 2. Solution exacte pour lalignement multiple 3. Heuristique bornée 4. Alignement phylogénétique

Nadia El-Mabrouk Alignement multiple

Plan 1. Introduction 2. Solution exacte pour lalignement multiple 3. Heuristique borne 4. Alignement phylogntique 5. Heuristiques usuelles: Mthodes progressives 6. Heuristiques usuelles: Mthodes itratives 7. Heuristiques usuelles: Mthodes par point dancrage

1. Introduction Gnralisation de lalignement de 2 squences Donnes: Un ensemble de squence homologues (nuclotides ou AA): S 1, S 2, , S k Alignement multiple: Matrice A = (a ij ), 1ik; 1 jl. a ij symboles de lalphabet ou -, tq contatnation des caractres la ligne i produit S i

Exemple: Alignement multiple dARN http://en.wikipedia.org/wiki/File:Multiple_alignment_and_the_consensus_secondary_structure_model_of_the_sRNA-Xcc1_homologs.jpg sRNA-Xcc1

Alignement multiple dacides amins Alignment of forkhead box (Fox) genes in mice.

Alignement multiple de gnes Base de donne Ensembl contient plus de 100,000 arbres de gnes

B.subtilis Anc Ile Ala Ser Ile Ala Met Glu Val Thr Lys Leu Gly Leu Arg Pro Ala Asn Thr ----------------------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (1) Ile Ala Ser Ile Ala Met Glu Val Thr Lys Leu Gly Leu Arg Pro Ala Asn Thr Gly Arg Pro Ala ------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met Asp Asn Ser Glu Val Met Asp Phe Thr Tyr Trp (2) Ile Ala Ser Ile Ala Met Glu ----------------------------------- Asn Thr Gly Arg Pro Ala ------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met Asp Asn Ser Glu Val Met Asp Phe Thr Tyr Trp (3) Ile Ala Ser Ile Ala Met Glu Val Thr Lys Leu Gly Leu Arg Pro Ala Asn Thr Gly Arg Pro Ala ------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met Asp Asn Ser Glu Val Met Asp Phe Thr Tyr Trp (4) Ile Ala Ser Ile Ala Met Glu ----------------------------------- Asn Thr Gly Arg Pro Ala ------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (5) Ile Ala Ser Ile Ala Met Glu ----------------------------------- Asn Thr ----------------------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (6) Ile Ala Ser Ile Ala Met Glu ------------------------------------------------------------------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (7) ------- Ser Ile Ala Met Glu ------------------------------------------------------------------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (8) Ile Ala Ser Ile Ala Met Glu Val Thr Lys Leu Gly Leu Arg Pro Ala Asn Thr Gly Arg Pro --- Ile Ala Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly Ile Ala --- Met Asp Ile Ala Asn Ser Glu Val Val ----------------------- Asp Phe Thr Tyr Trp (9) ------- Ser ------- Met Glu Val Thr Lys Leu Gly Leu Arg Pro Ala Asn Thr Gly Arg Pro Ala Ile Ala Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (10) Ile Ala Ser Ile Ala Met Glu ----------------------------------- Asn Thr ----------------------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly ------- --- Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp (11) ------------------- Met Glu ----------------------------------- Asn --------------------------- Glu Val Thr Tyr Gln Asn Ser Glu Gln Lys Leu Leu Arg Gly Ile Ala Ser Met Asp ------- Asn Ser Glu Val Met ----------------------- Asp Phe Thr Tyr Trp Anc Trp His Gln Gly Cys Leu Leu Gly Val [t] -Arg ---------- Gln -Arg --- -Glu -Ser -Asn -Ile -Gly -His -Phe -Asp -Met -Ser -Met ------------------------ -Met -Ala -Pro -Arg -Leu -Gly -Leu -Lys -Thr -Val -------- -Ala -Arg -Phe -Asp -Glu Lys (1) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg --- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val ------- -Ala Arg Phe Asp Glu Lys (2) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg --- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met Phe Asp Met Ser Met Met Ala Pro Arg Leu Gly Leu Lys Thr Val Ala Ile Ala Arg Phe Asp Glu Lys (3) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg --- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val --------- -Ala Arg Phe Asp Glu Lys (4) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg --- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val --------- Ala Arg Phe Asp Glu Lys (5) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg Trp Arg Gln Arg --- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val --------- -Ala Arg Phe Asp Glu Lys (6) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg Arg Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val --------- Ala Arg Phe Asp Glu Lys (7) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg Arg Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val --------- Ala Arg Phe Asp Glu Lys (8) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg Arg Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val Ala -Ile Ala Arg Phe Asp Glu Lys (9) Trp His Gln Gly Cys Leu Leu Gly Val [t] Arg ---------- Gln Arg Arg Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg Leu Gly Leu Lys Thr Val Ala Ile Ala Arg Phe Asp Glu Lys (10) Trp His Gln Gly Cys Leu Leu Gly -Val[t] -Arg ---------- Gln Arg ---- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg --- Gly Leu Lys Thr Val --------- Ala Arg Phe Asp Glu Lys (11) Trp His Gln Gly Cys Leu Leu Gly Val [t] -------------- Gln Arg ---- Glu Ser Asn Ile Gly His Phe Asp Met Ser Met ------------------------ Met Ala Pro Arg -Leu Gly Leu Lys Thr Val --------- -Ala Arg Phe Asp Glu Lys ANC Alignement de gnomes

But de lalignement multiple Dterminer si une squence appartient une famille donne de gnes; Trouver des contraintes de structures pour les ARN Trouver des caractristiques communes une famille de protines; Caractriser les rgions conserves et les rgions variables Relier la squence la structure et la fonction Reconstuire des phylognies Slectionner des squences homologues Trouver un alignement multiple Lutiliser pour construire larbre phylogntique. Infrer des scnarios dvolution

Modle volutif sous-jacent Un bon alignement reflte le modle dvolution qui a donn lieu aux squences Hypothses: les squences aligner descendent dun anctre commun Les squences ont volu par mutations ponctuelles GCG ACG ACG A G G C G | | A C G

Prsentation de Tandy Warnow MAGE http://www-etud.iro.umontreal.ca/~lafonman/MAGE2013/slides/Tandy-Warnow-MAGE.pdf AGGGCAT TAGCCCA TAGACTT AGCACAA AGCGCTT Alignement multiple induit: Modle volutif sous-jacent

Retrouver la phylognie Prsentation de Tandy Warnow MAGE http://www-etud.iro.umontreal.ca/~lafonman/MAGE2013/slides/Tandy-Warnow-MAGE.pdf

Pondration dun alignement multiple Par rapport larbre phylogntique produit. Garder lalignement qui produit larbre de poids minimal. Complexit de calcul considrable

Score sum of pairs (SP) Gnralisation du score utilis pour lalignement de deux squences Le plus utilis, bonnes proprites thoriques et pratiques Score SP dun alignement A = somme des scores des alignements induits pour chaque paire de squences dans A

2. Solution exacte Alignement multiple pour le score SP Trouver un alignement multiple ayant un score SP minimum Problme NP-complet (Wang and Jiang 1994) Gnralisation de lalignement de deux squences: si m squences de taille n, algorithme en O(n m ). Trs inefficace ds que m>5 et n~100

Solution exacte pour n=3 On considre la distance ddition avec pondration de lalphabet. S,T,U trois seq. de tailles n 1, n 2, n 3 D(i,j,k): Score SP de lal. op. de S[1..i], T[1..j], U[1..k]; b: score dun indel; c(i,j): sore de lappariement (S [i],T [j]).

Solution exacte pour n=3 Pour chaque case (i,j,k), examiner 7 cases voisines: d1= D(i-1,j-1,k-1)+c(i,j)+c(i,k)+c(j,k) d2= D(i-1,j-1,k)+c(i,j)+2b; d3= D(i-1,j,k-1)+c(i,k) +2b; d4= D(i,j-1,k-1)+c(j,k)+2b d5= D(i-1,j,k)+2b ; d6=D(i,j-1,k)+2b; d7=D(i,j,k-1)+2b. D(i,j,k) = min(d1,d2,d3,d4,d5,d6,d7) D ST (i,j): Score de lal. Op. de S[1..i] et T[1..j]; D(i,j,0) = D ST (i,j) +(i+j)b; D(i,0,k) = D SU (i,k)+(i+k)b; D(0,j,k) = D TU (i,k)+(i+k)b

Optimisation: Algorithme MSA (Lipman et al. 1989) Calculer les alignements optimaux pour chaque paire de squences; Trouver un alignement multiple provisoire par une heuristique rapide: z Effectuer la programmation dynamique en scrutage avant dans un espace dalignement restreint.

Programmation dynamique avec scrutage avant D GTCAGGT 0 C A T A G T G Les flches vont de (i,j) (i,j+1), (i+1,j) et (i+1,j+1) p(v,w): Poids de la flche de v w p(w): Valeur provisoire de D(w). Aprs calcul de D(v): p(w) = min(p(w), D(v)+p(v,w)) Valeur de D(w) = valeur de p(w) aprs considration de tous les voisins de w vw 1235 11224 4 5 67 67

Programmation dynamique avec scrutage avant D GTCAGGT 0 C A T A G T G 1235 11224 4 5 67 67 22 1 2 2 Les flches vont de (i,j) (i,j+1), (i+1,j) et (i+1,j+1) p(v,w): Poids de la flche de v w p(w): Valeur provisoire de D(w). Aprs calcul de D(v): p(w) = min(p(w), D(v)+p(v,w)) Valeur de D(w) = valeur de p(w) aprs considration de tous les voisins de w

Algorithm: q=(0,0) (liste contenant les cases considrer) Tant que q nest pas vide faire v = premire case de q; Supprimer v de q; D(v)=p(v); Si w=(i,j+1) pas dans q, le rajouter a la fin de q; p(w)=min(p(w),D(v)+p(v,w)); Mme chose pour w=(i+1,j) et w=(i+1,j+1)

D GTCAGGT 0 C A T A G T G 1 2 112 q: (0,0)(0,1) (1,0) (1,1)(0,2) (1,2)(2,0) (2,1) 2 2 2 2 01234567 0 1 2 3 4 5 6 7

Acclration de lalignement SP exact ID ST (i,j): Score de lal. Op. de S[i..n] et T[j..n]. Dfinition similaire pour ID SU (i,k) et ID TU (j,k). z = score dUN alignement multiple de S, T, U Observation: Score SP pour S[i..n], T[j..n], U[k..n] suprieur ID ST (i,j) +ID SU (i,k) + ID TU (j,k) Si D(i,j,k) + ID ST (i,j) + ID SU (i,k) + ID TU (j,k) > z, alors (i,j,k) ne peut pas faire partie dun chemin optimal Aucun scrutage avant nest ncessaire pour (i,j,k). Plus important, certaines cases ne sont jamais introduites dans la liste q. Observation ampirique: Cette mthode peut aligner efficacement jusqu 6 squences de longueur 200. Efficacit dpend beaucoup de la val. z initiale

3. Heuristique borne pour le score SP Heuristique: Algorithme qui nest pas garanti dobtenir la solution optimale. Utilis pour des problmes difficiles (NP-complets) Heuristique borne: On sait dans quel intervalle se situe la solution Heuristique pour le score SP: Algorithme garanti dobtenir un alignement dont le score est au plus deux fois plus lev que le score dun alignement optimal.

Alignement consistant avec un arbre S: Ensemble de squences; T: Arbre guide reliant les sq. de S A: Alignement multiple de S A consistant avec T ssi: pour tout couple de squences S i, S j relies par une arte, S i et S j sont alignes de faon optimale dans A AXZ AXXZ AYZ AYXYZ 3: A X X - Z 1: A X - - Z 2: A - X - Z 4: A Y - - Z 5: A Y X X Z 3 1 2 4 5

Mthode Choisir deux squences quelconques adjacentes dans larbre et former un alignement optimal A; Choisir une squence non encore aligne S i, adjacente une squence aligne S j Aligner S i et S j. Incorporer lalignement A. Si un nouvel indel a t rajout dans S j, rajouter un espace chaque ligne la colonne correspondante dans A Complexit: k squences de taille n, O(kn 2 )

Arbre toile S: ensemble de squences Squence centrale S c : Squence de S tq la somme des distances toutes les autres squences de S est minimale. Arbre toile T c : Arbre en toile, connectant toutes les squences de S, et de racine S c S1 S2 S3 S4 S5 S6 S={S1,S2,S3,S4,S5,S6}

k = nb de squences, n = taille de chaque squence Complexit: Trouver la squence centrale S c : O(k 2 n 2 ) Alignement A c consistant avec T c : O(kn 2 ) Trouver un Alignement consistant avec larbre toile

d(A): Score SP de lalignement multiple A A c : Alignement consistant avec larbre toile d c (Si,Sj): Score induit par A c pour S i, S j D(Si,Sj): Score dun alignement optimal de S i et S j A*: Alignement multiple optimal de S d*(Si,Sj): Score induit par A* Si le score considr vrifie lingalit triangulaire: e(x,z) e(x,y)+e(y,z) alors d c (S i,S j ) d c (S i,S c ) + d c (S c,S j ) = D(S i,S c )+D(S c,S j ) Et donc: d(A c )/d(A*) 2(k-1)/k < 2 Bornes

Plan 1. Introduction 2. Solution exacte pour lalignement multiple 3. Heuristique borne 4. Alignement phylogntique 5. Heuristiques usuellesMthodes progressives 6. Heuristiques usuelles: Mthodes itratives 7. Heuristiques usuelles: Mthodes par point dancrage

Donnes: Un ensemble de squences S, et un arbre phylogntique T pour S. Problme: Trouver un tiquetage des nuds internes de T qui minimise la score de T (somme des poids des artes) Larbre T avec tiquetage de ses nuds internes est appel alignement phylogntique. Un alignement phylogntique T* induit un alignement de S: cest lalignement consistant avec T*. Problme de ltiquetage: NP-complet Alignement soulev: Les tiquettes Sont des squences de S 4. Alignement phylogntique

Alignement soulev optimal: borne sup pour lal. phyl. opt. T*: alignement phylogntique optimal On veut construire un alignement soulev T S partir de T* Dans T S, v est tiquet par la squence de S la plus proche de S v * Score de T S 2 fois score de T*

Alignement soulev optimal T v : sous-arbre de racine v de T d(v,S): Score de lal. phyl. opt. de T v sachant que v tiquet par S v S1 S2 d(v,S) = D(S,S1)+D(S,S2) S v S v S d(v,S) = v min S [D(S,S) + d(v,S)] Valeur de lal. Soulev op. = minimum de d(r,S) o r racine de larbre Complexit: k seq. de taille n. Au cours dun prtraitement, calculer tous les D(Si,Sj): O(k 2 n 2 ) Pour chaque nud v, calculer chaque d(v,S) en O(k 2 ) : O(k 2 n 2 +k 3 )

5. Heuristiques usuelles Mthodes progressives Crer un alignement multiple de S en fusionnant deux alignements de deux sous-ensembles S1 et S2 de S Mthode gnrale: Calculer les alignements deux deux; Construire un arbre guide des squences (UPGMA, Neighbour-Joining); Incorporer les squences une une dans lalignement multiple, en suivant lordre dtermin par larbre guide

Pour commencer, aligner les deux squences de distance minimale chaque tape, choisir la squence dont la distance avec une des squences dj aligne est minimale 5.1 Exemple

MultAlign, ClustalW, Pileup, T-Coffee Diffrent surtout par la mthode de construction de larbre guide Avantages: Rapide, simple programmer, ncessite peu de mmoire Inconvnients: Alignement obtenu trs dpendant de larbre guide considr. Do limportance davoir un bon arbre de dpart. Lalignement ne peut pas tre modifi au cours du processus Produit un seul alignement Le positionnement des indels rsulte du choix de larbre guide, et donc pas informatifs. 5.2 Plusieurs implmentations

5.3 ClustalW (Thompson, Higgins, Gibson 1994) Algorithme progressif le plus utilis Calcule les scores dalignement de chaque paire de squences. Construit un arbre guide par Neighbour-Joining Utilise cet arbre pour choisir les squences incorporer lalignement. Choisit les plus petites distances chaque fois A B C D 2 1 3 4 2 Effectue trois sortes dalignements: Entre deux squences, une squence et une matrice consensus, ou deux matrices consensus

Matrice de similarit choisie en fonction de la similarit des squences compares 80 100 % identit --> Blosum80 60 80 % identit --> Blosum60 30 60 % identit --> Blosum45 0 30 % identit --> Blosum30 Scores des gaps: -Score dinitialisation dun gap (SIG) + score dextension (SEG) G T E A K L I V L M A N E G A - - - - - - - - - K L -----> SIG + 9 * GEP - Score des gaps dpendant des positions et des rsidus supprims (si hydrophiles, SIG plus faible) 5.3.1 Scores de ClustalW

C1C2C3C4C5 acg-t acact aggc- gc-cg C1C2C3C4C5 a0.7500.2500 c00.750 0 g0.25 0.5000.25 t00000.50 -000.25 5.3.2 Alignement dune squence avec une matrice consensus a a c - c g C1 - C2 C3 C4 C5

5.3.2 Valeur dun tel alignement? Matrice de pondration Matrice consensus acgt- a2-3-3 c-32 g -32 t-3-32 - 0 C1C2C3C4C5 a0.7500.2500 c00.750 0 g0.25 0.5000.25 t00000.50 -000.25 Alignement : S: a a c c g C1 - C2 C3 C4 C5 p(a,C1) = 2 * 0.75 1 * 0.25 = 1.25 p(a,-) = -1*1 = -1 ; S(c,C2)= 2*0.75 -3*0.25 =0.75 p(-,C3) = -1 * 0.25 -1 * 0.50 + 0 * 0.25 = -0.75 => Score alignement = i p(Ci,ti) =1.25 1+0.75+= -1

5.3.2 Calcul dun alignement optimal D(i,j) : Score alignement optimal entre S[1..i] et C[1..j] D(i,0) = ki p(t k,-) ; D(0,j) = kj p(-,C k ) D(i,j) = max [D(i-1,j-1)+p(t i,C j ), D(i-1,j)+p(t j,-), D(i,j-1)+p(-,C j )] Complexit: O(| | mn) (n: nbre de colonnes de C; m: taille de S)

6. Heuristiques usuelles: Mthodes itratives Un des problmes des mthodes progressives: alignements intermdiaires figs X: GAAGTT Y: GAC - TT 1er alignement intermdiaire Z: GAACTG W: GTACTG Y aurait d tre: G - ACTT

Mthode itrative Obtenir un premier alignement multiple de basse qualit Amliorer lalignement par une suite ditrations bien dfinies, jusqu ce que lalignement ne puisse plus tre amlior. Mthodes dterministes ou stochastiques (alignement modifi au hasard) MultAlign, IterAlign, Praline, SAGA, HMMER

Algorithme de Barton-Stenberg (MultAlign) Calculer tous les alignements deux deux Choisir lalignement de score max, une premire matrice consensus chaque tape, choisir une paire de squences de score max, tq exactement une des squences est dans lalignement partiel obtenu. Aligner la nouvelle squence avec la matrice consensus courante. Mettre jour la matrice consensus Recommencer jusqu puisement des squences Retirer S1 et la raligner avec la matrice consensus de lal. restant (S2. Sn). Recommencer avec S2,,Sn Rpter le processus un nbre fix de fois, ou jusqu ce que le score de lalignement converge.

7. Mthode dalignement par points dancrage Base sur la recherche de motifs (points dancrage, squences consensus). Par exemple, MACAW: Rechercher un motif suffisamment long commun une majorit de squences Problme subdivis en deux: partie gauche et partie droite par rapport au motif Recommencer rcursivement avec chaque partie Les squences ne contenant pas le motif sont alignes sparment, par score SP. Les deux sous-alignements sont ensuite fusionns Lorsque les sous-squences ne contiennent plus de bons motifs, elles sont alignes par score SP

Documents

Nadia El-Mabrouk Alignement multiple. Plan 1. Introduction 2. Solution exacte pour lalignement multiple 3. Heuristique bornée 4. Alignement phylogénétique