Math 239 Homepage, Spring 2008.

Discrete Mathematics for the Life Sciences

Instructor: Lior Pachter.

Graduate assistant: Anne Shiu

Phone: (510) 642-2028.
Lectures: Tuesdays and Thursdays, 11-12:30pm, 81 Evans.
Office hours: Tuesdays and Thursdays 12:30pm-2pm in 1081 Evans.
Course Control Number: 54949


Phylogenetics by C. Semple and M. Steel, Oxford University Press.
Algebraic Statistics for Computational Biology by L. Pachter and B. Sturmfels, Cambridge University Press.

Lecture notes

Lecture 1: Introduction to the course
Lecture 2: Log linear models
Lecture 3: Markov chains
Lecture 4: Introduction to Gröbner bases
Lecture 5: Hidden Markov models and the EM algorithm
Lecture 6: Tree models I
Lecture 7: Tree models II
Lecture 8: Phylogenetic oranges
Lecture 9: What is an alignment?
Lecture 10: Statistical models for alignment
Lecture 11: The generalized distributive law for alignment
Lecture 12: Inference functions
Lecture 13: The fundamental theorem of phylogenetics I
Lecture 14: The fundamental theorem of phylogenetics II
Lecture 15: Least squares trees
Lecture 16: The neighbor-joining algorithm
Lecture 17: Toric dynamical systems I
Lecture 18: Toric dynamical systems II
Lecture 19: Cyclic split systems
Lecture 20: The neighbor-net algorithm
Lecture 21: Epistasis I
Lecture 22: Epistasis II
Lecture 23: The fundamental theorem of natural selection
Final project presentations April 29: Robert Bradley, Allen Chen, Meromit Schuster
Final project presentations May 1: Maria Cueto, Shaowei Lin, Kevin McLoughlin
Final project presentations May 5: Sudeep Juvekar, Michaeel Kazi, Cynthia Vinzant
Final project presentations May 8: Cordelia Csar, Caroline Uhler, Wenjing Zheng

Tentative syllabus

Week 1 Introduction to algebraic statistics
Statistical models for discrete data, linear and toric models
Week 2 Introduction to computational algebra
Groebner bases and implicitization, maximum likelihood estimation
Week 3 The EM algorithm and biological applications
Week 4 Foundations of graphical models
Hidden Markov models, the Hammersley-Clifford theorem, inference
Week 5 Tropical arithmetic and dynamic programming
Polytopes, linear programming and optimization
Week 6 Sequence analysis
The Needleman-Wunsch algorithm, parametric alignment, the Elizalde-Woods theorem
Week 7 Trees and metrics
The fundamental theorem of phylogenetic combinatorics, the Gromov product, splits
Week 8 The space of trees
Introduction to tropical geometry and the tropical Grassmanian
Week 9 Reconstructing trees
The UPGMA and neighbor-joining algorithms, the robustness theorems, least squares and the minimum evolution polytope
Week 10 Population genetics I
Fisher's fundamental theorem, hapltoypes and genotypes, the coalescent theorem
Week 11 Population genetics II
Reombination, mutation, selection and fitness, the genotope
Week 12 Graphs, networks and dynamical systems
Polynomial dynamical systems, stability, applications to regulatory networks
Week 13 Special topics
Week 14/15 Final project presentations