Pair HMM

Pair HMMs are generative models that extend traditional HMMs by having two observation sequences instead of one. The pair HMM emits edit operations between pairs of observations, and by doing so, generates an alignment of the two sequences through the hidden states.

Pair HMMs models have been used for estimating string similarity, based on the string edit distance between the two observation sequences. They are also widely used for biological sequence analysis.

Single-State Pair HMM

A simple pair HMM can be defined over a single state which emits edit operations between two observation sequences, $x^{T},y^{V}$, as well as an end symbol.

• Let $E$ be a set of edit operations, including deletions $(x,\epsilon )$, insertions $(\epsilon ,y)$ and substitutions $(x,y)$, and an end symbol $(\#)$.
• Let $\theta _{e}$ be the emission probability over the edit operation $e\in E$
• Let $z^{n}$ be a sequence of edit operations over $x$ and $y$, and $r_{k}$ is the hidden property of the edit operation $z_{k}$, representing the amount of symbols that have been consumed of each of the observation strings so far. $r_{k}\in \{1..T\}\times \{1..V\}$

String Edit Distance based on a Pair HMM

Given a pair of input strings and a pair HMM, we can define two types of edit distances:

• The Viterbi distance is defined as the most likely transduction between the two strings and it is given by

$d(x^{T},y^{V})=-\log \arg \max _{Edit(z^{n},x^{T},y^{V})}p(z^{n}|\Theta )$

• The Stochastic distance is defined as the aggregation of all possible transductions between the two strings and is given by

$d(x^{T},y^{V})=-\log \ p(x^{T},y^{V}|\Theta )$

Inference

Inference on pair HMMs is done with versions of the Forward and Backward algorithms which track the possible edit operations over positions on both observable strings.

$\alpha (t,v)=p(x^{t},y^{v})=p(x^{t-1},y^{v-1})\cdot \theta _{(x_{t},y_{v})}+p(x^{t-1},y^{v})\cdot \theta _{(x_{t},\epsilon )}+p(x^{t},y^{v-1})\cdot \theta _{(\epsilon ,y_{v})}$

$=\alpha (t-1,v-1)\cdot \theta _{(x_{t},y_{v})}+\alpha (t-1,v)\cdot \theta _{(x_{t},\epsilon )}+\alpha (t,v-1)\cdot \theta _{(\epsilon ,y_{v})}$

And similarly:

$\beta (t,v)=p(x_{t+1}^{T},y_{v+1}^{V})$

Multi-State Pair HMM

The single-state definition can be extended to multiple states (for example, distincs states may be defined for Deletions, Insertions and Substitutions). The dynamic programming algorithms for inference and decoding used in the single-state case, are easily extended to the multi-state case by iterating over a third dimension (representing the states).

Relevant Papers

method