Noisy Pattern Search using Hidden Markov Models

We have a pattern string david that we wish to search for in an observation string, say fgidavidjj. More generally, we might have a dictionary of patterns david anton fred jim barry and wish to check where they may appear in the observation string. There are classical fast algorithms that can do this, for example the Aho-Corasick algorithm [1]. The complexity of the Aho-Corasick algorithm is linear in the length of the observation string and linear in the total length of the dictionary. 2 Noisy pattern search When the observation string is potentially corrupted with noise, we cannot apply the standard Aho-Corasick algorithm. One approach in this case is to use a Hidden Markov Model (HMM) which defines a distribution over a set of observations v1,..., vT (or v1:T for short) and corresponding hidden variables h1:T: p(v1:T, h1:T) = p(h1)p(v1|h1) T∏ t=2 p(vt|ht)p(ht|ht−1) (1) whose structure as a belief network is represented in figure(1). In this case the hidden variables h1:T represent the ‘clean ’ sequence and the variables v1:T the observed sequence. The ‘emission ’ matrix p(vt = i|ht = j) ≡ Bij