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. In particular, lectures marked "(optional)" will be dropped if the course is going slower than I am currently expecting.

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 Lecture Notes Comments
1 Sequence
1. Overview & What is the genome Sept 12 EBI's Intro to Biology: Sections 1-3
JGI's Intro to Genomics
Lecture Slides
No lecture Sept 14
2-3. Genome assembly & String Graphs Sept 19, 21 Algorithmic:
Batzoglou et al: Arachne
Pevzner et al: Euler
Myers: String graphs
Weber & Myers: Human Whole-Genome Shotgun Sequencing
Green: Against a Whole-Genome Shotgun
Green: Whole-Genome Shotgun Disassembly
4. Hidden Markov Models (CpGs)Sept 26 Rabiner's tutorial on HMMs
Huson's notes on HMMs & CpGs
2 Sequences
5.Evolution: Jukes Cantor and IndelsSept 28 Section 1 of Speed's notes on Evolution and Phylogeny
6.Longest common subsequence, Substitution matricesOct 3
7. Alignment (Needleman-Wunsch, Smith-Waterman)Oct 5 Speed: Lecture Notes on Sequence Alignment
Myers & Miller: Alignments in Linear Space
8. Gap penalties, Alignment relation to HMMs Oct 10 Chapter 4 of Durbin's book (distributed in class) HW1 Out
Project handout
9. Modern Alignment ProgramsOct 12 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
10-11. Multiple AlignmentOct 17, 19 Thompson et al: CLUSTALW
Loytinoja & Golding: Progressive Alignment
Do et al: Probabilistic Consistency Multiple Alignment
12-13. Rearrangements & Hannenhali-Pevzner AlgorithmOct 24, 26 Bergeron's presentation of Hannenhali-Pevzner
14. Review of HW1 Nov 2
15. Phylogenetic Tree ReconstructionNov 7 Lecture notes on phylogenetic treesHW2 out
Genes & Regulation
16. Biology of genes & Motifs Nov 9 Lecture slides
17. Microarrays & Gene ExpressionNov 14 Lecture Slides
Microarray Overview
Eisen et al: Microarray Clustering
18-19 Gene finding Nov 16 Zhang's Review of Gene-Finding
Brent & Guigo's Review of Comparative Gene-Finding
20-21. Motif finding Nov 21,23 Lawrence et al: Gibbs Sampling
Blanchette et al.: Footprinter
22-23.Protein-Protein Interaction (PPI) networks Nov 28, 30 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
24-25. Presentations Dec 5,7