Rosalind — Bioinformatics Textbook Track — Hmm

BA10A — Compute the Probability of a Hidden Path

One product of fifty transitions, which lands at 1e-19 — the concrete reason the decoding problems that follow are done in log space rather than directly.

BA10B — Compute the Probability of an Outcome Given a Hidden Path

solved Problem statement

Conditioning on the path makes the positions independent, so the transitions never enter into it. Checked against the same product taken by hand.

BA10C — Implement the Viterbi Algorithm

solved Problem statement

The problem this pack was built to reach: HMM decoding is what gene finders, profile search and segmentation all run on, and nothing in the tree could do it before.

BA10D — Compute the Probability of a String Emitted by an HMM

solved Problem statement

The forward algorithm. Its assertion enumerates all 1024 paths of the sample and sums them, so the collapse is checked against the thing it replaces rather than only against a published number.

BA10J — Solve the Soft Decoding Problem

solved Problem statement

Forward-backward, which answers a different question from Viterbi: the most likely state at each position need not lie on any single path the model can produce.

BA10H — Estimate the Parameters of an HMM

solved Problem statement

With the path given there is nothing to infer — the best estimate is the fraction of the time each move was made. A state the path never visits keeps a uniform row, which is the only choice that leaves it a distribution.

BA10I — Implement Viterbi Learning

solved Problem statement

Decode, re-estimate as if that path were the truth, repeat. Climbs to a local optimum, so where it starts is part of the problem rather than an implementation detail.

BA10K — Implement Baum-Welch Learning

solved Problem statement

Expectation-maximisation: counts the expected number of times each transition was taken over every path at once, instead of committing to the best one. Its assertion checks the likelihood rises round by round, not only end to end.

BA10E — Construct a Profile HMM

solved Problem statement

A family of sequences becomes something a new sequence can be scored against — what Pfam and HMMER search with. Conserved columns become match states; gappy ones become insertions, which keeps the model's length at the family's length rather than the alignment's.

BA10F — Construct a Profile HMM with Pseudocounts

solved Problem statement

Without a pseudocount, anything six sequences never happened to do is scored as impossible. It is added after the counts become probabilities, not before — added to raw counts its influence would depend on how many sequences the alignment contains.

BA10G — Perform a Multiple Sequence Alignment with a Profile HMM

solved Problem statement

Viterbi cannot do this: deletion states are silent, so nine states emit seven symbols. The silent states have to be settled in layer order at each position before the emitting ones look back at them.