Significance:
CpG islands — GC-rich regions often found near gene promoters — are biologically important markers used in epigenetics and gene-finding pipelines, and they are the textbook motivating example for Hidden Markov Models in bioinformatics (this exact problem appears in Durbin et al.'s *Biological Sequence Analysis*, the field's standard reference text). The key insight is that you never directly observe whether a base is "inside" or "outside" an island — you only observe the DNA sequence itself — so you must infer the most likely underlying hidden state path using the Viterbi dynamic programming algorithm. This is the same class of algorithm used in gene-prediction tools (like GENSCAN) to infer exon/intron boundaries.
Statement
Model a DNA sequence as generated by a 2-state Hidden Markov Model with hidden states `H` (High-GC / "CpG island") and `L` (Low-GC / "background"):
Given an observed DNA sequence, use the **Viterbi algorithm** to find the single most probable sequence of hidden states (the "path") that could have generated it. Output the path as a string of `H`/`L` characters, one per input base.
Sample Input
GCGCGATCGC
Sample Output
HHHHHLLHHH
Constraints
- `1 ≤ length(sequence) ≤ 500` - Use log-space probabilities internally to avoid floating-point underflow on long sequences (this is a required implementation detail, not optional — sequences near the upper length bound will underflow standard floats if you multiply raw probabilities directly)
My Notes
Log in to save personal notes.
Console output will appear here when you click Run Code or Submit...