CpG Island Detection with a Hidden Markov Model

Advanced Computational Biology HMM Viterbi CpG Island
Significance:

CpG islands are GC-rich regions that mark the promoters of most housekeeping genes, and their
methylation state is central to gene silencing and cancer epigenetics. Finding them is the
textbook application of hidden Markov models in biology: the island state is hidden, and only the
emitted bases are observed. Viterbi decoding recovers the most likely hidden path.

Statement

Given a DNA sequence, use Viterbi decoding to find the most likely sequence of hidden states.

There are two states: H (inside a CpG island, GC-rich) and L (outside one, AT-rich).

Model parameters:

Initial:      P(H) = 0.5        P(L) = 0.5

Transitions:  H -> H = 0.8      H -> L = 0.2
              L -> H = 0.2      L -> L = 0.8

Emissions:    H:  A 0.15  C 0.35  G 0.35  T 0.15
              L:  A 0.35  C 0.15  G 0.15  T 0.35

Print the most likely state path as a single string of H and L characters — one character per
input base, no spaces.

If two paths are exactly equally likely at some step, prefer state H.

Input — read from standard input
Variable Type Description
s
line 1
 str The DNA sequence to decode
1 <= len(s) <= 1000, uppercase A, C, G, T only

These variables are already read for you in the starter code on the right.

Output

str the most likely state path, one 'H' or 'L' per input base, no spaces

Sample Cases
Sample 1
Input
ATATATGCGCGCGCATATAT
Expected Output
LLLLLLHHHHHHHHLLLLLL
The AT-rich flanks decode to L and the GC-rich core to H — the model finds the island.
Sample 2
Input
AAAAAAAAAA
Expected Output
LLLLLLLLLL
An entirely AT-rich sequence stays in the L state throughout.

Submit also runs your code against 5 hidden test cases. Hidden inputs are never shown — if one fails you'll get its number and a description of the mismatch, not the data.

Constraints
  • 1 <= length(s) <= 1000
  • Uppercase A, C, G, T only
  • Ties are resolved in favour of H
  • Work in log space to avoid floating-point underflow on long sequences
Further Reading
  • Multiplying hundreds of probabilities underflows to zero; add log probabilities instead.
  • Keep a back-pointer per position per state, then walk backwards from the better final state.
  • Don't expect the path to follow the bases one-for-one. Staying put is four times likelier than
    switching (0.8 vs 0.2), so a short AT dip inside a GC-rich stretch will often stay in H —
    paying two transitions costs more than the emissions gain. That stickiness is the point of
    using an HMM rather than a per-base threshold.
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...
Expected: s (str)
Next Problem
Mendelian Inheritance Probability