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:
-
DNA
match probability computation in forensic science; and
-
likelihood computation under the coalescent with recombination, a
genealogy-based stochastic process widely used in population
genetics.