[PDF] Phylogénie moléculaire Phylogénie moléculaire. Thomas

View - Download Phylogénie moléculaire

Previous PDF

Next PDF

Phylogénie moléculaire

Thomas Gaillard

thomas.gaillard@polytechnique.edu

École Polytechnique

Sommaire

1Introduction

2Construction d"arbres

Alignement multiple des séquences

Modèles d"évolution

Utilisation de matrices de distance

Maximum de parcimonie

Maximum de vraisemblance

3Applications

4Bibliographie

Introduction

Sommaire

1Introduction

2Construction d"arbres

Alignement multiple des séquences

Modèles d"évolution

Utilisation de matrices de distance

Maximum de parcimonie

Maximum de vraisemblance

3Applications

4Bibliographie

Introduction

Phylogénie

Définition :?

Étude des relations évolutives entre êtres vivants.

Étymologie :

fÜlon= tribu, genre, espèce gènesic= origine, source, naissanceIntérêt : origine de la vie histoire évolutive des gènes et des organismes classification et taxonomie annotation fonctionnelle

épidémiologie

Introduction

Historique

phylogénie = taxonomie + évolutionDarwin, 1837

Haeckel, 1866Molecules as

Documents of

Evolutionary History

Zuckerlandl & Pauling,

1965

Introduction

Données de départ

Approche morphologique :

matrice de caractèresApproche moléculaire :

alignement multiple de séquenceshomologuesgoshawk GALSKLSDLHAQKLRVDPVNFKLLGQCFLVVVAIHHPSVLTPEVHASLDKFLCAVGNVLTAKYR

vulture GALSKLSDLHAQKLRVDPVNFKLLGQCFLVVVAIHHPSVLTPEVHASLDKFLCAVGNVLTAKYR duck GALSKLSDLHAQKLRVDPVNFKFLGHCFLVVVAIHHPAALTPEVHASLDKFMCAVGAVLTAKYR alligator GALCRLSELHAHSLRVDPVNFKFLAHCVLVVFAIHHPSALSPEIHASLDKFLCAVSAVLTSKYR lesser GALSALSDLHAHKLRVDPVNFKLLSHCLLVTLACHHPAEFTPAVHASLDKFFSAVSTVLTSKYR giant GALSALSDLHAHKLRVDPVNFKLLSHCLLVTLASHHPAEFTPAVHASLDKFFSAVSTVLTSKYR moose GTLSDLSDLHAHKLRVDPVNFKLLSHTLLVTLAAHLPSDFTPAVHASLDKFLANVSTVLTSKYR axolotl ATLVKLSDKHAHDLMVDPAEFPRLAEDILVVLGFHLPAKFTYAVQCSIDKFLHVTMRLCISKYR

Introduction

Homologie

Deux séquences sont dites

homologueslorsqu"elles possèdent un ancêtre communLes évènements de spéciation donnent desorthologuesLes évènements de duplication donnent desparaloguesgène ancestral gèneβgèneαgèneβ ratgèneβ sourisgèneα sourisgèneα ratorthologuesorthologues paralogues homologues

Introduction

Arbres

vocabulaire définition mathématique : graphe connexe acyclique arbre binaire : chaque noeud possède au plus deux fils arbre racinéracine feuillestemps9 8 7 6 5432

1arbre non-raciné

8 7 65
4 321

Introduction

Arbres

comptagenon-racinés racinés feuilles 3 4n3n noeuds internes noeuds branches arbresavecn!! =?[n/2]-1 i=0(n-2i)autant de branches que d"ajouts d"une racineou d"une feuille pourn=10,≈2 millions d"arbres non-racinés3 21
3213
214
3 21
3123
21
4321
2133
21
4 321

Introduction

Arbres

