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. Readings for future weeks are "approximations"; required reading will be posted by Wednesday before 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.

Lec # Topic Date Reading Handouts & Slides
Genomes, Assembly & Evolution
1. Overview: what is the genome, and where does it come from? Sept 13 EBI's Intro to Biology: Sections 1-3
JGI's Intro to Genomics
Weber & Myers: Human Whole-Genome Shotgun Sequencing
Green: Against a Whole-Genome Shotgun
Lecture slides
2. Genome assembly & String Graphs Sept 20 Medvedev et al: Models for Genome Assembly
Batzoglou, et al: Arachne
Butler, et al: AllPaths
3. Basic Evolution & Variation DetectionSept 27 Section 1 of Speed's notes on Evolution and Phylogeny
Chapter 9 of the Haubold book (only available from on-campus).
Alignment & Phylogeny
4.Pairwise Alignment: Longest common subsequence, Substitution matrices, Global v LocalOct 4 Speed: Lecture Notes on Sequence Alignment
Myers & Miller: Alignments in Linear Space
More Lecture Notes on Alignment
HW1 out
Project Description
5. Modern Alignment programs: Gap penalties, Anchored Alignment Oct 18 Reduction from LIS to LCS (Gusfield 12.4-12.5)
Brudno & Dubchak: Comparisons of Long Genomic Sequences (Chapter 14 from Aluru's Handbook)
HW1 due on Thurs Oct 21 @10am
6. Multiple Alignment & Phylogenetic Tree Reconstruction Oct 25 Thompson et al: CLUSTALW
Loytinoja & Golding: Progressive Alignment
Lecture notes on phylogenetic trees
7. Rearrangements & Hannenhali-Pevzner TheoryNov 1 Bergeron's presentation of Hannenhali-Pevzner Project proposal due!
HW2 out
Genes & Regulation
8. Biology of genes & Motifs; Microarrays Nov 15 Microarray Overview
Eisen et al: Microarray Clustering
Lecture slides
9.Hidden Markov Models & Comparative GenomicsNov 22 Rabiner's tutorial on HMMs
Huson's notes on HMMs & CpGs
HW2 Due!
10. Gene finding Nov 29 Zhang's Review of Gene-Finding
Brent & Guigo's Review of Comparative Gene-Finding
HW3 out; due Dec 9
Genome for HW3
11. Motif finding Dec 6 Blanchette et al.: Footprinter
Lawrence et al.: Gibbs Sampling
Bailey et al.: EM for Motif Finding (MEME)