Cuprins

Lanţuri Markov & Modele Markov Ascunse – Aplicaţii

Lanţuri Markov & Modele Markov Ascunse – Aplicaţii

Exemplu

Fie un lanţ Markov ascuns cu trei stări s1, s2, s3 şi trei simboli de emisie observabili X, Y, Z. Probabilităţile de start, tranziţie, şi de emisie sunt definite de următoarele matrice:

  1. Desenaţi automatul nedeterminist corespunzător acestui lanţ Markov.
  2. Presupunînd că acest lanţ a emis secvenţa de semnale XZXYYZYZZ, identificaţi cea mai probabilă secvenţă de stări corespunzătoare, precum şi probabilitatea acestei emisii.

Temă

Folosiţi o implementare proprie sau disponibila pe internet pentru HMM, în vederea rezolvării următoarelor două probleme:

  1. Un cazino foloseşte două perechi de zaruri, una corectă şi una măsluită, pe care le poate interschimba fără să observe clientul. La un zar corect, probabilitatea fiecărei feţe este aceeaşi (1/6), în timp ce, la unul măsluit, faţa 6 are probabilitatea 1/2, celelalte 5 având probabilităţi egale de 1/10.

    Vom presupune că se trece de la zar corect la zar măsluit cu o probabilitate de 0.05 înainte de fiecare aruncare, resprectiv de la zar măsluit la zar corect cu o probabilitate de 0.1.

    Folosiţi algoritmul Viterbi pentru a stabili, dată o secvenţă de rezultate ale aruncărilor, care corespund unui zar corect şi care corespund unui zar măsluit. Testaţi pe:

    544552213525245666363632432522253566166546666666533666543261
fffffffffffflllllllllllfffffffffffflllllllllllllllllllffffff

363546253252546524422555242223224344432423341365415551632161
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

144212242323456563652263346116214136666156616666566421456123
fffffflllfffffffffffffffffffffffflfllllllllllllllllfffffffff

346313546514332164351242356166641344615135266642261112465663
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
  2. Identificarea de Insule CpG în secvenţe genetice; conform abordării prezentate în curs.
    1. Cum alegeţi probabilitătile de tranziţie între stările corespunzătoare insulelor CpG şi celelalte stări?
    2. Ar fi potrivit, pentru modelarea problemei, un lanţ Markov care are doar două stări: una pentru emisia simbolurilor din insulele CpG, şi alta pentru emisia celor din afara insulelor CpG? Justificaţi.

Resurse