13 - Homology Mapping with Markov Random Fields

Summary

In this chapter we present a probabilistic approach to the homology mapping problem. This is the problem of identifying regions among genomic sequences that diverged from the same region in a common ancestor. We explore this question as a combinatorial optimization problem, seeking the best assignment of labels to the nodes in a Markov random field. The general problem is formulated using toric models, for which it is unfortunately intractable to find an exact solution. However, for a relevant subclass of models, we find a (non-integer) linear programming formulation that gives us the exact integer solution in polynomial time in the size of the problem. It is encouraging that for a useful subclass of toric models, maximum a posteriori inference is tractable.

Genome mapping

Evolutionary divergence gives rise to different present-day genomes that are related by shared ancestry. Evolutionary events occur at varying rates, but also at different scales of genomic regions. Local mutation events (for instance, the point mutations, insertions and deletions discussed in Section 4.5) occur at the level of one or several base-pairs. Large-scale mutations can occur at the level of single or multiple genes, chromosomes, or even an entire genome. Some of these mutation mechanisms such as rearrangement and duplication, were briefly introduced in Section 4.1. As a result, regions in two different genomes could be tied to a single region in the ancestral genome, linked by a series of mutational events.