Computational Genomics: Sequence Modeling (600.403, Fall 2004)

Course description:

This short course will cover probabilistic methods for modeling biological sequences (e.g., DNA and protein sequences). Topics include inferring relationships between and among sequences and evolutionary trees over sequences. Pre-requisites: knowledge of algorithms, probability and programming.

Dates/times:

This is a short course meeting from 1-2 pm on Mondays, Tuesdays, and Wednesdays from October 4 through November 1. Tentatively the location is Shaffer 2.

Instructors:

Noah Smith and Roy Tromble; please contact us by email if you have any questions about the course.

Syllabus (in pdf form)

Textbook:

R. Durbin, S. Eddy, A. Krogh, and G. Mitchison, Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.

Errata for the Durbin et al. book.

This book may also be useful but is not required:

D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.

Additional notes on HMMs, following the lectures on 10/13 and 10/18 are available in PDF.

Topics (subject to change):

Course introduction and probabilty theory review
Given two sequences, are they related? Here we cover dynamic programming algorithms for aligning two sequences, scoring them, and measuring statistical significance. The usefulness of Hidden Markov models (HMMs) will be highlighted, and significant time will be spent on the machinery of HMMs.
Is a given sequence related to a given sequence family? We continue the use of HMMs, here discussing profile HMMs, which are used to determine the relationship between one sequence and a known family of sequences. This leads naturally to the problem of constructing alignments between more than two sequences.
What evolutionary relationships exist among sequences? We describe algorithms for inferring evolutionary trees over sequences, and the application of probabilistic modeling to this problem.

Lecture Slides

Assignments

Assignment 1 (pdf)
This is the sequence from the assignment, in case you want it in electronic form:
V,V,V,V,T,W,Z,V,Y,V,X,V,U,V,W,U,U,Y,U,U,V,V,T,V,Z,Y,Z,X,Y,T,U,U,Y,Y,Y,W,U,W,Y,T,U,X,X,Z,W,X,T,W,T,U,Z,W,Z,T,V,U,Y,Z,W,X,W,Z,T,V,V,V,V,V,X,Y,W,T,T,X,V,V,V,V,V,V,V,T,V,V,Z,U,T,V,V,V,V,V,T,W,Y,Y,T,V,V,V
Assignment 2 (pdf)
Assignment 3 (pdf)
The executable for problem 1 is here:
Linux
SunOS
Cygwin (cygwin1.dll needs to be in the same directory if you are not running Cygwin already.)
Contact us if you have problems running it.
Assignment 4 (pdf)
You will also need either hw4.linux.tar.gz or hw4.sunos.tar.gz and the data in hw4.data.tar.gz.

Class project (pdf)

You will need dataset A. You will also need dataset B; to get that, come to class on November 1 with your partner (or wait until after that class and email us begging forgiveness!).

Updated pbw and pvit (not completely tested, but appear to work). These might run faster than the old versions. tools.v2.linux.tar.gz tools.v2.sun.tar.gz

Noah A. Smith and Roy Tromble