### Inference functions and sequence alignment

### Sergi Elizalde, MSRI

Statistical models are used to solve certain problems in computational
biology, such as determining what parts of the genome will be
translated into proteins, or how a DNA sequence evolved into another
via a series of mutations, insertions and deletions. Each answer has
a certain probability depending on the model parameters. When these
are given, the most probable answer, called the *explanation*, is
obtained by solving a combinatorial optimization problem. The map
sending each observation to its explanation is called an *inference
function*.
Using some theory about lattice polytopes, I will prove that the
number of inference functions of any graphical model is polynomial in
the size of the model. Then I will give applications to optimal
sequence alignment, and discuss some open combinatorial problems that
arise.