(b) indicates slides that contain primarily background information. (a) indicates “advanced” material. All slides (and errors) by Carl Kingsford unless noted. Often the material for a lecture was derived from some source material that is cited in each PDF file.

### Introduction to Computers and Biology

### Exact String Search

- Z-Algorithm
- Knuth-Morris-Pratt and Boyer-Moore (a)
- Seminumerical String Matching
- Multiple pattern search (a)

### Dynamic Programming & Sequence Alignment

- Introduction to Dynamic Programming (b)
- More Dynamic Programming Examples: Subset Sum & Knapsack (b)
- Global Sequence Alignment
- Local Sequence Alignment
- General & Affine Gap Penalties [examples]
- Multiple Sequence Alignment
- Linear-space Sequence Alignment (a)
- “4 Russian’s Speedup” (a)

### Genome Sequencing & Assembly

- DNA (Sanger) Sequencing & Lander-Waterman Statistics
- Introduction to Graphs (b)
- Genome Assembly Paradigms
- Comparing Whole Genomes with MUMmer

### Data Structures for String Queries

- Introduction to Trees (b)
- (Optimal) Binary Search Trees (b)
- Suffix Tries & Trees [paper]
- Suffix Arrays (including Skew Algorithm) [examples]
- Applications of suffix trees
- Burrows-Wheeler Transform [examples, paper]
- Wavelet Trees (a)

### Structural Biology

### Pattern Discovery

- Motif Finding with Gibbs Sampling [paper]
- Bacterial Gene Finding
- Hidden Markov Models and Eukaryotic Gene Finding [examples]
- Profile Hidden Markov Models

### Phylogenetics

### Clustering Biological Networks

- Yeast 2-hybrid
- Other Interaction Experiments
- Function Prediction
- Network Modularity (a)
- Clustering via Minimum Spanning Trees
- Kernighan-Lin Graph Partitioning & Clustering via Distances (a)
- MCL and Other Graph Clustering (MCODE, RNSC) (a)

### Aligning Biological Networks

- PathBLAST (a)
- Alignment via Color Coding (a)
- IsoRank (a)

### Random Models of Network Evolution

- Models of Network Evolution (a)
- Attack vs. Failure Response (a)
- Network Motifs & Symmetry Breaking (a)

## Computer Science Background

All slides by Carl Kingsford unless noted. Often the material for a lecture was derived from some source material that is cited in each PDF file.

### Basic Data Structures

### Other Data Structures

### Interval & Spatial Data Structures

- Quadtrees (PR, MX, Point)
- kd-Trees
- Searching in kd-Trees
- Range Trees
- Interval Trees
- Finding Closest Pair of Points

### Programming Languages

### Network Flow Algorithms

- Network Flows
- Bipartite Matching
- Edge-disjoint paths
- Flows with Demands, etc.
- Shortest paths with negative weights