Introduction to Computational Molecular Biology:
Genome and Protein Sequence Analysis
(Winter Quarter 2013)
Assignment 1, due Sunday Jan. 20
Assignment 2, due Sunday Jan. 27
Assignment 3, due Sunday Feb. 3
Assignment 4, due Sunday Feb. 10
Assignment 5, due Sunday Feb. 17
Assignment 6, due Sunday Feb. 24
Assignment 7, due Sunday Mar. 3
Assignment 8, due Sunday Mar. 10
Assignment 9, due Sunday Mar. 17
SYLLABUS & LECTURE SLIDES:
Nature paper on Avida
Nature paper on human genome sequence
Nature paper on mouse genome sequence
Siepel et al. paper on PhyloHMMs & sequence conservation
Rabiner tutorial on HMMs
HMM scaling tutorial (Tobias Mann)
- Biological Review : Gene and genome structure in prokaryotes and eukaryotes; the genetic code & codon usage; "global" genome organization. Sources and characteristics of sequence data; Genbank and other sequence databases.
- Programming Review (1st discussion section) -- Jarrett's slides
- Lecture 1: Finding exact matches in sequences. Living organisms as imperfect replication machines.
- Lecture 2: Theory of evolution & tree of life; 'artificial life'. Mutations as molecular basis for evolutionary change. CpG mutations/CpG islands. Segmental changes.
- Lecture 3: Mutation fates. Neutral/nearly neutral theories. Mutation & substitution rates. Generalities on algorithms for biological data; directed graphs. Reading: Durbin et al. section 2.1, 2.2, 2.3.
- Lecture 4: Depth structure of directed acyclic graphs (DAGs); trees and linked lists. Dynamic programming on weighted DAGs. Reading: Durbin et al. 2.4, 2.5, 2.6.
- Lecture 5: Algorithmic complexity. Maximal-scoring sequence segments. Reading: Durbin et al. 6.1, 6.2, 6.3; Ewens & Grant 1.1, 1.2, 1.12
- Lecture 6: Edit graphs & sequence alignment. Smith-Waterman algorithm. Needleman-Wunsch algorithm. Local vs. global. Multiple sequence alignment. Reading: Ewens & Grant 3.1, 3.2, 3.4, 3.6, 5.2, 9.1, 9.2
- Lecture 7: Linear space algorithms. General & affine gap penalties. Reading: Ewens & Grant 5.3.1, 5.3.2, 12.1, 12.2, 12.3; Durbin et al. chapter 3
- Lecture 8: Profiles. Probability models on sequences; review of basic probability theory: probability spaces, conditional probabilities, independence. Comparing alternative models. Failure of equal frequency assumption for DNA. Site models. Examples: 3' splice sites, 5' splice sites, protein motifs. Site probability models. Comparing alternative models. Reading: Ewens & Grant 12.2, 12.3, 1.14, Appendix B.10; Durbin et al. chapter 3
- Lecture 9: Weight matrices for site models. Weight matrices for splice sites in C. elegans. Score distributions. Limitations of site models (variable spacing, non-independence).
- Lecture 10: Hidden Markov Models: introduction; formal definition. HMM examples: -- splice sites; 2-state models; 7-state prokaryote genome model. Reading: Siepel et al.
- Lecture 11: Probabilities of sequences; computing HMM probabilities via associated WDAG. HMM Parameter estimation: Viterbi training, Baum-Welch (EM) algorithm; specialized techniques.
- Lecture 12: Detection of evolutionarily conserved regions using Phylo-HMMs.
- Lecture 13: Detection of evolutionarily conserved regions using Phylo-HMMs (cont'd).
- Lecture 14: Detection of evolutionarily conserved regions using Phylo-HMMs (cont'd). Information theory: entropy. Information inequality.
- Lecture 15: Distributions with maximum entropy. Boltzmann distribution. Coding theory/data compression, uniquely decodable codes. Kraft inequality, entropy & expected code length.
- Lecture 16: Information. MDL principle and overfitting. Relative entropy. Relative entropies of site models. Sequence logos.
- Lecture 17: Maximal scoring segments. D-segments, relationship to 2-state HMMs. Random variables.
- Lecture 18: Exact & approximate probability distributions for weight matrix scores. Maximal scoring segments.
- Lecture 19: Karlin-Altschul theory.
OTHER RELEVANT COURSES AT UW:
COMPUTATIONAL BIOLOGY COURSES AT OTHER SITES: