Viterbi Decoding

The CpG-Island HMM

A hidden Markov model combines start, transition, and emission probabilities.

highlighted = computed this step

The model has hidden states and emissions

The HMM has two hidden states: I for CpG island and N for normal background. Each state emits G or A.

hidden path⟶observed sequence\text{hidden path} \longrightarrow \text{observed sequence}
Running HMM parametersStart, transition, and emission probabilities are exact fractions.StateStart probabilityI1/2N1/2FromINI3/41/4N1/43/4StateGAI3/41/4N1/43/4

Decoding asks for the most likely path

Given the observed sequence, Viterbi decoding finds the single hidden state path with the largest joint probability.

arg⁡max⁡pathP(path,observations)\arg\max_{\text{path}} P(\text{path},\text{observations})
Running HMM parametersStart, transition, and emission probabilities are exact fractions.StateStart probabilityI1/2N1/2FromINI3/41/4N1/43/4StateGAI3/41/4N1/43/4