The following is a preliminary schedule and is subject to minor modifications
Class 1: 08/01/2008, tue |
* Course overview * human genome project Course information |
Class 2: 08/01/2008, thr |
* Entrance exam * naive exact string matching Introduction to string matching (including KMP algorithm) |
Class 3: 15/01/2008, tue |
* exact string matching CBC News: Chromosome abnormality linked to autism, study finds * Animation of the KMP-Algorithm: http://www.ics.uci.edu/~goodrich/dsa/11strings/demos/pattern/ |
Class 4: 17/01/2008, thr |
* finished exact string matching (KMP) * the sequence similarity problem * quiz 1 (see news archive) * text, sections 2.1 and 2.3 up to local alignment (p. 22) |
Class 5: 22/01/2008, tue |
* sequence similarity: dynamic programming * global pairwise alignment (needleman-wunsch algorithm) * local pairwise alignment (smith-waterman algorithm) * Sequence alignment algorithms demo: http://www.iro.umontreal.ca/~casagran/baba.html * text, section 2.2-2.3 |
Class 6: 24/01/2008, thr |
* sequence similarity: affine gap scores * overview of other sequence alignment problems * text, section 2.4 (up to page 31) |
Class 7: 29/01/2008, tue |
* Guest lecture: Anne Condon * sequence similarity: probability background * text, sections 2.2, 2.7, 2.8 * Cool genome graphic in New York Times by Martin Krzywinski |
Class 8: 31/01/2008, thr |
* Guest lecture: Andrew Carbonetto * sequence similarity: more on scoring functions * sequence similarity: BLAST * text, sections 2.5 * Homework 1 release (01/02/2008) |
Class 9: 05/02/2008, tue |
* sequence similarity: BLAST - recap and more on parameters * sequence similarity: multiple sequence alignment (up to complexity of multidimensional dynamic programming * text, section 6.1-6.3 |
Class 10: 07/02/2008, thr |
* sequence similarity: multiple sequence alignment (carillo-lipman; progressive alignment: feng-doolittle; profile alignment) * text, section 6.4 |
Class 11: 12/02/2008, tue |
* sequence similarity: multiple sequence alignment (profile-based progressive alignment, ClustalW, iterative refinement methods, Barton-Sternberg algorithm) * Self-Assessment on Multiple Alignment (by Georg Fuellen, University of Bielefeld, Germany): http://www.techfak.uni-bielefeld.de/bcd/Curric/SelfA/mulali1.html" |
Class 12: 14/01/2008, thr |
* brief review of MSA * started phylogenetic tree inference (motivation, problem statement, exhaustive enumeration, brief intro to distance-based methods, UPGMA) * text, section 7.1 - 7.3 |
18/02/2008 | Reading Week |
Class 13: 26/02/2008, tue |
* distance metrics for phylogenetic tree reconstruction * UPGMA clustering algorithm * molecular clock property and ultrametric condition * text 8.2, in particular the Jukes-Cantor model. * text 7.3 * Java applet for phylogenetic tree inference (UPGMA) by Peter Sestoft (IT University of Copenhagen, Denmark) available here |
Class 14: 28/02/2008, thr |
* UPGMA: time complexity * assessing quality of phylogenetic trees obtained from distance-based methods * NP-hardness of general phylogenetic tree reconstruction problem * parsimony: motivation, background, small and large parsimony problem, fitch's algorithm |
Class 15: 04/03/2008, tue |
* parsimony: fitch's algorithm (for the small parsimony problem) back tracing, complexity and limitations * parsimony: solving the large parsimony problem using greedy constructive search, branch and bound |
Class 16: 06/03/2008, thr |
* large parsimony problem: stochastic local search (with various
types of swaps) * briefly mentioned other approaches to phylogenetic tree reconstruction (simultaneous alignment and tree construction, max likelihood) |
Class 17: 11/03/2008, tue |
* introduction to motif finding + discovery * motivating examples, problem statement(s) * maximum likelihood approach, log odds score * weight matrices Notes from Larry Ruzzo's course (covers weight matrices): lect08.pdf lec05.pdf (note: we covered only part of the materials from these slides in CPSC 445 and students are not expected to know what we have not covered in class) |
Class 18: 13/03/2008, thr |
* motif finding (brief summary, wrap-up) * relative entropy * motif discovery based on relative entropy |
Class 19: 18/03/2008, tue |
* discovery based on relative entropy (brief recap) * greedy algorithm by Hertz and Stormo * Gibbs sampling algorithm by Lawrence et al. * motif discovery based on consensus sequences |
Class 20: 20/03/2008, thr |
* RNA structure prediction: introduction * RNA secondary structure * text, section 10.1, to page 165 |
Class 21: 25/03/2008, tue |
* RNA structure prediction: free energy minimization * text, section 10.2, to page 275 (ignore parts on SCFG's) |
Class 22: 27/03/2008, thr |
* protein structure prediction (guest lecture by Chris Thachuk) * Slides here |
Class 23: 01/04/2008, tue |
* project presentations |
Class 24: 03/04/2008, tue |
* project presentations * project report due |
Class 25: 08/04/2008, tue |
* project presentations |
Class 26: 10/04/2008, tue |
* open |
* Final Exam: 21/04/2008, mon - 22/04/2008, tue |
* student exam guidelines * student exam FAQs |