Alignement multiple

Nadia El-MabroukAlignement multiplePlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques usuelles: Mthodes par point dancrage

1. IntroductionGnralisation de lalignement de 2 squencesDonnes: Un ensemble de squence homologues (nuclotides ou AA): S1, S2, , SkAlignement multiple: Matrice A = (aij ), 1ik; 1 jl. aij symboles de lalphabet ou -, tq contatnation des caractres la ligne i produit Si

Exemple: Alignement multiple dARN

http://en.wikipedia.org/wiki/File:Multiple_alignment_and_the_consensus_secondary_structure_model_of_the_sRNA-Xcc1_homologs.jpgsRNA-Xcc1Alignement 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 gnesB.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 TrpAnc 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

ANCAlignement de gnomesBut de lalignement multipleTrouver des contraintes de structures pour les ARNTrouver des caractristiques communes une famille de protines;Caractriser les rgions conserves et les rgions variablesRelier la squence la structure et la fonctionReconstuire des phylogniesSlectionner des squences homologuesTrouver un alignement multipleLutiliser pour construire larbre phylogntique.Infrer des scnarios dvolution

Modle volutif sous-jacentUn bon alignement reflte le modle dvolution qui a donn lieu aux squencesHypothses: les squences aligner descendent dun anctre communLes squences ont volu par mutations ponctuelles

GCG ACGACG A GG C G | |A C G

Prsentation de Tandy Warnow MAGEhttp://www-etud.iro.umontreal.ca/~lafonman/MAGE2013/slides/Tandy-Warnow-MAGE.pdfAGGGCATTAGCCCATAGACTTAGCACAAAGCGCTTAlignement multipleinduit:Modle volutif sous-jacent

Retrouver la phylogniePrsentation de Tandy Warnow MAGEhttp://www-etud.iro.umontreal.ca/~lafonman/MAGE2013/slides/Tandy-Warnow-MAGE.pdfPondration dun alignement multiplePar 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 squencesLe plus utilis, bonnes proprites thoriques et pratiquesScore SP dun alignement A = somme des scores des alignements induits pour chaque paire de squences dans A

PlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques usuelles: Mthodes par point dancrage

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

