Algorithms for Genome Analysis
Syllabus & Reading

This is a more of a "What's Happened" than a "What's Coming Up" syllabus. Lectures are subject to adjustment depending on the pace of the class.

There will not be a required book for this class, most topics will be covered by research papers. This is mainly due to the fact that the field changes rapidly and many books are dated by the time they hit the shelves.

Having said that, for a lot of the topics in this class a copy of Durbin, Eddy, Krogh & Mitchison's book Biological Sequence Analysis is good reading. It is especially good at covering HMM's and other probabilistic approaches. It is "suggested" but not "required".

Two optional "reference" books are Waterman's Introduction to Computational Biology and Gusfield's Algorithms on Strings Trees and Sequences. If you really want a bible you may want to get the newly published Handbook of Computational Molecular Biology.

Note that the links to Amazon above are for convinience and not an endorsement of the seller or an indication that these are the lowest prices on these books.


Lec # Topic Date Reading Handouts & Slides
1 Sequence
1. Overview: what is the genome, and where does it come from? Jan 7 EBI's Intro to Biology: Sections 1-3
JGI's Intro to Genomics
Lecture slides
2. Genome assembly & String Graphs Jan 14 Algorithmic:
Medvedev et al: Models for Genome Assembly
Batzoglou, et al: Arachne
Historic:
Weber & Myers: Human Whole-Genome Shotgun Sequencing
Green: Against a Whole-Genome Shotgun
2 Sequences
3.Hidden Markov Models (CpGs) and Evolution: Jukes Cantor and IndelsJan 21 Rabiner's tutorial on HMMs
Huson's notes on HMMs & CpGs
Section 1 of Speed's notes on Evolution and Phylogeny
4.Pairwise Alignment: Longest common subsequence, Substitution matrices, Global v LocalJan 28 Speed: Lecture Notes on Sequence Alignment
Myers & Miller: Alignments in Linear Space
More Lecture Notes on Alignment
HW1 Due Feb 11
Project Description
5. Modern Alignment programs: Gap penalties, Alignment relation to HMMs, Anchored Alignment Feb 4 Chapter 4 of Durbin's book (distributed in class)
Reduction from LIS to LCS (Gusfield 12.4-12.5)
Brudno & Dubchak: Comparisons of Long Genomic Sequences (Chapter 14 from Aluru's Handbook)
3 (and more) Sequences
6. Multiple Alignment Feb 11 Thompson et al: CLUSTALW
Loytinoja & Golding: Progressive Alignment
Do et al: Probabilistic Consistency Multiple Alignment
Reading Break &mdash no class! Feb 18
7. Rearrangements & Hannenhali-Pevzner AlgorithmFeb 25 Bergeron's presentation of Hannenhali-Pevzner
Genes & Regulation
8. Biology of genes & Motifs; Microarrays Mar 11 Microarray Overview
Eisen et al: Microarray Clustering
Lecture slides
HW 2 out, Due March 18
9. Phylogenetic Tree ReconstructionMar 4 Lecture notes on phylogenetic trees
10. Gene finding Mar 18 Zhang's Review of Gene-Finding
Brent & Guigo's Review of Comparative Gene-Finding
11. Motif finding Mar 25 Blanchette et al.: Footprinter
Lawrence et al.: Gibbs Sampling
HW 3 out, Due April 15
12.Protein-Protein Interaction (PPI) networks Apr 1 Bork et al: Protein Interaction Networks
Przulj et al: Modeling Interactome: Scale Free or Geometric?
Nabieva et al: Prediction of Protein Function
Kelley et al: PathBLAST
Final Project
13. Presentations Apr 8