CPSC 445 - Course Calendar


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


last update 09/01/2008 14h,