Coursework

Algorithms

Dynamic programming applied to biological sequences.

Hidden Markov models, Viterbi decoding and sequence folding.

Project 1

Gene finding with a hidden Markov model

A two-state hidden Markov model that labels every base of a DNA sequence as background or gene, decoded with the Viterbi algorithm.

Stack: Python
NumPy
Dynamic programming
Who and when: Course project
My contribution: I implemented the model, the sequence generator and the Viterbi decoder.

Working demo

Runs in your browser

Try this: Make alpha larger, or the switch probability smaller, and watch the decoded gene regions sharpen.

Runs entirely in your browser with a seeded random generator. Nothing is sent anywhere.

Loading demo...

Two hidden states: background, where every base is equally likely, and gene, where A and G have probability alpha and C and T have probability beta, with 2(alpha + beta) = 1.
A stay probability of 0.95 and a switch probability of 0.05 between states.
Viterbi decoding in log space with a back-pointer table, then a backtrack to recover the labels.
A generator that plants genes in a random sequence, so the decoded labels can be scored against the truth.

For each position the decoder keeps the best log-probability of ending in each state, from either staying or switching.
Working in log space avoids numerical underflow on long sequences.
The back-pointers record which state each best path came from, and the backtrack walks them from the end.

Sliders for alpha, the switch probability, the sequence length and the seed.
A heat map of the Viterbi table with the winning path highlighted, and a step-through slider.
A box to decode your own DNA sequence.

The planted genes use the same emission probabilities the decoder assumes, so accuracy here shows that the algorithm works, not that it would find real genes.
As in my original, the first position starts from a 50/50 prior over the two states.

Project 2

A dynamic-programming predictor that pairs RNA bases to maximise a base-pair score and prints the structure in dot-bracket notation.

Stack: Python
Dynamic programming
Who and when: Course project
My contribution: I implemented the scoring, the table fill and the traceback.

Working demo

Runs in your browser

Try this: Press 'Find a sequence where the original traceback fails' to see the two traceback versions disagree.

Runs entirely in your browser. The structure is a score-maximising pairing, not a physical energy model.

Loading demo...

Pair scores A-U 2, C-G 3 and G-U 1, with a minimum distance of 4 between paired bases.
For each substring: leave the last base unpaired, pair the two ends, or split the substring at some point k and add the two halves.
A traceback that turns the table into a dot-bracket string such as ((...)).

The table is filled by substring length, so every cell only depends on shorter substrings that are already known.
The value in the top-right cell is the best total pair score for the whole sequence.
The traceback walks back from that cell, deciding at each step which of the three cases produced the value.

A table view that fills in length by length, with a step slider.
An arc diagram of the predicted pairs above the sequence.
A switch between my original traceback and a corrected one, with a check that the structure's score equals the table's score.

Revisiting the code for this demo I found two problems in the original: a duplicated A-U condition meant G-U pairs never scored, and the traceback trusted a pair flag that a later split could overwrite. The demo scores G-U as intended and recomputes the traceback from the table.
The original traceback is still available in the demo so the mismatch can be seen on sequences where it happens.