Computational Biology: Genomes, Networks, Evolution

Lecture Slides

Lecture 1
Course Overview and Outline - Intro to Biology - Why Computational Biology - Regulatory Motif discovery

Lecture 2 - Sequence Alignment + Dynamic Programming
Fibonacci - Paths & Alignments - Bounded DP - Linear Space Alignment

Lecture 3 - Sequence Alignment II
Globa/Local/Semi-global alignment + Affine gaps + Alignment statistics

Lecture 4 - Exact string matching
Semi-numerical methods, prelude to hashing

Lecture 5 - Hashing + Blast
Database search - Hashing - Blast - Extensions - Combs - Suffix Trees

Lecture 6 - Modeling Biological Sequences with HMMs
Dishonest Casino, CpG islands, Markov Chains, HMMs, Viterbi

Lecture 7 - HMM decoding evaluation training
Viterbi+Decoding, Forward+Evaluation, Backward+Posterior Decoding, BaumWelch+Training

Lecture 8 - Clustering gene expression data 

Lecture 9 - Clustering and Dimensionality Reduction
Running time analysis, feature selection, SVD, PCA

Lecture 10 - Regulatory Motif Discovery
Combinatorial/probabilistic formulation, weight matrices, gibbs sampling, EM

Lecture 11 - Graph algorithms
Connected components, spectral partitioning

Lecture 12 - Evolutionary trees 

Evolution, trees, distance-based methods, parsimony 

Lecture 13 - Phylogenetics
Jukes-Cantor, Kimura, ultrametric, additive, UPGMA, Neighbor-Joining, Dynamic programming parsimony

Lecture 15 - RNA folding
RNA folding - Nussinov's algorithm - Zucker's algorithm - context-free grammars - parsing

Lecture 16 - Stochastic Context-Free Grammars
CYK algorithm - Inside/Outside - HMM similarity - Posterior decoding

Lecture 17 - Genome Rearrangements
Evolution by rearrangements - Sorting by reversals - greedy algorithms - approximation algorithms - breakpoint graphs

Lecture 18 - Genome Duplication
Orthologs - Paralogs - Phylogenetic Tree Reconciliation - Genome Duplication - Duplicate gene divergence - Accelerated Evolution

Lecture 19: Genome assembly
Sequencing, assembly, whole genome shotgun, hierarchical approach

Lecture 22 - Biological Networks
Guest lecture by Laszlo Barabasi - Scale-free networks - Network growth - Robustness - Modularity - Hierarchical - Flux

Lecture 23 - Advanced Multiple Alignment and Assembly
Traditional assembly - String-graph assembly - Global and glocal alignment - Alignmnet with polymorphism

Lecture 24 - Whole-Genome Analysis
HMMs for Gene Finding - Classification based gene finding - Human Motif Finding - MicroRNA regulation

Recitation Notes

Recitation 1 - Running Times, Molecular Biology and Probability

Recitation 2 - Python and Dynamic Programming and Alignments 

Recitation 3 - Randomization, Modulus, Hashing, Random Projections, BLAST, Suffix Trees 

Recitation 4 - Hidden Markov Models 

Recitation 6 - Motif Finding Using EM and Gibbs Sampling

Recitation 7 - UPGMA, Neighbor Joining, Parsimony 

Recitation 8 - RNA Folding, Context Free Grammars and Related Algorithms

Recitation 9 - Sequencing by Hybridization 

Problem Sets

Problem Set 1     

Problem Set 2     

Problem Set 3    

Problem Set 4    

Problem Set 5