Solution exacte pour n=3On considre la distance ddition avec pondration de lalphabet. S,T,U trois seq. de tailles n1, n2, n3D(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=3Pour 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)+2bd5= 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)DST(i,j): Score de lal. Op. de S[1..i] et T[1..j];D(i,j,0) = DST(i,j) +(i+j)b; D(i,0,k) = DSU(i,k)+(i+k)b; D(0,j,k) = DTU(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: zEffectuer la programmation dynamique en scrutage avant dans un espace dalignement restreint.Programmation dynamique avec scrutage avantDGTCAGGT0CATAGTGLes 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 wp(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 vw123511224456767Programmation dynamique avec scrutage avantDGTCAGGT0CATAGTG12351122445676722122Les 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 wp(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 fairev = 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) DGTCAGGT0CATAGTG12112q: (0,0)(0,1) (1,0) (1,1)(0,2) (1,2)(2,0) (2,1)22220123456701234567Acclration de lalignement SP exactIDST (i,j): Score de lal. Op. de S[i..n] et T[j..n]. Dfinition similaire pour IDSU (i,k) et IDTU (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 IDST(i,j) +IDSU(i,k) + IDTU(j,k)

Si D(i,j,k) + IDST(i,j) + IDSU(i,k) + IDTU(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 initialePlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques usuelles: Mthodes par point dancrage

3. Heuristique borne pour le score SPHeuristique: 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 solutionHeuristique 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 arbreS: Ensemble de squences;T: Arbre guide reliant les sq. de SA: Alignement multiple de S

A consistant avec T ssi: pour tout couple de squences Si, Sj relies par une arte, Si et Sj sont alignes de faon optimale dans AAXZAXZAXXZAYZAYXYZ3: A X X - Z1: A X - - Z2: A - X - Z4: A Y - - Z5: A Y X X Z31245MthodeChoisir deux squences quelconques adjacentes dans larbre et former un alignement optimal A;Choisir une squence non encore aligne Si, adjacente une squence aligne SjAligner Si et Sj.Incorporer lalignement A.Si un nouvel indel a t rajout dans Sj , rajouter un espace chaque ligne la colonne correspondante dans A

Complexit: k squences de taille n , O(kn2)Arbre toileS: ensemble de squencesSquence centrale Sc: Squence de S tq la somme des distances toutes les autres squences de S est minimale.Arbre toile Tc: Arbre en toile, connectant toutes les squences de S, et de racine Sc S1S2S3S4S5S6S={S1,S2,S3,S4,S5,S6}k = nb de squences, n = taille de chaque squence

Complexit: Trouver la squence centrale Sc: O(k2n2)Alignement Ac consistant avec Tc: O(kn2)Trouver un Alignement consistant avec larbre toiled(A): Score SP dun alignement multiple AAc : Alignement consistant avec larbre toiledc(Si,Sj): Score induit par Ac pour Si, SjD(Si,Sj): Score dun alignement optimal de Si et SjA*: Alignement multiple optimal de Sd*(Si,Sj): Score induit par A*

Si le score considr vrifie lingalit triangulaire: e(x,z) e(x,y)+e(y,z)alorsdc(Si,Sj) dc(Si,Sc) + dc(Sc,Sj) = D(Si,Sc)+D(Sc,Sj)

Et donc:d(Ac)/d(A*) 2(k-1)/k < 2

BornesPlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques 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-completAlignement soulev: Les tiquettes Sont des squences de S

4. Alignement phylogntiqueAlignement soulev optimal: borne sup pour lal. phyl. opt.T*: alignement phylogntique optimalOn veut construire un alignement soulev TS partir de T*

Dans TS , v est tiquet par la squence de S la plus proche de Sv*

Score de TS 2 fois score de T*Alignement soulev optimalTv: sous-arbre de racine v de Td(v,S): Score de lal. phyl. opt. de Tv sachant que v tiquet par S vS1S2d(v,S) = D(S,S1)+D(S,S2)SvSvSd(v,S) = Sv minS [D(S,S) + d(v,S)]Valeur de lal. Soulev op. = minimum de d(r,S) o r racine de larbreComplexit: k seq. de taille n. Au cours dun prtraitement, calculer tous les D(Si,Sj): O(k2n2)Pour chaque nud v, calculer chaque d(v,S) en O(k) : O(k2n2+k3)PlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques usuelles: Mthodes par point dancrage

5. Heuristiques usuelles Mthodes progressivesCrer 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 ExempleMultAlign, ClustalW, Pileup, T-CoffeeDiffrent surtout par la mthode de construction de larbre guideAvantages: Rapide, simple programmer, ncessite peu de mmoireInconvnients: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 processusProduit un seul alignement5.2 Plusieurs implmentations5.3 ClustalW (Thompson, Higgins, Gibson 1994)Algorithme progressif le plus utilisCalcule les scores dalignement de chaque paire de squences.Construit un arbre guide par Neighbour-JoiningUtilise cet arbre pour choisir les squences incorporer lalignement. Choisit les plus petites distances chaque foisABCD21342Effectue trois sortes dalignements: Entre deux squences, une squence et une matrice consensus, ou deux matrices consensusC1C2C3C4C5acg-tacactaggc-gc-cgC1C2C3C4C5a0.7500.2500c00.7500.750g0.250.250.5000.25t00000.50-000.250.250.25Alignement dune squence avec une matrice consensus a a c - c g C1 - C2 C3 C4 C540Valeur dun tel alignement?Matrice de pondration

Matrice consensus acgt-a2-3-1-3-1c-32-3-1-1g-1-32-3-1t-3-1-32-1--1-1-1-10C1C2C3C4C5a0.7500.2500c00.7500.750g0.250.250.5000.25t00000.50-000.250.250.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 ; p(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 = Si p(Ci,ti) =1.25 1+0.75+= -1Calcul dun alignement optimalD(i,j) : Score alignement optimal entre S[1..i] et C[1..j]

D(i,0) = Ski p(tk,-) ; D(0,j) = Skj p(-,Ck)

D(i,j) = max [D(i-1,j-1)+p(ti,Cj), D(i-1,j)+p(tj,-), D(i,j-1)+p(-,Cj)]

Complexit: O(|S | mn) (n: nbre de colonnes de C; m: taille de S)PlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques usuelles: Mthodes par point dancrage

6. Heuristiques usuelles: Mthodes itrativesUn 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 - ACTTMthode itrativeObtenir un premier alignement multiple de basse qualitAmliorer 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, HMMERAlgorithme de Barton-Stenberg (MultAlign)Calculer tous les alignements deux deuxChoisir 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 consensusRecommencer jusqu puisement des squencesRetirer S1 et la raligner avec la matrice consensus de lal. restant (S2. Sn). Recommencer avec S2,,SnRpter le processus un nbre fix de fois, ou jusqu ce que le score de lalignement converge.PlanIntroductionSolution exacte pour lalignement multipleHeuristique borneAlignement phylogntiqueHeuristiques usuelles: Mthodes progressivesHeuristiques usuelles: Mthodes itrativesHeuristiques usuelles: Mthodes par point dancrage

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