logo

Computational Molecular Biology, aka Algorithms for Computational Biology

Home * Syllabus * Course Information * Lecturers,TAs, office hours * Programming Help

Hidden Markov Model Module Guide

This module is intended to teach essentially everything there is to know about the most basic type of hidden Markov model (HMM).  Specifically, you should be able to:

1.      Determine the strengths and weaknesses of an HMM as a model of a given situation.

2.      For a given situation, sketch the state diagram of an HMM model and describe the characteristics of reasonable parameter values.

3.      Implement the Viterbi algorithm for HMM decoding.

4.      Implement posterior decoding.

5.      Implement the Baum-Welch algorithm for unsupervised parameter estimation.

6.      Read, understand, and correct errors in correctness proofs for the above algorithms.

7.      Explain limitations of HMMs and associated algorithms and reference methods for enhancing them.

The source for the material in this module is largely the first few sections of “A tutorial on Hidden Markov Models…” by Rabiner. HMMs are also covered, using a different notation in Chapter 3 of Biological Sequence Analysis, by Durbin et al. (see Notation guide). Relevant sections of both are worth reading. Durbin & Eddy is a good (and inexpensive) book to have on your shelf.

Day 1: Wednesday, September 16

In class

  • Discussion: HMM programming project, and other applications.

Before the next class

 

  • Read this brief, informal primer, intended for molecular biologists.
  • Now read the formal version in Sections 1.1-1.5 of the course notes (HMM Notes).T
  • This material is loosely based on Sections I and II (pages 257-261) of Rabiner, which you may also want to read.

Day 2: Friday, September 18

In class

  • Discussion: Independence properties of HMMs; mechanics of the Viterbi decoding algorithm.
  • Due: EM programming assignment, Part 2

Before the next class

  • Carefully read Sections 2.1-2.3 of the course notes (HMM Notes).Parts of this material are loosely based on Section III.B of Rabiner (but you might want to read Section III.A first).
  • Do these exercises. You will be expected to do similar exercises at the next class meeting.

Day 3: Monday, September 21

In class

  • In-class exercises similar to previous homework
  • Discussion: Correctness of the Viterbi algorithm.

Before class on Monday, September 28

 

Day 4: Friday, September 25 (NOTE Wed is not an HMM day)

In class

  • Workshop HMM assignment (MB out of town)

Before the next class

·         Carefully read Sections 3 & 4 of the HMM Notes.

Day 5: Monday, September 28

In class

  • Discussion: The Forward algorithm and Posterior Decoding.
  • DUE TODAY: Viterbi programming assignment

Before the next class

·         Do these exercises. You will be expected to do similar exercises at the next class meeting.

·         Carefully read Sections 5 & 6 of the HMM Notes.

Day 6: Wednesday, September 30

In class