Discrete graphical models are instances of statistical models that can be characterized by polynomials in the joint probabilities. The emerging and active field of algebraic statistics offers algorithms for this polynomial representation, and is a fertile area for the application of ideas from commutative algebra and algebraic geometry.

We will focus on the rich interaction between the theory of algebraic statistics, and the motivating application of computational biology. Several recent papers have demonstrated that algebraic statistics can be applied to developing practical algorithms for biological applications, and conversely that computational biology questions motivate interesting research directions in the theory of algebraic statistics. After a brief primer in algebra and biology, we will survey some of this current literature. Students will be encouraged to select topics for study and to participate in class discussions.

*Prerequisites*: The class is suitable for graduate students who have a background in discrete applied mathematics, preferrably with experience in algebra and/or combinatorics. Familiarity with basic biology will be helpful, but is neither necessary nor sufficient for taking the course.

Topic | Date | Lecturer | Title | Homework | Notes and Links | ||
---|---|---|---|---|---|---|---|

HTML | HTML | ||||||

What is the mathematics of phylogenomics? | August 31st | Lior Pachter | Introduction to the mathematics of phylogenomics | HW #1 | The Mathematics of Phylogenomics | ||

September 2nd | Lior Pachter Bernd Sturmfels | Introduction to biology Algebra basics | On-Line Biology Book NCBI home page Gröbner bases 1 Gröbner bases 2 | ||||

Hidden Markov models and gene finding | September 7th | Lior Pachter | Hidden Markov models | HW #2 | MATLAB example Region for annotation | Likelihood function for a binary model of length three Regions of the explanations | |

September 9th | Lior Pachter | Gene finding | |||||

Tropical geometry and parametric inference | September 14th | Bernd Sturmfels | Introduction to tropical geometry | Handout: page 1 page 2 | Tropical Mathematics | ||

September 16th | Lior Pachter | Pair HMMs and sequence alignment | |||||

Maximum likelihood estimation | September 21st | Dan Levy | Introduction to Maximum likelihood | ||||

September 21st -- 3:45PM | Serkan Hosten | The Maximum Likelihood Degree | The Maximum Likelihood Degree | ||||

Bernd Sturmfels | Solving The likelihood Equations | Solving the Likelihood Equations | |||||

September 23rd | Mathias Drton Luis Garcia | Binary bi-directed four chain | |||||

Sequence alignment | September 28th | Lior Pachter Colin Dewey | Parametric inference | Parametric Inference for Biological Sequence Analysis Tropical Geometry of Statistical Models | |||

September 30th | Lior Pachter | Project assignments | |||||

September 30th -- 4:00PM | Leroy Hood | ||||||

Phylogenetic trees | October 5th | Lior Pachter | The four point condition | A Note on the Metric Properties of Trees | Reconstructing Trees from Subtree Weights | ||

October 7th | Lior Pachter | Characterizations of trees | Geometry of the Space of Phylogenetic Trees The Tropical Grassmanian | ||||

Evolutionary models | October 12th | Lior Pachter | Markov models on trees | ||||

October 14th | Seth Sullivant | Phylogenetic invariants for trees and networks | Phylogenetic Algebraic Geometry Toric Ideals of Phylogenetic Invariants | ||||

Reconstructing trees and networks I | October 19th | Sagi Snir | Convex recolorings of trees | ||||

October 21st -- 12:00PM | Michael Hendy | Tandem duplication trees | |||||

October 21st | David Bryant | Cyclic splits and network reconstruction | Neighbor-Net: An Agglomerative Method for the Construction of Phylogenetic Networks | ||||

Reconstructing trees and networks II | October 26th | Group meetings for preliminary proposals | |||||

October 28th | Nicholas Eriksson | Constructing trees using singular value decomposition | |||||

Bay Area Discrete Math Day | October 30th | ||||||

RNA metrics and alignment | November 2nd | Ian Holmes | Simultaneous alignment and phylogeny | ||||

November 4th | Lior Pachter | RNA metrics | |||||

November 4th -- 4:10PM | Philip Hanlon | ||||||

Group presentation | November 9th | Parametric inference with few parameters | |||||

Veterans day holiday | November 11th | ||||||

Group presentation | November 16th | HMM: Algebraic tools | |||||

Algebraic statistics and other biology | November 18th | Niko Beerenwinkel | Computational Analysis of HIV Drug Resistance Data | RECOMB paper | |||

Group presentation | November 23rd | HMM: Numerical tools | |||||

Thanksgiving holiday | November 25th | ||||||

November 30th | Raazesh Sainudiin | Rigorous numerical statistics via enclosures | Talk abstract | ||||

Group presentation | December 2nd | Small trees | Small trees website | ||||

Group presentation | December 7th | What happened to the data? | |||||

Conclusion | December 9th | Lior Pachter Bernd Sturmfels | Reports due in class |

G. Pistone, E. Riccomagno, H.P. Wynn,

D. Cox, D. O'Shea, J.B. Little,

C. Semple, M. Steel,

Abstracts from a mini-workshop on algebraic statistics (held in Berkeley 14-16 January, 2003).

Seminar on the mathematics of phylogenetics trees hosted by Lior Pachter and Bernd Sturmfels, Fall 2003.

Template for reports.

Probability on Trees and Networks

Combinatorial Commutative Algebra

Maintained by Lior Pachter.