| Date | Topics | Slides | Resources |
|---|
| 9/ 1 | Molecular biology primer: Structure of DNA, Proteins | Administrivia.ppt, Introduction.ppt, Lecture1.ppt | |
| 9/ 6 | Molecular biology primer (cont.): Central dogma of molecular biology, DNA mutation and selection | Lecture2.ppt | |
| 9/ 8 | Molecular biology primer (cont.): Biotechnology | Lecture3.ppt | |
| 9/13 | Exact String Matching: Preliminaries, a naive algorithm and fundamental pattern preprocessing | Lecture4.ppt | Gusfield, Chapter 1 |
| 9/15 | Exact String Matching: Knuth-Morris-Pratt: shift rule, running time, and Z based shift computation. | Lecture5.ppt | Gusfield, Chapter 2 |
| 9/20 | Exact String Matching: Knuth-Morris-Pratt (cont.): failure functions, algorithm pseudo code, real-time failure functions, deterministic automaton, and original K-M-P pattern preprocessing. Homework 1 distributed. | Lecture6.ppt, Homework1.pdf | Gusfield, Chapters 2 & 3 |
| 9/22 | Exact String Matching: Boyer-Moore: shift rules, Z based shift computation. | Lecture7.ppt | Gusfield, Chapter 2 |
| 9/27 | Exact Set Matching: Aho-Corasick: keyword trees, failure links, substring patterns. Homework 1 collected. | Lecture8.ppt | Gusfield, Chapter 3 |
| 9/29 | Exact Set Matching: Aho-Corasick (cont.): empirical performance, applications. | Lecture9.ppt | Gusfield, Chapter 3 |
| 10/ 4 | Exact String Matching: Hashing, Karp-Rabin Fingerprinting | Lecture10.ppt | Gusfield, Chapter 4 |
| 10/ 6 | Suffix Trees: Introduction, Ukkonen's linear time construction. | Lecture11.ppt | Gusfield, Chapter 5 & 6 |
| 10/11 | Suffix Trees: Ukkonen's construction (cont.), Generalized suffix trees, applications | Lecture12.ppt, Homework2.pdf | Gusfield, Chapter 6 & 7 |
| 10/13 | Suffix Arrays | Lecture13.ppt | Gusfield, Chapter 7 |
| 10/18 | Sequence Alignment: Global alignment, dynammic programming | Lecture14.ppt | Gusfield, Chapter 11 |
| 10/20 | Sequence Alignment: Local aligment, non-linear gap models, linear-space alignments | Lecture15.ppt | Gusfield, Chapter 11 & 12 |
| 10/25 | Sequence alignment: Speedups for bounded differences: banding, exclusion methods, chaining | Lecture16.ppt | Gusfield, Chapter 12 & 13 |
| 10/27 | Sequence Similarity Models: Log-odds scores and scoring matrices | Lecture17.ppt | Durbin et al., Chapter 2 |
| 11/ 1 | Sequence Similarity Models: Statistical significance, e-values | Lecture18.ppt | Durbin et al., Chapter 2; Mount, Chapter 3 |
| 11/ 3 | Hidden Markov Models: Introduction and Gene Finding | Lecture19.ppt | Durbin et al., Chapter 3 |
| 11/ 8 | Midterm exam. | | |
| 11/10 | Hidden Markov Models: Basic Algorithms: Viterbi, Forward, Backward dynamic programs | Lecture20.ppt | Durbin et al., Chapter 3; Rabiner, '89 |
| 11/15 | Hidden Markov Models: Parameter estimation, model structure, semi-HMMs | Lecture21.ppt | Durbin et al., Chapter 3; Ewens and Grant, Chapter 12; Rabiner, '89 |
| 11/17 | Hidden Markov Models: Application to gene-finding and protein families | Lecture22.ppt | Durbin et al., Chapter 5; Ewens and Grant, Chapter 12; Henderson et al., '97, Burge and Karlin, '97 |
| 11/22 | de Bruijn Graphs and Optimal k-mer Superstrings | Lecture23.ppt, Homework3.pdf | Edwards and Lippert, '04 |
| 11/24 | Thanksgiving | | |
| 11/29 | Population Genetics Introduction, Clark's Rule | Lecture24.ppt | Halldorsson et al., '03; Halldorsson et al., '04 |
| 12/ 1 | Haplotype Phasing: EM algorithm, Haplotyping by perfect phylogeny | Lecture25.ppt | Halldorsson et al., '04; Excoffier and Slatkin, '95; Bafna et al., '03 |
| 12/ 6 | Haplotype Phasing and Tagging SNP Selection: Haplotyping by perfect phylogeny (cont.) and optimal block-free tagging SNP selection | Lecture26.ppt | Bafna et al., '03; Bafna et al., '03 |
| 12/ 8 | Multiplex genomic assay design: Universal DNA tag systems | Lecture27.ppt | Ben-Dor et al., '00; Ben-Dor et al., '04 |
