Reconstruction Phylogenetique par Analyse Bayesienne des Sequences

De
Publié par

Reconstruction Phylogenetique par Analyse Bayesienne des Sequences Samuel Blanquart Projet Methodes et Algorithmes pour la Bioinformatique LIRMM CNRS January 13, 2005

  • distribution de probabilites

  • echantillonner des distributions de probabilites inconnues

  • relations phylogenetiques entre les especes representees par les sequences

  • chaine de markov

  • reconstruction phylogenetique par analyse bayesienne des sequences

  • probabilite des donnees


Publié le : mardi 19 juin 2012
Lecture(s) : 43
Source : lirmm.fr
Nombre de pages : 32
Voir plus Voir moins
ReconstructionPhylogenetiqueparAnalyse BayesiennedesSequences
Samuel Blanquart
Projet Methodes et Algorithmes pour la Bioinformatique LIRMM CNRS
January 13, 2005
Resume
La technique des “Chaines de Markov Monte Carlo” (MCMC) permetdechantillonnerdesdistributionsdeprobabilites inconnues a priori. Le programme PhyloBayes (Nicolas Lartillot,2004)implementeuneMCMCechantillonnantla distribution de probabilite a posteriori induite sur les parametresdunmodeledevolutionparlesdonnees (alignementsdesequences).Cettemethodepermetdestimer lesrelationsphylogenetiquesentrelesespecesrepresenteespar lessequences.Lorsduseminaire,onpresentera:
I,CMCMrapegannollircneLpsantiechdelipes IL’algorithme de Metropolis-Hastings, Icnoiaruovetulosli,esenmmtituodelesdLesm Ie,delnnudseyomuaevuotouajLbalohyaP ILes premiers resultats obtenus pour ce modele.
LetheoremedeBayes
Ou :
P(|D) =P(D|P)(D)P()
IDees,eddsnonneesbmelelst Itrlamenesterembledesepsael,dsmudoe IP(|DemstPoes)omtnoire,r IP(D|sembVraimetnomlpniSmaeuoalcn,gse) IP(momtnes),roirPe IP(Dltpaorabibiltdeesdonnees.se)
(1)
Analyse Bayesienne
Onchercheaconnaitreladistributiondeprobabilitedu posteriorP(|D.O)eunp:ereequivalenteptorcdereedamin IuttournsalsvleestniraPoitargeopssuesrdsebiel, IlreluresPvaanatgieldelcohnandse. soit :
A=ZA()P(|D)d1KA(k) 'KX k=1 Onpeutechantillonnerladistributiondesprobabilitesa posteriori avec une “Chaine de Markov Monte carlo”.
(2)
LeschainesdeMarkov,processusgeneral
Une chaine de Markov : Estunprocessusstochastiqueamemoire niede nisurun espaceX:x={x0, x1, x2, ..., xn, xn+1, ...}netuearsaliontiedse la chaine de Markov surX. Estentierementde nipar: IUn espaceX, InUmeyauounoetirtedisnanoitriatdeceobprilabQ, IUn etat initialx0. Possedelesproprietes: IporP1eteir:P(xn+1|x0, x1, x2, ..., xn) =P(xn+1|xn) I:eir2etporPPtelle que P(xn+1) =PxnP(xn)Q(xn, xn+1)
LeschainesdeMarkov,processusgeneral
Laprobabilitedˆetredansletatxn+1au pasn+ 1 sachant qu’on etait dans l’etatxnau pasnde la chaine de Markov est : Pn+1(xn+1) =XPn(xn)Q(xn, xn+1) xn
Ou :
(3)
IQqutie,otsusahcnatnoeeioninstaetransitamrtcideetsal ou encore le noyau, IPn+1(xn+1obseedrverrpaltse)tilibaboxn+1au pasn+ 1 de la chaine de Markov, IPn(xntedobserverse)paltaborilibxnau pasnde la chaine de Markov, IQ(xn, xn+1renuceutd etieeiondnsitetrailabobprlast)e xnversxn+1.
LeschainesdeMarkov,processusgeneral
Soit une fonctionRsur un espaceX, telle quexR(x)0. SelonlatheoriedeschainesdeMarkov,onpeutproposerune chaine de Markov surXde noyauQtelle queP=R. OnpeutechantillonnerRMedeniahtidvokraegrˆaceacettec chaine de Markov Monte Carlo.
Les MCMC, l’algorithme de Metropolis
OnchercheaechantillonnerunefonctionRavec une chaine de Markovpardefautdenoyauq: Itemuqir,senedeMarkovsontsysntioisnedalhciarastleSi on aq(xn, xn+1) =q(xn+1, xn exprime le rapport de). on Metropolis parM(xn, xn+1) =RR(x(xnn+)1),
ILa transition dexnaxn+1robabiliavecunepteeccaetptse IA(xn, xn+1) = 1 siM(xn, xn+1)1, IA(xn, xn+1) =M(xn, xn+1) siM(xn, xn+1)<1. IL’introduction du calcul d’un rapport d’acceptationA biaise la chaine de Markov de noyauq obtient une. On chaine de Markov de noyau Q(xn, xn+1) =q(xn, xn+1)A(xn, xn+1) dont la distribution stationnaireP=R.
Les MCMC, l’algorithme de Metropolis-Hastings
Ide la chaine de Markov ne sont pasSi les transitions symetriques,onaq(xn, xn+1)6=q(xn+1, xn).
IcdtnHleasaOitidortcorpprs.alneglecuruetcerH(xn, xn+1) =qq((xxnn,+x1n,x+n1)) IOn exprime le rapport+1d)e Mqe(txrno+1p,olis)-Hastings par M H(xn, xn+1) =R(Rx(nxn)q(xn,xnx+n1). IitildeceacatptlacnelucrpalbaboOoinA. IA(xn, xn+1) = 1 siM H(xn, xn+1)1, IA(xn, xn+1) =M H(xn, xn+1) siM H(xn, xn+1)<1. IOn obtient un chaine de Markov de noyau Q(xn, xn+1) =q(xn, xn+1)A(xn, xn+1).
AnalyseBayesienneetalgorithmeMetropolis

Dans le cas de l’analyse bayesienne, la fonction que l’on echantillonne est le posterior. Le rapport de Metropolis est le rapport de deux posteriors consecutifs d’une MCMC:
M(n, n+1) =PP((n+n1||DD))
Soit,enutilisantletheoremedeBayes(formule1):
M(n, n+)P(DP(|D|n+1n))PP((n)+1) 1= n
Laprobabilitedacceptationdunnouveletatn+1est:
A(n, n+1) = min(1, M(n, n+1))
(4)
(5)
(6)
L’algorithme Metropolis, Exemple
I
I
Accepterunnouveletatn+1: P(n|D) = 0.8 P(n+1|D) = 0.9 M(n, n+1) =00..89= 1.125 A(n, n+1) = min(1,1.125) = 1
Refuserunnouveletatn+1: P(n|D) = 0.8 P(n+1|D) = 0.5 M(n, n+1) =00..58= 0.625 A(n, n+1) = min(1,0.625) = 0.625
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.