A rejtett Markov láncok nagyon hasonlóak a korábban bemutatott Markov láncokhoz, de van bennük egy csavar. Minden állapot bizonyos valószínűséggel emittál egy másik állapotot, amit látunk. Ezért az eredeti állapotot mi nem látjuk, tőlünk rejtve van, ezért hívják rejtett Markov láncoknak.
Például, ha azt vesszük, hogy egy (nagyon is leegyszerűsített) genomon egymást követik a fehérje kódoló, és nem kódoló szakaszok, akkor ez lehet egy rejtett állapot. Ezt mi nem látjuk (legalábbis a modell szerint, kísérleteket természetesen tervezhetünk a kimutatására). Amit látunk, az a DNS bázissorrend. Ha hétköznapi módon akarnék fogalmazni, a rejtett Markov lánc a közvetett bizonyítékok vizsgálatán alapul.
Gyakorati szempontból három algoritmust szoktak tárgyalni, ami a rejtett Markov láncok három alkalmazási módjával áll kapcsolatban. A Forward-Backward algoritmus, a Viterbi algoritmus és a Baum-Welch algoritmus.
Az első segítségével a modell paramétereit és megfigyelt állapotok kapcsolatát lehet számszerűsíteni, magyarul, mennyire jó a modellünk a megfigyelt adatokra. A Baum-Welch a látható állapotok alapján a modellünk paramétereit határozza meg.
A bioinformatikában általában a Viterbi algoritmust használják, mert ez mondja meg, hogy mi a legvalószínűbb rejtett állapot, ha ismerjük az emittált állapotokat. A példánknál maradva, hol vannak a kódoló/nem kódoló szakaszok, ha ismerjük a DNS bázissorrendjét.
A rejtett Markov láncokról rengeteget lehet olvasni a Wikipédián, én nem is akarom újra leírni azt. Amit viszont fontos megismerni, hogy mi a módszer gyengesége, mert a későbbi posztokban utalni fogok rá.
Ezért írtam egy kis programot, ami nem csinál mást, mint generál egy Markov láncot, és abból emittál bizonyos valószínűséggel egy másik állapotot. Ez most az időjárásos példa a Wikipédiából. Utána egy Viterbi algoritmussal visszafejti azt. Tehát egyszerre látjuk, miből indultunk ki, és mi lett a keresés eredménye.
Nyugodtam írjuk át a programban a valószínűségi értékeket, hogy lássuk, milyen hatással van az eredményekre. (Ha telepítve van a Go fordító, akkor a go build hmm.go paranccsal fordíthatjuk.)
Ha megnézünk egy tipikus kimenetet, akkor nem sok eltérést fogunk látni. Olyan esetekben lesz eltérés például, ha napos idő esetén is takarítanak. Mivel napos időben csak 0,1 a valószínűsége, hogy valaki takarít, ezért a Viterbi inkább az esős idő felé hajlik ilyen esetekben. Ez nem is meglepő, hiszen ez a legvalószínűbb állapot.
A másik fontos észrevétel, hogy az állapot átmeneteknél egyfajta "késés" van a valódi és a Viterbi által visszafejtett állapotok között. Igazából, ez sem meglepő, ha belegondolunk. Napos idő után nagy valószínűséggel megint napos lesz, esős után esős. Ha történik egy átmenet naposból esősbe (vagy vissza), akkor az algoritmus, ami csak az emittált állapotok alapján dolgozik, pár lépéssel később végzi el a váltást. (Persze ez is a valószínűségektől függ. Ha minden rejtett állapot csak egyfélét emittál, akkor ez a késés nem jelentkezik.)
És mi a helyzet a HMM profilokkal?
A bioinformatikában a rejtett Markov láncok alkalmazásának másik nagy területe a különböző profilok létrehozása, elsősorban fehérje alapon. Itt szó szerint rejtett állapotok vannak. Mit értek ez alatt? Az időjárásos példánál a rejtett állapot egy valódi entitás volt (maga az időjárás), csak nem szerezhettünk róla információt. A fehérje profiloknál viszont a rejtett állapot egy meg nem fogható jellemzője a fehérjének. Csupán egy absztakció, még akkor is, ha szoros kapcsolatban van az aminosav fehérjében betöltött pozíciójával. Amit mi látunk, tehát az emittált állapot, maga a fehérje aminosav sorrendje.
Most jön a trükk. Hogyan lesz ebből a megfoghatatlan valamiből profil? Hiszen nekünk ismernünk kell az emittált valószínűségeket. Úgy, hogy fogunk sok - valamilyen tulajdonság alapján hasonló - fehérjét és végzünk egy többszörös illesztést. Ha egy pozícóban csak glicin van, akkor az a rejtett állapot 100%-ban glicint emittál. Egy másik pozícióban azt látjuk, hogy néha alanin, néha fenilalanin van, akkor a modellben annak megfelelően állítjuk be a valószínűségeket, hogy a többszörö illesztésben hányszor fordul elő az adott aminosav.
Még a deléciók és inszerciók sem jelentenek problémát, hiszen azokat is felvehetjük rejtett állapotnak. Az inszerciók szintén emittálnak aminosavat, de a deléciók nem fognak semmit emittálni, a szerepük, hogy át tudjunk ugrani a következő állapotba.
Leegyszerűsítve, a többszörös illesztés oszlopai a rejtett állapotok, a sorok pedig az emittált állapotok. Itt az állapot átmeneteknek kisebb szerep jut. Képzeljünk el egy olyan többszörös illesztést, ahol nincsenek inszerciók, sem deléciók. Minden állapot 100%-ban átmegy a következő aminosavat emittáló állapotba. A profilban az igazi információt az emittálási valószínűségek fogják adni, mert abból derül ki, milyen aminosavat tartalmazhatnak az egyes pozíciók.
Talán ebből is látszik, hogy a rejtett Markov láncok rendkívül rugalmasan alkalmazhatóak. Nem véletlen, hogy szinte minden programozási nyelvhez adtak ki modulokat, amelyek segítségével rejtett Markoc láncokat kezelhetünk. Python alatt a hmmlearn csomagot érdemes használni, mert az közeli kapcsolatban van a sci-kit learn csomaggal. R alatt több lehetőségünk is van, az rHMM, a HMM és a depmixS4.
