MBT/Genetics 540/541

Introduction to Computational Molecular Biology:

Genome and Protein Sequence Analysis

(Winter/Spring Quarter 2002)

• Synopsis: A two-quarter introduction to protein and DNA sequence analysis and molecular evolution, including a brief review of basic molecular biology (structure & evolution of genes, genomes and proteins), 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. These are the central computational methods required to determine the "periodic table of biology", i.e. the list of proteins and their evolutionary relationships, which can be regarded as the first stage in the conversion of molecular biology into a quantitative science. Moreover, the statistical and algorithmic methods used (which include maximum likelihood estimation, hidden Markov models, dynamic programming) have wide applicability in other areas of computational/mathematical biology.
• 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:30-11:50 in J-280 (Health Sciences Complex)
• Instructors:
  • Phil Green (K-343B; phg (at) u.washington.edu)
  • Joe Felsenstein (J-253; joe (at) genetics.washington.edu)
• Office hours: by appointment with the instructor.
• Text:
  • (Required): Statistical Methods in Bioinformatics : An Introduction by Warren J. Ewens, Gregory R. Grant; Springer, 2001. ISBN: 0387952292 . Hardbound, ~$80 (available from UW Bookstore, or www.bn.com, www.amazon.com).
  • (Recommended): 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, ~$35.
• To register for credit, contact Brian Giebel (bgiebel (at) u.washington.edu) to obtain an entry code. Enrollment is limited to 25 students. Auditing is allowed.

  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.

• last year's site

HOMEWORK ASSIGNMENTS (Winter Quarter):

• Assignment 1, due Friday Jan. 18
• Assignment 2, due Sunday Jan. 27
• Assignment 3, due Monday Feb. 4
• Assignment 4, due Monday Feb. 11
• Assignment 5, due Friday Feb. 22
• Assignment 6, due Monday Mar. 4
• Assignment 7, due Friday Mar. 15

HOMEWORK ASSIGNMENTS (Spring Quarter):

• Assignment 1, due Tuesday Apr. 16
• Assignment 2, due Tuesday Apr. 23
• Assignment 3, due Tuesday Apr. 30
• Assignment 4, due Tuesday May 7
• Assignment 5, due Tuesday May 14
• Assignment 6, due Friday June 7

SYLLABUS & LECTURE SLIDES FOR WINTER QUARTER:

Math Notation

Nature paper on human genome sequence

