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.