Seminár teoretickej informatiky

Fri 15 May. 2009, 11:00
M-213

Title: On-line Viterbiho algoritmus a jeho analýza
Speaker: Broňa Brejová

Skryté Markovove modely (HMM) sa často používajú v bioinformatike na
rozpoznávanie rôznych prvkov v DNA sekvenciách, ako sú gény, CpG
ostrovy a evolučne konzervované oblasti. Klasický Viterbiho algoritmus
pre HMM používa pamäť Theta(mn) na analýzu postupnosti dĺžky n s
m-stavovým modelom, čo je nepraktické, ak analyzujeme dlhé
postupnosti, napríklad celé chromozómy. Na tomto seminári predstavíme
on-line Viterbiho algoritmus, ktorý používa oveľa menšiu pamäť.
Ukážeme, že pre dvojstavové modely je priemerná pamäť Theta(mlogn) a
tento odhad sa dá rozšíriť aj na niektoré viacstavové modely. Naopak,
pre niektoré modely algoritmus potrebuje Omega(n) pamäť a pre ďalšie
skupiny modelov je ich priemerná pamäťová zložitosť zatiaľ otvorená.

Spoluautori: Rasťo Šrámek, Tomáš Vinař, Uri Keich (prvá časť
publikovaná na WABI 2007, na ďalšej analýze stále pracujeme)