• 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. site with molecular biology graphics used in this lecture.
  • Lecture 3: codon usage; gene and genome structure in prokaryotes and eukaryotes
  • Lecture 4: genome structure in eukaryotes: repeats, "global" genome organization, GC content variation in mammalian genomes. Mutations as molecular basis for evolutionary change.
  • Lecture 5: CpG islands. Large-scale mutational changes. Mutation fates, neutral theory, mutation & substitution rates.
  • Lecture 6: 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 7: generalities on algorithms for biological data; finding exact matches in sequences; directed graphs; depth structure of directed acyclic graphs (DAGs); trees and linked lists; dynamic programming on weighted DAGs
  • Lecture 8: dynamic programming on weighted DAGs (cont'd); maximal-scoring sequence segments; edit graphs & sequence alignment (local & global): Smith-Waterman algorithm
  • Lecture 9: global alignments (Needleman-Wunsch algorithm); local vs global; edge weight issues; linear space algorithms; hidden state DAGs
  • Lecture 10: general & affine gap penalties; extending graphs to have "edge memory"; Smith-Waterman special cases, self-similarity; speedups based on nucleating word matches: BLAST, FASTA, cross_match
  • Lecture 11: Multiple sequence alignment: biological considerations; product DAGs; Carillo-Lipman, Hein, & progressive alignment algorithms as special cases of projection-reduced complexity.
• Probability distributions on sets of sequences
  • Lecture 12: Multiple sequence alignment (continued). Probability models on sequences; review of basic probability theory: probability spaces, conditional probabilities, independence; failure of equal frequency assumption for DNA Reading: Ewens & Grant sections 1.1, 1.2, 1.12
  • Lecture 13: Failure of equal frequency assumption for proteins. 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 Reading: Ewens & Grant 3.1, 3.2, 3.4
  • Lecture 14: 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; random variables; exact probability distribution for weight matrix scores Reading: Ewens & Grant 8.1, 8.3, 5.2, 5.3.1, 5.3.2
  • Lecture 15: Exact probability distribution for weight matrix scores (cont'd); application to 3', 5' splice sites; failure of independence assumption. Information theory: entropy, information inequality Reading: Ewens & Grant 1.3.1, 1.3.2, 1.3.3, 1.4, 1.5, 2.10.1, 1.14
  • Lecture 16: Boltzmann distribution, coding theory/data compression, Kraft inequality, entropy & expected code length, uniquely decodable codes; information; relative entropy
  • Lecture 17: Relative entropies of site models; sequence logos; model parameter estimation & maximum likelihood; consistency of maximum likelihood estimates; Bayesian analysis Reading: Ewens & Grant 3.3, 8.2
  • Lecture 18: Bayes theorem; binomial/beta, multinomial/Dirichlet conjugate distributions & pseudocounts; Scores on probability spaces, realization as scaled LLRs Reading: Ewens & Grant 1.8, 1.9.1, 1.10.1, 1.10.5, 1.10.6, 2.1.1, 2.1.2, 3.6, 3.7
  • Lecture 19: exact score distribution for maximal scoring segments on sequence graphs; failure of independence assumption for residue sequences; arbitrary distributions on sequence spaces via conditional probabilities; stationary order k Markov models; Introduction to Hidden Markov Models Reading: Ewens & Grant 4.4, 4.5, 4.8, 6.5, 11.1
  • Lecture 20: HMMs: formal definition; probabilities of sequences; examples: higher order Markov models, site models, 2-state models, 7-state prokaryote genome model. Computing HMM probabilities via associated WDAG. Parameter estimation: Viterbi training, Baum-Welch (EM) algorithm. Reading: Ewens & Grant 11.2, 11.3

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

• Lecture 1: Parsimony phylogeny methods. Fitch and Sankoff algorithms for counting steps on a given tree. Compatibility method and pairwise compatibility theorem. Reading: Ewens & Grant 385-387, 398-400; Durbin et al. 160-163, 173-176, 188-189
• 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: Ewens & Grant 398-400; Durbin et al. 163-165, 176-179
• Lecture 3: Distance methods. Least squares fitting of trees to matrices of distances. Statistical behavior. Neighbor-joining and UPGMA methods. Reading: Ewens & Grant 387-398; Durbin et al. 165-173, 189-191
• Lecture 4: 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. Reading: Ewens & Grant 365-382; Durbin et al. 193-197
• Lecture 5: 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: Ewens & Grant 400-408; Durbin et al. 197-209
• Lecture 6: 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. Hasegawa 14-species 232-site primate mitochondrial sequences Reading: Ewens & Grant 415-416; Durbin et al. 215-217
• Lecture 7: Bootstraps and jackknifes for resampling among sites to get confidence intervals on the tree. What they do and don't mean. Reading: Ewens & Grant 408-415; Durbin et al. 179-180, 212-215
• Lecture 8: Tree testing. Likelihood ratio tests, Paired sites tests including KHT test, Shimodaira-Hasegawa multiple-tree extension of it. Reading: Ewens & Grant 416-421; Durbin et al.
• Lecture 9: Coalescents: Trees of genes within species and what happens to molecular evolution as one gets down near the species level. Reading: Ewens & Grant ; Durbin et al. 211-212
• Lecture 10: Markov Chain Monte Carlo methods. Using them to compute likelihoods summing over all coalescent genealogies. Griffiths/Tavare' and Kuhner et. al. approaches. Reading: Ewens & Grant 310-314; Durbin et al. 206-207, 211-212
• 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: Ewens & Grant ; Durbin et al. 180-188
• Lecture 12 and Lecture 13: 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. Reading: Ewens & Grant ; Durbin et al.
• Lecture 14: Repeats in human genome: classification, age analysis, distribution with respect to GC content, other features. Reading: Initial sequencing and analysis of the human genome. The Genome International Sequencing Consortium. Nature 409, 860-921 (15 February 2001) : pp. 879-892.
• Lecture 15: Repeats in human genome: distribution with respect to GC content & genes. use in studying GC content variation, male/female differences in mutation rates
• Lecture 16: Segment analysis of human genome: mouse-human syntenic segments, duplicated segments, whole genome duplication. Horizontal transfer from bacteria. Non-randomness of mutations, strand asymmetry. Transcription-associated strand asymmetry in mammalian DNA evolution.
• Lecture 17: Maximal scoring segments in weighted linked lists. Karlin-Altschul theory for high-scoring segments. Reading: Ewens & Grant chapter 7
• Lecture 18: Genome sequencing & assembly.
• Lecture 19: Genome sequencing & assembly (cont'd). Gene identification in eukaryotes.
• Lecture 20: Gene identification in eukaryotes (cont'd).
• Other topics, as time permits:
  • More on probabilities and sequence alignment. Dayhoff model, BLOSUM. maximum probability alignments. statistics of gapped alignments
  • Comparative genomics.
  • 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.
  • Minimum Description Length principle.
  • Protein sequence/structure relationships. Protein evolution. Variable rates. structural constraints.

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)
• Introduction to Computational Molecular Biology (Peter Clote, MIT)