Bioinformatics Lecture Slides

Introduction to Computers and Biology

• Introduction and Computational Successes
• Quick Biology Introduction (b)

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
• More Dynamic Programming Examples: Subset Sum & Knapsack
• Global Sequence Alignment
• Local Sequence Alignment
• General & Affine Gap Penalties
• Multiple Sequence Alignment
• Linear-space Sequence Alignment
• “4 Russian’s Speedup”
• Python code for local, global alignment & RNA folding
• Local and Global Alignment Web Demo

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
• (Optimal) Binary Search Trees
• Suffix Tries & Trees
• Suffix Arrays (including Skew Algorithm)
• Applications of suffix trees
• Burrows-Wheeler Transform
• Wavelet Trees

Structural Biology

• RNA Folding
• Protein Folding
• Linear Programming
• Side-chain Positioning

Pattern Discovery

• Motif Finding with Gibbs Sampling
• Bacterial Gene Finding
• Hidden Markov Models and Eukaryotic Gene Finding
• Profile Hidden Markov Models

Phylogenetics

• Phylogenetics

Clustering Biological Networks

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

Aligning Biological Networks

• PathBLAST
• Alignment via Color Coding
• IsoRank

Random Models of Network Evolution

• Models of Network Evolution
• Attack vs. Failure Response
• Network Motifs & Symmetry Breaking