codage et représentationsCodage : correspondance entre arbres et parenthèses imbriquées (Arthur Cayley, 1857) format Newick : ((1,(2,3)),(4,5)); ((1,(2,3) 6 7 ,(4,5) 8 9 ((1:3,(2:1,3:1.3)6:1)7:2,(4:3,5:3.5)8:1)9;Représentations : rectangulaire oblique circulaire radiale2 1 3 4 5 7 8 6 9 12 1 3 1 1.3 3 3.5 2 3 1 5 4 23
1 5 4 2 3 1 5 4

Introduction

L"arbre de la vie

http://itol.embl.de

Construction d"arbres

Sommaire

1Introduction

2Construction d"arbres

Alignement multiple des séquences

Modèles d"évolution

Utilisation de matrices de distance

Maximum de parcimonie

Maximum de vraisemblance

3Applications

4Bibliographie

Construction d"arbres

Construction d"arbres phylogénétiques

choix des séquences alignement multiple des séquences sélection d"une partie de l"alignement construction de l"arbre UPGMA

NJmaximum

de parcimoniemaximum de vraisemblancemodèle de distancemodèle probabilisteévaluation de l"arbre1 2 3 4 5 Construction d"arbresAlignement multiple des séquences

Alignement multiple des séquences

Toutes les approches phylogénétiques moléculaires commencent par un alignement multiple des séquences 1 beta MVHLTPEEKSAVTALWGKVN--VDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGAFSDGLA delta MVHLTPEEKTAVNALWGKVN--VDAVGGEALGRLLVVYPWTQRFFESFGDLSSPDAVMGNPKVKAHGKKVLGAFSDGLA epsilon MVHFTAEEKAAVTSLWSKMN--VEEAGGEALGRLLVVYPWTQRFFDSFGNLSSPSAILGNPKVKAHGKKVLTSFGDAIK gamma MGHFTEEDKATITSLWGKVN--VEDAGGETLGRLLVVYPWTQRFFDSFGNLSSASAIMGNPKVKAHGKKVLTSLGDAIK theta -MALSAEDRALVRALWKKLGSNVGVYTTEALERTFLAFPATKTYFSHL-DLSP-----GSSQVRAHGQKVADALSLAVE alpha -MVLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHF-DLSH-----GSAQVKGHGKKVADALTNAVA zeta -MSLTKTERTIIVSMWAKISTQADTIGTETLERLFLSHPQTKTYFPHF-DLHP-----GSAQLRAHGSKVVAAVGDAVK myoglobin -MGLSDGEWQLVLNVWGKVEADIPGHGQEVLIRLFKGHPETLEKFDKFKHLKSEDEMKASEDLKKHGATVLTALGGILK 80
beta HLDNLKGTFATLSELHCDKLHVDPENFRLLGNVLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYH------ delta HLDNLKGTFSQLSELHCDKLHVDPENFRLLGNVLVCVLARNFGKEFTPQMQAAYQKVVAGVANALAHKYH------ epsilon NMDNLKPAFAKLSELHCDKLHVDPENFKLLGNVMVIILATHFGKEFTPEVQAAWQKLVSAVAIALAHKYH------ gamma HLDDLKGTFAQLSELHCDKLHVDPENFKLLGNVLVTVLAIHFGKEFTPEVQASWQKMVTAVASALSSRYH------ theta RLDDLPHALSALSHLHACQLRVDPASFQLLGHCLLVTLARHYPGDFSPALQASLDKFLSHVISALVSEYR------ alpha HVDDMPNALSALSDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTPAVHASLDKFLASVSTVLTSKYR------ zeta SIDDIGGALSKLSELHAYILRVDPVNFKLLSHCLLVTLAARFPADFTAEAHAAWDKFLSVVSSVLTEKYR------

myoglobin KKGHHEAEIKPLAQSHATKHKIPVKYLEFISECIIQVLQSKHPGDFGADAQGAMNKALELFRKDMASNYKELGFQGLes zones de faible similarité sont ignorées

Construction d"arbresModèles d"évolution

Distance évolutive

Lap-distance est l"estimation la plus simple de la distance entre deux séquences : p=n/l

avecnle nombre de substitutions etlle nombre de sitesLa distanceévolutive dest supérieure à la distanceobservée p

substitution(s) séquence 1 séquence 2p dsimple C C→A ? ? multiples A A→C→T ? ? coïncidentes C→A C→G ? ? parallèles T→A T→A ? ? convergentes A→T A→C→T ? ?

inverse C C→T→C ? ?Avec un modèle d"évolution, on peut estimerdà partir depSoitλle taux global de substitutions dans une séquenceOn ad=λt

Construction d"arbresModèles d"évolution

Modèle de Jukes-Cantor

modèle à un seul paramètre même taux de substitutionαpour les quatre nucléotides Jukes & Cantor, 1969Matrice de taux de substitution : Q=( ((A C G T

A-3α α α α

Cα-3α α α

Gα α-3α α

Tα α α-3α)

))Matrice de probabilité de substitution :

On aP?(t) =QP(t)

On poseP(t) =(

((A C G T

Ar(t)s(t)s(t)s(t)

Cs(t)r(t)s(t)s(t)

Gs(t)s(t)r(t)s(t)

Ts(t)s(t)s(t)r(t))

))avecr(t) +3s(t) =1

Construction d"arbresModèles d"évolution

Modèle de Jukes-Cantor

On obtient le système d"équations différentielles : r ?=-3αr+3αs s ?=αr-αsQui a pour solutions : r(t) =14 (1+3e-4αt) s(t) =14 (1-e-4αt)tp r(t)s(t)000.250.50.751 tempsprobabilité lorsquet=0,r=1 ets=0 lorsquet→ ∞,r=s=14(fréquences d"équilibre des nucléotides)

Construction d"arbresModèles d"évolution

Distance de Jukes-Cantor

Par définition,d=λt, etλ=3αpour Jukes-CantorLa probabilité globale de substitution estp=3s(t)On obtient :p=34

(1-e-43 d)Et la distance de Jukes-Cantor :d=-34 ln(1-43 p)dp aléatoire

00.511.500.250.50.751

distance évolutivedistance observée lorsquep=75%,d→ ∞

Construction d"arbresModèles d"évolution

Autres modèles

ADN

K80Kimura 1980

2 paramètres, distingue transition et transversion

d=-12 ln(1-2p-q)-14 ln(1-2q)

HKY85Hasegawa, Kishino et Yano 1985

Kimura avec fréquences d"équilibre différentes pour les quatre nucléotides GTR" Generalised time-reversible », Tavaré 1986 le plus général avec la réversibilitéProtéines

PAM" Point Accepted Mutation »

Dayhoff, Schwartz & Orcutt, 1978

Construction d"arbresUtilisation de matrices de distance

Matrices de distance

Une matrice de distancedijest calculée à partir de l"alignement de séquences et d"un modèle de distance- beta delta epsilon gamma theta alpha zeta myoglobin beta 0.00 0.07 0.30 0.34 1.20 0.93 1.18 2.22 delta 0.07 0.00 0.33 0.35 1.17 0.95 1.13 2.14 epsilon 0.30 0.33 0.00 0.22 1.21 1.05 1.03 2.07 gamma 0.34 0.35 0.22 0.00 1.19 0.99 1.03 2.05 theta 1.20 1.17 1.21 1.19 0.00 0.51 0.77 1.87 alpha 0.93 0.95 1.05 0.99 0.51 0.00 0.56 1.88 zeta 1.18 1.13 1.03 1.03 0.77 0.56 0.00 1.64 myoglobin 2.22 2.14 2.07 2.05 1.87 1.88 1.64 0.00(distances calculées avec modèle PAM) Construction d"arbresUtilisation de matrices de distance

Méthode UPGMA

UPGMA =

" unweighted pair group method with arithmetic averages »Sokal & Michener, 1958 méthode standard de clustering hiérarchique ascendant

but : regrouper progressivement les séquencespdans des clustersCidistance inter-cluster :dij=1|Ci||Cj|?

p?Ci,q?Cjdpq avec|Ci|et|Cj|le nombre de séquences dans les clustersCietCj, et d pqla matrice de distance inter-séquencesvariantes : d ij= minp?Ci,q?Cjdpq(saut minimum ou " single linkage ») d ij= maxp?Ci,q?Cjdpq(saut maximum ou " complete linkage ») Construction d"arbresUtilisation de matrices de distance

Méthode UPGMA : algorithme

Initialisation:Attribuer à chaque séquenceison propre clusterCi.Définir une feuille pour chaque séquence, à hauteur zéro.

Itération:Déterminer les deux clustersCietCjpour lesquelsdijest minimale.Définir un nouveau clusterCk=Ci?Cj, et calculerdklpour toutl.Définir un noeudkavec pour descendantsietj,

et le placer à hauteurdij/2.AjouterCkaux clusters courants et supprimerCietCj.Terminaison:Lorsqu"il reste seulement deux clustersCietCj,

placer la racine à hauteurdij/2. Construction d"arbresUtilisation de matrices de distance

Méthode UPGMA : exemple

5 séquences, représentées comme des points du plan•1•2

•3 •4 •5126 457
389
1 2 d68 Construction d"arbresUtilisation de matrices de distance

Hypothèse de l"horloge moléculaire

UPGMA produit des arbres dont les branches peuvent être vues comme des

temps mesurés par une " horloge moléculaire »L"hypothèse de l"horloge moléculaire suppose que les mutations surviennent

à une vitesse constanteLes distances entre un noeud et ses feuilles sont identiques 123
4 arbre correct1423 arbre produit par UPGMA Construction d"arbresUtilisation de matrices de distance

Méthode Neighbor-joining

Ne requiert pas l"hypothèse de l"horloge moléculaire

mais seulement l"additivité des distancesAdditivité des distances : la distance entre une paire

de feuilles est la somme des longueurs des branches le long du chemin qui les reliePour trois feuillesi,j, etm, il y a un noeudkoù les branches vers ces feuilles se rejoignent.Par additivité, on a : d im=dik+dkm,djm=djk+dkm, etdij=dik+djkLa distance du noeudkà la feuillemest donc : d km=12 (dim+djm-dij)Produit un arbre non-racinékm ji Construction d"arbresUtilisation de matrices de distance

Méthode Neighbor-joining

Les feuilles les plus proches ne sont pas forcément voisinesComment déterminer si des feuilles sont voisines à partir des distancesdij?Procédure proposée par Saitou & Nei (1987) et modifiée par Studier & Keppler (1988)On introduitDij=dij-(ri+rj) avecri=1(|L|-2)? m?Ldim et|L|le nombre de feuillesOn peut prouver queDijest minimale si et seulement siietjsont voisines12

340.10.10.1

0.40.4

d

13>d12

mais D

13 Construction d"arbresUtilisation de matrices de distance

Méthode Neighbor-joining : algorithme

Test l"arbre courant

Lest la liste courante des feuillesInitialisation:DéfinirTcomme l"ensemble des noeuds feuilles, un pour chaque

séquence, etL=T.Itération:Choisir une pairei,jdansLpour laquelleDijest minimale.Définir un nouveau noeudkavecdkm=12

(dim+djm-dij), pour toutmdeL.AjouterkàTavec des branches versietjde longueur d ik=12 (dij+ri-rj)etdjk=dij-dik.RetirerietjdeLet ajouterk.Terminaison:LorsqueLcontient deux noeudsietj, ajouter la dernière branche entreietj, de longueurdij.

Construction d"arbresMaximum de parcimonie

Maximum de parcimonie

Principe de parcimonie:

(lex parsimoniae, " principe de simplicité », ou encore " principe d"économie ») " Les hypothèses suffisantes les plus simples sont les plus vraisemblables » rasoir d"Ockham:

Pluralitas non est ponenda sine necessitate

" Les multiples ne doivent pas être utilisés sans nécessité »En phylogénie : trouver l"arbre qui peut expliquer les observations

avec le minimum de substitutions

Construction d"arbresMaximum de parcimonie

Maximum de parcimonie

Deux composantes :1calcul du coût pour un arbre donné

2exploration de l"espace des arbres pour identifier

l"arbre de coût minimal

Exemple :

quatre séquences alignées AAG, AAA, GGA, AGA coût = 1 par substitution trois exemples d"arbres possibles :AAGAAA?

GGAAGA??

111

AAGAGA?

AAAGGA??

112

AAGGGA?

AAAAGA??

121
coût =?3coût =?4coût =?4 i jk {Ri}{Rj}{Rk}Construction d"arbresMaximum de parcimonie

Maximum de parcimonie

Algorithme de parcimonie traditionnelle

minimise le coût total de l"arbre pour un siteu(Fitch, 1971) nséquencesx1,...,xn x iudésigne le résidu de la séquenceiau siteu R kest une liste des résidus de coût minimal pour le noeudk

Cest le coût courant de l"arbreInitialisation:SoitC=0 etk=2n-1.Récursion. Calcul de l"ensembleRk:Sikest un noeud feuille :Rk=xku.Sikn"est pas un noeud feuille :

calculerRietRjpour les noeuds fillesietj, puis R k=Ri∩Rjsi cette intersection n"est pas vide, R k=Ri?Rjsinon et incrémenterC.Terminaison:Le coût minimal de l"arbre estC. i jk {A:Si(A),...}{A:Sj(A),...}{A:Sk(A),...}Construction d"arbresMaximum de parcimonie

Maximum de parcimonie

Algorithme de parcimonie pondérée

minimise le coût total de l"arbre pour un siteu

Sankoff & Cedergren, 1983

S(a,b)est le coût pour une substitution du résiduaversb S

k(a)est le coût minimal pour l"attribution du résiduaau noeudkInitialisation:Soitk=2n-1, le numéro du noeud racine.Récursion. CalculerSk(a)pour toutacomme suit :Sikest un noeud feuille :

S k(a) =0 sia=xku, sinonSk(a) =∞.Sikn"est pas un noeud feuille : calculerSi(a)etSj(a)pour toutapour les noeuds fillesietj, et

obtenirSk(a) = minb(Si(b) +S(a,b)) + minc(Sj(c) +S(a,c)).Terminaison:Le coût minimal de l"arbre estminaS2n-1(a).

Construction d"arbresMaximum de parcimonie

Maximum de parcimonie

Reconstitution de la séquence des ancêtresAjouter des pointeurs de chaque résiduadu noeudkvers les résidus

correspondantsbetcdes noeuds fillesietj, qui minimisaientSk(a) (les pointeurs peuvent avoir plusieurs cibles) : l k(a) = argminb(Si(b) +S(a,b)) r

k(a) = argminc(Sj(c) +S(a,c))À la fin, choisir un résiduaà la racine donnant le coût minimal pourS2n-1,

puis remonter jusqu"aux feuilles en lisant les pointeurs, choisissant arbitrairement lorsque le pointeur a plusieurs cibles.{A:0,B:∞}{A:∞,B:0}{A:?,B:?} {A:0,B:∞}{A:?,B:?} {A:∞,B:0}{A:?,B:?} AB? A? B? xx xx

Construction d"arbresMaximum de vraisemblance

Maximum de vraisemblance

Terminologiesoit un modèle probabiliste de paramètresθ P(x|θ)est laprobabilitéd"observer les résultatsxétant donnés les paramètresθ L(θ|x) =P(x|θ)est lavraisemblancedes paramètresθétant donnés les résultatsxestimer les paramètres d"un modèle probabiliste à partir d"un jeu de données fiableDmaximum de vraisemblance:

ML= argmax

θP(D|θ)si la quantité de données est limitée, risque de surajustement (" overfitting ») par exemple un tirage [pile,pile,pile] donnerait

P(pile) =1,P(face) =0

Construction d"arbresMaximum de vraisemblance

Maximum de vraisemblance

En phylogénieSoit un modèle probabiliste d"évolution, qui permet de calculer les

probabilités de substitutionP(b|a,t)Soit un ensemble denséquencesx1,...,xnOn cherche l"arbreTde longueurs de branchest1,...,t2n-2qui

maximise la vraisemblanceP(x1,...,xn|T,t1,...,t2n-2)

Construction d"arbresMaximum de vraisemblance

Maximum de vraisemblance

Deux séquences

quotesdbs_dbs33.pdfusesText_39

[PDF] transformer photo en cartoon photoshop

[PDF] transformer photo en dessin photoshop

[PDF] transformer photo en bd gratuit

[PDF] phylogénie moléculaire

[PDF] méthode neighbor joining

[PDF] transformer une photo en coloriage

[PDF] mécanique quantique cours pdf

[PDF] transformer photo en dessin couleur photoshop

[PDF] mécanique quantique l2 pdf

[PDF] photoshop effet dessin crayon

[PDF] mecanique quantique 2

[PDF] l'analyse des textes littéraires une méthodologie complète

[PDF] technique collage artistique

[PDF] activité collage maternelle

[PDF] tableau avec collage papier