Suivez le guide : en quête de HMM

Hidden Markov Model | licence Wikipedia
Hid­den Mar­kov Model | licence Wiki­pe­dia

Bases Théoriques :

Une chaîne de Mar­kov , ça vous dit quelque chose ? Une classe de modèles de Mar­kov, appe­lée Modèle de Mar­kov Caché (Hid­den Mar­kov Model, HMM), est un modèle mathé­ma­tique per­met­tant de seg­men­ter un signal obser­vé en régions (états cachés) défi­nis par le modèle. Lequel est com­po­sé de quatre élé­ments : N états, une matrice d’émissions, des condi­tions ini­tiales et une matrice de tran­si­tion. Le rôle de la matrice de tran­si­tion est de défi­nir la pro­ba­bi­li­té de pas­ser d’un état à un autre ou de le main­te­nir inchan­gé au cours d’un cer­tain nombre d’observations. Quant à la matrice d’émissions, elle défi­nit la pro­ba­bi­li­té d’émission d'un cer­tain signal en fonc­tion de l'état caché.

Com­pli­qué ? Pas du tout. Voyez par exemple le cas d’un modèle à deux états. Ce type d’algorithme  a fait ses preuves dans dif­fé­rents domaines tels que la recon­nais­sance vocale (Juang Rabi­ner, Tech­no­me­trics 1991), la détec­tion de domaines topo­lo­giques issus de don­nées de séquen­çage High‑C (Dixon,Nature 2012), et dans le « foot prin­ting » de don­nées DNA­se1-seq (Boyle, Genome Res 2011) entre autres.

Nous allons ici détec­ter des pat­terns dans des séquences d’ADN à l’aide d’une librai­rie R nom­mée  « HMM » et apprendre par l’exemple cer­taines des fonc­tions de cette librai­rie.

ISOCHORE dans la ligne de mire

Objec­tif : détec­ter auto­ma­ti­que­ment une région ISOCHORE riche en GC de 10 paires de bases (pb) dans une séquence d’ADN  (ATGC) d’une lon­gueur de 100 pb. Un ISOCHORE est défi­ni par un conte­nu en GC de 50% et un conte­nu en AT de 50%. Dans le reste du génome (ou de notre séquence à ana­ly­ser) le conte­nu en GC est de 20% et le conte­nu en AT est de 80%.

Pre­mière étape : défi­nir le modèle. À savoir, le nombre d’états, la matrice d’émission et la matrice de tran­si­tion. Dans le cas pré­sent, deux états : ISOCHORE et NON-ISOCHORE. Sachant que la lon­gueur d’un iso­chore est de 10 pb envi­ron et que la séquence ana­ly­sée est de 100 pb, voi­ci une défi­ni­tion de la matrice (de dimen­sions 2x2) de tran­si­tion entre les deux états :

matrice de tran­si­tion ISOCHORE NON-ISOCHORE
ISOCHORE 9/​10    (1‑p) 1/​10     (p)
NON-ISOCHORE 1/​90    (q) 89/​90  (1‑q)

 

Pour cet exemple, la pro­ba­bi­li­té de res­ter dans l’état ISOCHORE est de 9/​10 ; en effet, un iso­chore fait envi­ron 10 pb de long et la pro­ba­bi­li­té de pas­ser de l’état ISOCHORE à l’état NON- ISOCHORE est de 1–9/10. De plus, sachant que la lon­gueur totale de la séquence est de 100 pb, 90 obser­va­tions sur 100 sont dans l’état NON-ISOCHORE. Ain­si, la pro­ba­bi­li­té de pas­ser de l’état NON-ISOCHORE à l’état ISOCHORE est de  1/​90= 1/(100–10) et la pro­ba­bi­li­té de res­ter dans l’état NON-ISOCHORE de 1–1/90 =89/​90.

La matrice d’émissions du modèle est donc défi­nie comme suit :

Matrice d’emmission

ISOCHORE

NON-ISOCHORE

A

0.25

0.4

T

0.25

0.4

G

0.25

0.1

C

0.25

0.1

