Algorithms for Genome Analysis
Syllabus & Reading

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.


Lec # Topic Date Reading Handouts & Slides
Genomes, Assembly & Evolution
1. Overview: what is the genome, and where does it come from?
Genome Assembly
Jan 9th EBI's Intro to Biology: Sections 1-3
JGI's Intro to Genomics
Weber & Myers: Human Whole-Genome Shotgun Sequencing
Medvedev et al: Models for Genome Assembly
Lecture slides
2. Basic Evolution & Variation Detection Jan 16th Section 1 of Speed's notes on Evolution and Phylogeny
Chapter 9 of the Haubold book (only available from on-campus).
pyroBayes paper by Marth et al
Alignment & Phylogeny
3.Pairwise Alignment: Longest common subsequence, Substitution matrices, Global v Local Jan 23 Speed: Lecture Notes on Sequence Alignment
Myers & Miller: Alignments in Linear Space
More Lecture Notes on Alignment

Project Description
4. Modern Alignment programs: Gap penalties, Anchored Alignment Jan 30th Reduction from LIS to LCS (Gusfield 12.4-12.5)
Brudno & Dubchak: Comparisons of Long Genomic Sequences (Chapter 14 from Aluru's Handbook)
Knuth-Morris-Pratt String Matching Algorithm
HW1 out due February 13
Project Description out; Proposal due February 27
5. Suffix Arrays, Burrows-Wheeler Transform, FM-index Feb 6th Suffix Arrays
Burrows Wheeler Transfor
BWA Aligner
6. Multiple Alignment & Phylogenetic Tree Reconstruction Feb 13th Thompson et al: CLUSTALW
Loytinoja & Golding: Progressive Alignment
Lecture notes on phylogenetic trees
Genes, Epigenetics & Regulation
7.CpGs & Hidden Markov Models February 27th Rabiner's tutorial on HMMs
Huson's notes on HMMs & CpGs
8. Epigenetic Modification & ChiP-SeqMarch 6th
9. Gene finding March 13th Zhang's Review of Gene-Finding
10. Measuring Gene Expression & Isoforms March 20th
11. Motif finding March 27th Blanchette et al.: Footprinter
Lawrence et al.: Gibbs Sampling
Bailey et al.: EM for Motif Finding (MEME)