Statistique pour la bio-informatique

Description

Statistique pour la bio-informatique
Seance 9-10 - Decembre 2003
Chaˆ nes de Markov cachees
1 Chaˆnes de Markov cachees et applications
Les modeles a donnees latentes (ou manquantes ou cachees) constituent des outils
puissants pour modeliser des systemes dont la dynamique e ectue des transitions entre
di erents etats impossible a observer directement. Dans une chaˆ ne de Markov cachee,
lesdi erentsetatsd’unsystemepeuventˆetrecaracterisesparunnombre nidevaleurs.
Onpassealorsdel’etats al’etats aveclaprobabilitep lorsd’unetransition.Dansi j s ,si j
chaque etat, le systeme est susceptible emettre un symbole o pris dans un alphabet O
ni ( O pour observable). La probabilite d’emission du symbole o peut dependre de
l’etat s. Nous la notons q .s,o
Les algorithmes dedies aux chaˆ nes de Markov cachees sont des algorithmes d’es-
timation statistique. Etant donnee une suite d’observations de longueur T, o ,...,o ,1 T
ils ont pour objectif typique d’estimer la suite d’etats s ,...,s la plus probable. Pour1 n
cela, il faudra ajuster correctement les parametres du modeles P = (p ) et Q = (q )s ,s soi j
a partir d’un ensemble de n sequences dont les etats sont connus.
Le premier objectif est generalement rempli par l’algorithme deViterbi. Le second
objectif est rempli par l’algorithme EM, dont la version speci que aux CMC s’appelle
algorithme de Baum-Welch.
1.1 Applications
Les applications des CMC (ou d’autres modeles a structure latente comme les
reseaux de neurones) sont tres ...

Sujets

• Cachen
• Crédit mutuel Centre Est Europe
• Calcul parasitaire
• Bio-informatique
• Valeur de la biodiversité
• Estimation par noyau

Informations

• Publié par: Mothung
• Nombre de lectures: 89
• Langue: Catalan

Extrait

Statistique pour la bio-informatique S´eance9-10-Decembre2003 ChaıˆnesdeMarkovcach´ees

1ChaıˆnesdeMarkovcach´eesetapplications Lesmode`lesa`donne´eslatentes(oumanquantesoucache´es)constituentdesoutils puissantspourmod´eliserdessyste`mesdontladynamiqueeffectuedestransitionsentre diffe´rentse´tatsimpossible`aobserverdirectement.DansunechaˆınedeMarkovcache´e, lesdiff´erents´etatsd’unsyst`emepeuventeˆtrecaracte´ris´esparunnombrefinidevaleurs. Onpassealorsdel’´etats i tate´’la`s j t´libibaroapclveaep s i ,s j lors d’une transition. Dans chaque´etat,lesyst`emeestsusceptiblee´mettreunsymboleopris dans un alphabetO fini (Obarolibiedt´em’´issiudnobmyselopouorsbreavlb)eL.paodeenerd´dpeeptu l’´etats. Nous la notonsq s,o . Lesalgorithmesd´edi´esauxchaˆınesdeMarkovcach´eessontdesalgorithmesd’es- timationstatistique.Etantdonn´eeunesuited’observationsdelongueurT,o 1 , . . . , o T , ilsontpourobjectiftypiqued’estimerlasuited’´etatss 1 , . . . , s n la plus probable. Pour cela,ilfaudraajustercorrectementlesparam`etresdumod`elesP= (p s i ,s j ) etQ= (q so ) a`partird’unensembledenonntnluess.´etuaetnscsoenstdco´sqe Lepremierobjectifestg´en´eralementrempliparl’algorithmedeViterbi. Le second objectifestrempliparl’algorithmeEM,dontlaversionsp´ecifiqueauxCMCs’appelle algorithme deBaum-Welch.

1.1 Applications LesapplicationsdesCMC(oud’autresmode`lesa`structurelatentecommeles re´seauxdeneurones)sonttr`esnombreusesenbio-informatique.Nousillustronscette approchea`l’aidedel’exempleclassiquelarecherchedege`nesquenoussimplifierons`a l’extreˆme(cflogicielgenscande Burge et Karlin, 1997).

1.2AlgorithmiquedeschaıˆnesdeMarkovcach´ees Dans cette section, nous notonsSchcatsta´eesedblsnmele’tese´S t eassoci´eenıˆahcal ∀s 1 , s 2 ∈ S, p s 1 ,s 2 = P(S t+1 =s 2 |S t =s 1 ). 1