Elle per­met de déter­mi­ner la pro­ba­bi­li­té d’une obser­va­tion don­née selon l’état caché. En ce qui concerne ISOCHORE, nous avons 50% de GC et 50% de AT, donc une pro­ba­bi­li­té égale de 25% pour chaque obser­va­tion A, T ,G,C. Dans le cas de l’état NON-ISOCHORE, un biais appa­raît, avec 80% de AT donc 40% de A, 40% de T, 10% de G et 10% de C.

Enfin, dans ce modèle, la pro­ba­bi­li­té  ini­tiale d’être dans l’un ou l’autre des états a été défi­nie à 90% pour l’état NON-ISOCHORE et à 10% pour l’état ISOCHORE.

Le modèle com­plet est repré­sen­té dans la figure sui­vante.

HMM ISOCHORE

Les miracles de la librairie HMM pour R

Deuxième étape : ins­tal­ler la librai­rie HMM pour R. Pour cela, uti­li­sez les com­mandes sui­vantes :

Puis défi­nis­sez le modèle décrit plus haut :

Ensuite, il faut simu­ler. Soit créer une simu­la­tion de la séquence obser­vée à par­tir du modèle ou alors ana­ly­ser une séquence d’intérêt puis détec­ter la région ISOCHORE. Marche à suivre pour créer une séquence d’ADN  de lon­gueur 100 bp conte­nant une ISOCHORE :

Pour ana­ly­ser une séquence d’observations non simu­lée par le modèle, vous pou­vez détec­ter les états cachées avec la fonc­tion Viter­bi de la librai­rie HMM.

Si vous n’y voyez pas clair, c’est nor­mal. Pour vous aider :

Voi­ci ce que vous devez obte­nir :

visualsation des résultats du HMM et de la séquence à analyser

Le panel supé­rieur montre la loca­li­sa­tion des G/​C ou des A/​T le long de la séquence de 100 pb. Quant au panel infé­rieur, il indique l’analyse du modèle par rap­port à la séquence. Le HMM a détec­té un ISOCHORE entre les bases 44 et 58.

Pour les pro­ba­bi­li­tés en marche avant et en marche arrière, c’est par ici :

Enfin, cette librai­rie per­met d’utiliser l’algorithme de Baum-Welch  pour amé­lio­rer les per­for­mances du modèle et ajus­ter les para­mètres à un test set. Voi­ci com­ment :

Ami-e‑s en quête des mys­tères des HMM, j’espère avoir éclai­ré votre lan­terne avec ce bref tuto­riel dont j’ai volon­tai­re­ment reti­ré les détails algo­rith­miques pour ne pas aggra­ver votre mal de tête ! Et si le Graal vous hante, ne renon­cez pas à vous en empa­rer en fouillant dans la lit­té­ra­ture exis­tante sur les algo­rithmes de Viter­bi, « For­ward » , « Back­ward » , et autres joyeu­se­tés telles que Baum-Welch.

Que la force soit avec vous !

Un grand mer­ci à nal­lias, Estel, mura­veill, Aline Jac­cot­tet et  Hatice Akar­su pour leur relec­ture.



Pour continuer la lecture :


Commentaires

2 réponses à “Suivez le guide : en quête de HMM”

  1. Bon­jour,

    Mer­ci pour ce tuto très expli­cite !

    Je dis­pose d'une matrice fré­quen­tielle (type WPM) qui repré­sente une région en ATCG variables et je sou­hai­te­rai détec­ter la pré­sence de cette région en par­ti­cu­lier au sein de séquences dif­fé­rentes de tailles dif­fé­rentes. Le HMM semble idéal pour trou­ver une solu­tion !

    Existe-t-il des outils faci­li­tant la concep­tion d'un HMM ou une publi­ca­tion trai­tant du pas­sage d'une matrice de WPM à une matrice d'émission ?

    En vadrouillant un peu, je suis tom­bé sur des solu­tions alter­na­tives d'HMM à ordre mul­tiples ou de par­ci­mo­nie qui semble plus adap­té que le HMM pré­sen­té ici à ma pro­blé­ma­tique mais je crains d'être hors-sujet et de com­plexi­fier la solu­tion !

    Mer­ci d'avance !

  2. Bon­jour
    Je suis un étu­diant en infor­ma­tique et s'il vous plaît j'aimerais avoir un aper­çu sur mon thème de mémoire "l'exploitation des chaînes de Mar­kov cachées(HMMs) pour la pré­dic­tion en fouilles de don­nées"

Laisser un commentaire