Tuesday, April 3, 2007
4:15 pm
B17 Upson Hall

Computer Science
Spring 2007

Yun Song
UC Davis

Graphical and Algorithmic
Approaches to Probability Computation in Genetics


Given a model of DNA sequence evolution with a set of parameters, computing the probability of observing data is a fundamental problem in genetics, but obtaining accurate results often is a challenging task. In this talk, I will describe how graph theoretic and algorithmic ideas can be employed to tackle the problem of computing exact probabilities. Two specific problems I will address are:

  1. DNA match probability computation in forensic science; and

  2. likelihood computation under the coalescent with recombination, a genealogy-based stochastic process widely used in population genetics.