Nous notonsπla loi initiale de la chaˆıne π s = P(S 1 =s). Nous notonsO`amentesedblemns’elbaelesvrstboe´atelleionnndits.CoS t =s´neeadon,l X t est donc issue de la loi ∀o∈ O,P(X t =o|S t =s) =q s,o . Ayantobserv´eunes´equencedelongueurT,o 1 , . . . , o T arvamesinalbudecer`mtea,plar multidimensionnel θ= (π, P, Q) este´galea` L(θ) = P(o 1 , . . . , o T ;θ). 1.2.1 Algorithmeforward La vraisemblanceL(θvrlaseaipoes`and)rroceinclamb`eplomncomnu’deta`ele`d donne´esmanquantes X L(θ) =P(o 1 , . . . , o T |s 1 , . . . , s T ;Q) P(s 1 , . . . , s T ; (π, P)). s 1 ,...,s T Pr´ecisement,nousavons X L(θ) =p qπ q∙ ∙ ∙.p q s 1 s 1 ,o 1 s 1 ,s 2 s 2 ,o 2 s T−1 ,s T s T ,o T s 1 ,...,s T Cetteformulesugge`reunalgorithmedecalculna¨ıf,dontlacomplexit´edel’ordre T O(T(#Sgo-unalpadimeneelocuˆrtrendrait))eivo’dtnitulrpnof.tisoLarotpbihi rithme de programmation dynamique. Il repose sur le calcul de la grandeur ∀s∈ S, α t (s) = P(o 1 , . . . , o t , S t =s). Cettegrandeurrepr´esentelaprobabilite´d’observero 1 , . . . , o t veclauatate´’spmett, S t =s.

Proposition 1.1Algorithme forward.Soito 1 , . . . , o T une suite d’observations provenant d’une CMC. Posons ∀s∈ S, α 1 (s) =π s q s,o 1 2

et, pour toutt= 2, . . . , T, X ∀s t ∈ S, α t (s t ) =α t−1 (s)p s,s t q s t ,o t . s Nous avons X L(θ) =α T (s) s∈S 2 L’algorithmedecalculassocie´estdecomplexit´edel’ordredeO(T(#S) ).

De´monstration.

Demani`ereunpeumoinsnaturelle,maiscomple`temente´quivalente,nouspouvons consid´ererunevariablequiremontelesensdutemps.Cettevariableestappele´eva- riable backward ∀s∈ S, β t (s) = P(o t+1 , . . . , o T |S t =s). Cettegrandeurrepre´sentelaprobabilit´ed’observero T , . . . , o t+1 `antmeleelnntioiocdn S t =s.

Proposition 1.2Algorithme backward.Soito 1 , . . . , o T une suite d’observations provenant d’une CMC. Posons ∀s∈ S, β T (s) = 1 et, pour toutt= 1, . . . , T−1, X ∀s t ∈ S, β t (s t ) =β t+1 (s)p s t ,s q s,o t+1 . s Nous avons X L(θ) =π s β 1 (s)q s,o 1 s∈S 2 L’algorithmedecalculassocie´estdecomplexite´del’ordredeO(T(#S) ).

De´monstration.

3

1.2.2 Algorithmede Viterbi L’algorithmedeViterbipermetdecalculerlasuited’e´tatscache´slaplusprobable vu les observationso 1 , . . . , o T ∗ ∗ s ,. . . , s= a 1T rg maxP(o 1 , . . . , o T ∩s 1 , . . . , s T ;θ) Notonsquelavaleurmaxestappel´eescore de Viterbi. On l’obtient formellement enrempla¸cantlasommeparlemaximumdansl’expressiondelavraisemblancein- compl`eteL(θdnoc`tiuareenhtc´reeneulma´meriaxtuimvdemmena`irene)¨.aRveıcmhe unalgorithmedecomplexite´exponentiellementcroissanteenlalongueurdesobserva- T tions (O(T(#Snuetsnoriuruvposcone,ntusno´rcee´edestcoipnmedansla))).Com 2 algorithmecomplexit´equadratiqueO(T(#S) ). Cet algorithme, ditalgorithme de Viterbipmalc¸naltsamoemparlemax.o’seitbsintlempntmereen

Proposition 1.3Algorithme de Viterbi.Soito 1 , . . . , o T une suite d’observa- tions provenant d’une CMC. Posons ∀s∈ S, v(s) =π q 1s s,o 1 et, pour toutt= 2, . . . , n, ∀s t ∈ S, v t (s t ) = max{v t−1 (s)p s,s t q s t ,o t }. s Nous avons ∗ smax= argv T (s) T s et, pour toutt=T−1, . . . ,1,

D´emonstration.

1.2.3 Exercices

∗ s=axargm{v t (s)p s,s }. ∗ t t+1 s

Exercice 1.On pose ∀s∈ S, γ t (s) = P(S t =s|o 1 , . . . , o T ;θ). 4