This is a tentative outline of lecture topics and assignment dates for the semester. Although I have tried to predict our schedule accurately, the dates on this syllabus are subject to change, depending on how quickly we cover the material. "TBD" material at the end of class will be drawn from current literature.
| Date | Class Topic | Homework Due | Homework Assigned |
|---|---|---|---|
| Wed, Jan 19 | Introduction -- Why Biosequence Analysis? | ||
| Mon, Jan 24 | Introduction to Classical String Matching | ||
| Wed, Jan 26 | Classical String Matching -- Knuth-Morris-Pratt | Homework 0 (optional) | |
| Mon, Jan 31 | Classical String Matching -- Finite Automata | Homework 1 | |
| Wed, Feb 2 | Classical String Matching -- Aho-Corasick | ||
| Mon, Feb 7 | finish up classical string matching | ||
| Wed, Feb 9 | Indexing for Sublinear-Time Matching | ||
| Mon, Feb 14 | Suffix Arrays in Subquadratic Time: Manber-Myers | ||
| Wed, Feb 16 | Efficient Search in Suffix Arrays | ||
| Mon, Feb 21 | Computing Longest Common Prefixes | Homework 1 | Homework 2 |
| Wed, Feb 23 | Suffix Trees and Repeat Finding | ||
| Mon, Feb 28 | Finish Up Suffix Trees and Arrays | ||
| Wed, Mar 2 | Pattern Matching with the Burrows-Wheeler Transform | ||
| Mon, Mar 7 | Space-Efficient Indexing with the BWT | ||
| Wed, Mar 9 | The Bidirectional BWT and Virtual Suffix Trees | Homework 2 | |
| March 13-19 | Spring break; No class | ||
| Mon, Mar 21 | Approximate Matching 101: the Smith-Waterman Algorithm | Homework 3 | |
| Wed, Mar 23 | Variants of Smith-Waterman Algorithm | ||
| Mon, Mar 28 | Finding Optimal Alignments in Linear Space | ||
| Wed, Mar 30 | Filtering Methods for Large-Scale Approximate Matching | ||
| Mon, Apr 4 | Combining Filtering with Smith-Waterman | Homework 3 | |
| Wed, Apr 6 | Approximate Matching in Indexed References: Tree Traversal | Final Project Proposals | |
| Mon, Apr 11 | Speeding Up Approximate Matching in Trees | Homework 4 | |
| Wed, Apr 13 | TBD 1 | ||
| Mon, Apr 18 | TBD 2 | ||
| Wed, Apr 20 | TBD 3 | ||
| Mon, Apr 25 | TBD 4 | ||
| Wed, Apr 27 | TBD 5 | Homework 4 | |
| Wed, May 4 | Final projects due 5 PM |