MBT/Genetics 540/541

Introduction to Computational Molecular Biology:

Genome and Protein Sequence Analysis

(Winter/Spring Quarter 2001)

• Synopsis: A two-quarter introduction to probabilistic models of sequences and of sequence evolution, computational gene identification, pairwise sequence comparison and alignment (algorithms and statistical issues), multiple sequence alignment and evolutionary tree construction, comparative genomics, and protein sequence/structure relationships.
• Prerequisites: Ability to write computer programs for data analysis is essential (homework assignments will require this.) Some prior exposure to probability and statistics, and molecular biology is highly desirable but not essential.
• Lectures: TuTh 10:00-11:20 in J-280 (Health Sciences Complex)
• Instructors:
  • Phil Green (K-343B / Fluke Hall; phg (at) u.washington.edu)
  • Joe Felsenstein (J-253; joe (at) genetics.washington.edu)
• Text:
  • (Required (Winter)): Computational Molecular Biology : An Introduction (Wiley Series in Mathematical and Computational Biology) by Peter Clote, Rolf Backofen; John Wiley & Sons, Oct 2000. ISBN: 0471872520. Paperback $55.00 (available from UW Bookstore, or www.bn.com, www.amazon.com) -- hardbound version is $120.00.
  • (Required (Spring)): Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids by Richard Durbin, S. Eddy, A. Krogh, G. Mitchison; Cambridge University Press, 1998. ISBN: 0521629713. Paperback $28.95 (bn.com), $34.95 (amazon.com).
• To register for credit, use SLN #5009, Entry Code 95004 (Winter Quarter), SLN #8493 (Spring Quarter). Auditing is allowed. Contact Val Pruitt (vpruitt (at) mbt.washington.edu) in the MBT department if you encounter problems attempting to register.

  Since important announcements (e.g. schedule changes) may be made by email in advance of lectures, all attendees (whether or not registered for the course) should send their email addresses to Phil Green at the above address.

  MBT599 Message Board (run by Jon Schaefer).

  Reformatted slides (run by Jochen Jaeger).

HOMEWORK ASSIGNMENTS (Winter Quarter):

• Assignment 1, due Friday Jan. 12
• Assignment 2, due Friday Jan. 19
• Assignment 3, due Friday Jan. 26
• Assignment 4, due Friday Feb. 2
• Assignment 5, due Friday Feb. 9
• Assignment 6, due Friday Feb. 16
• Assignment 7, due Friday Feb. 23
• Assignment 8, due Friday Mar. 9

HOMEWORK ASSIGNMENTS (Spring Quarter):

• Assignment 1, due Wednesday Apr. 4
• Assignment 2, due Friday Apr. 13
• Assignment 3, due Friday Apr. 20
• Assignment 4, due Friday May 4
• Assignment 5, due Friday May 11
• Assignment 6, due Wednesday May 23

SYLLABUS (Approximate!) & LECTURE SLIDES FOR WINTER QUARTER:

Math Notation

• Biology review
  • Lecture 1: living organisms as imperfect replication machines; theory of evolution & tree of life; molecular structure; entropy and 2d law of thermodynamics, implications for living organisms
  • Lecture 2: DNA, RNA & protein structure; gene expression & "Central Dogma"; the genetic code
  • Lecture 3: gene and genome structure in prokaryotes and eukaryotes; mutations as molecular basis for evolutionary change
  • Lecture 4: overview of goals & experimental approaches of molecular biology; role of sequence analysis; sources and characteristics of sequence data; Genbank and other sequence databases
• Basic algorithms
  • Lecture 5: generalities on algorithms for biological data; finding exact matches in sequences; directed graphs
  • Lecture 6: depth structure of directed acyclic graphs (DAGs); trees and linked lists; dynamic programming on weighted DAGs; maximal-scoring sequence segments
  • Lecture 7: edit graphs & sequence alignment (local & global): Smith-Waterman, Needleman-Wunsch algorithms; linear space algorithms
  • Lecture 8: global alignments; hidden state DAGs; general & affine gap penalties; Smith-Waterman special cases, self-similarity; speedups based on nucleating word matches: BLAST, FASTA, cross_match; multiple sequence alignment
• Probability distributions on sets of sequences
  • Lecture 9: Probability models on sequences; review of basic probability theory: probability spaces, conditional probabilities, independence; failure of equal frequency assumption for DNA and proteins
  • Lecture 10: Site models; examples: 5' and 3' splice sites, protein motifs; limitations of site models (variable spacing, non-independence) -- splice site illustrations; site probability models; comparing alternative models, hypothesis tests, likelihood ratio tests
  • Lecture 11: Neyman-Pearson Lemma, approximation to significance level for likelihood ratio test; weight matrices for site models; weight matrices for splice sites in C. elegans, score distributions
  • Lecture 12: random variables; exact probability distribution for weight matrix scores; application to 3', 5' splice sites; failure of independence assumption
  • Lecture 13: Information theory: entropy, information inequality, Boltzmann distribution, coding theory/data compression, Kraft inequality, entropy & expected code length
  • Lecture 14: uniquely decodable codes; information; relative entropy; relative entropies of site models; sequence logos; model parameter estimation & maximum likelihood
  • Lecture 15: consistency of maximum likelihood estimates; Bayesian analysis & Bayes theorem; binomial/beta, multinomial/Dirichlet conjugate distributions & pseudocounts
  • Lecture 16: Scores on probability spaces, realization as scaled LLRs; exact and approximate score distributions on weight matrices; exact score distribution for maximal scoring segments on sequence graphs
  • Lecture 17: Karlin-Altschul theory for high-scoring segments
  • Lecture 18: Karlin-Altschul theory for gap-free alignments, extensions to gapped alignments; global vs. local behavior; trimming reads by highest weight paths; failure of independence assumption for residue sequences; arbitrary distributions on sequence spaces via conditional probabilities; joint and conditional entropy, chain rule for entropy & relative entropy; mutual information; stationary order k Markov models on genome sequences; intro to Minimum Description Length principle
  • Lecture 19: Models of DNA change. Markov chain models for evolutionary change of DNA sequences along lineages of a phylogeny. Jukes-Cantor, Kimura K2P, F84, HKY, Tamura-Nei, General Time-Reversible, General 12-parameter models.
  • Lecture 20: Modelling variation of rates of evolution from site to site. Gamma distribution of rates, Hidden Markov Model for rates and Forward-Backward algorithm to evaluate likelihood for it.

SYLLABUS (Approximate!) & LECTURE SLIDES FOR SPRING QUARTER:

14-species, 232-nucleotide mtDNA noncoding site data set

Nature paper on human genome sequence

• Lecture 1: Parsimony phylogeny methods. Fitch and Sankoff algorithms for counting steps on a given tree. Compatibility method and pairwise compatibility theorem. Reading: Durbin et al. 7.1, 7.4(173-176)
• Lecture 2: Searching tree space. Counting trees. Heuristic rearrangement, sequential addition, star decomposition, disk-covering, and quartet puzzling methods. Branch and bound for finding all most parsimonious trees. Reading: Durbin et al. 7.2, 7.4 (176-179)
• Lecture 3: Distance methods. Least squares fitting of trees to matrices of distances. Statistical behavior. Neighbor-joining and UPGMA methods. Reading: Durbin et al. 7.3, 7.8
• Lecture 4: Likelihood on phylogenies. Likelihoods for DNA models, algorithm for computing likelihoods on a tree. HMM rate variation again. Tree space with branch lengths. Likelihood ratio tests of molecular clocks, models of change. Reading: Durbin et al. 13, 11.3, 8.1-8.3, 11.1(304), 8.5(215-217), 3.2, 308-309
• Lecture 5: Bootstraps and jackknifes for resampling among sites to get confidence intervals on the tree. What they do and don't mean. Reading: Durbin et al. 7.5
• Lecture 6: Tree testing. Likelihood ratio tests, Paired sites tests including KHT test, Shimodaira-Hasegawa multiple-tree extension of it.
• Lecture 7: Introduction to Hidden Markov Models. Reading: Durbin et al. pp. 46-71 and 323-325
• Lecture 8: Coalescents: Trees of genes within species and what happens to molecular evolution as one gets down near the species level.
• Lecture 9: Markov Chain Monte Carlo methods. Using them to compute likelihoods summing over all coalescent genealogies. Griffiths/Tavare' and Kuhner et. al. approaches. Reading: Durbin et al. 8.4(211)
• Lecture 10: More on HMMs; multiple sequence alignment. Reading: Durbin et al. 100-113; and chapter 6
• Lecture 11: Tree alignment. Why you ought not do multiple sequence alignment without thinking about phylogenies at the same time. Sankoff's strategy, Clustal and progressive alignment as approximations. Probabilistic models of insertion and deletion and prospects for ever getting anywhere using them. Reading: Durbin et al. 7.6
• Lecture 12: More on multiple alignment: product graphs; Carillo-Lipman, Hein, & progressive alignment algorithms as special cases of projection-reduced complexity.
• Lecture 13: Extending graphs to have "edge memory"; affine gap penalties. Introduction to genome sequencing.
• Lecture 14: Genome sequencing (continued).
• Lecture 15: Analysis of human genome sequence: GC content. Reading: Initial sequencing and analysis of the human genome. The Genome International Sequencing Consortium. Nature 409, 860-921 (15 February 2001)
• Lecture 16: Analysis of human genome sequence (cont'd): segmental changes, horizontal transfer from bacteria, CpG islands, repeats. Rearrangements that occur in genomes. Inversions, transpositions, translocations, duplications, deletions.
• Lecture 17: Genomic models: Gene families. Reconciled trees. Computing minimum numbers of inversions between genomes. Signed and unsigned maps. Breakpoint approximations. Prospects for taking DNA change into account too.
• Lecture 18: Analysis of human genome sequence (cont'd): Age analysis of repeats in human genome. Distribution with respect to GC content, other features.
• Lecture 19: Male/female differences in mutation rates. Gene prediction in C. elegans & other organisms.
• Other topics, as time permits:
  • small sample correction, codon usage
  • probabilistic suffix trees.
  • Gene and feature prediction using extended Markov models and dynamic programming.
  • applications of HMMs to gene prediction and protein structure modelling.
  • Protein sequence/structure relationships. Protein evolution. Variable rates. structural constraints.
  • More on probabilities and sequence alignment. Dayhoff model, BLOSUM. maximum probability alignments. statistics of gapped alignments
  • Comparative genomics.

OTHER RELEVANT COURSES AT UW:

• CSE 590cb (Reading and Research in Computational Biology)
• CSE 527 (Computational Biology)
• Pathobiology 536 (Bioinformatics and Gene Sequence Analysis)
• Genetics 562 (Spring 2001): Population Genetics
• Genetics 570 (Spring 2000): Phylogenetic Inference
• Genetics 590 (Autumn 2000): Evolution and Population Genetics Seminar

COMPUTATIONAL BIOLOGY COURSES AT OTHER SITES:

• Computational Molecular Biology (Sean Eddy, Washington University)
• Algorithms for Molecular Biology (Ron Shamir, Tel Aviv University)
• Computational Molecular Biology (Doug Brutlag & Lee Kozar, Stanford)
• Representations and Algorithms for Computational Molecular Biology (Russ Altman, Stanford)
• Computational Molecular Biology (Peter Clote, MIT)