Viterbi is an algorithm for finding the maximum likelihood assignment to the hidden variables of an HMM, given the observed variables (we know the transition and emission probabilities of the HMM). However, the dynamic programming algorithm that finds the best alignment between two strings (SmithWaterman), is also referred to as Viterbi. I'm trying to understand why SmithWaterman is an instantiation of Viterbi. Specifically, what is the HMM that represents the alignment problem, what are the possible values for the hidden variables, what are the emission probabilities for each hidden variable, and what is the observed data. Can you help me see the correspondence?

Consider the problem of finding the best score rather than the item that achieves the best score. Then both of these algorithms are matrix multplications in the tropical semiring. In other words they can be written as matrix multiplications over the reals union $\infty$, where the usual $+$ operation is replaced by $\min$ and multiplication is replaced by $+$. (You may need to think in terms of log probabilities to see the correspondence.) You can see this by looking at the innermost loops of both algorithms. For example, the viterbi algorithm code at wikipedia has the $\min$ of a bunch of "emit_p[source_state][output] * trans_p[source_state][next_state]" in its innermost loop, just like the $a_{ij}b_{jk}$ in the definition of matrix multiplication. Similarly, if you look at the wikipedia edit distance algorithm the core work is done by a line "d[i, j] := minimum(d[i1, j] + 1, d[i, j1] + 1, d[i1, j1] + 1)". Again it's the $\min$ of a bunch of sums. In fact, I wrote one piece of code code to implement both edit distance and Viterbi a while back. Unfortunately that article's probably gobblydegook if you don't know Haskell, but the text around the diagrams may be helpful. (I should have made clear first time, edit distance and SmithWaterman are pretty much the same thing, just with different weights.) 


I think the best way of seeing the similarities is to see both algorithms as shortest path methods: Given a graph of a certain diameter, you find the shortest path between a start and a finish node recursively by first finding all shortest paths of length 1, then using that to find all shortest paths of length 2, and so on. When you reach the diameter of the graph, you know you have found the global minimum. In the case of a Hidden Markov Model, the nodes in the graph are value assignment pairs $(s_i,v)$, where $s_i$ is a hidden variable, and $v$ is one of its values. Two pairs are then connected if they assign values to two consecutive variables, $s_i$ and $s_{i+1}$. One will typically also add a dummy start node that connects to all the time $1$ variablevalue pairs, $(s_1,v)$, and a finish node to which all the time $n$ variablevalue pairs $(s_n,v)$ are connected. A value assignment for the whole sequences is then a path between these two dummy nodes. In the case of string matching algorithms, the nodes are positions $(i,j)$, indicating how much of each of the two strings we have consumed so far. The possible transitions are determined by the editing operations you have access to: A deletion will for instance correspond to a step from $(i,j)$ to $(i+1,j)$ since it consumes input character but no output characters. In this case, an alignment corresponds to a path from the position $(0,0)$ to the position $(n,m)$ if you require both strings to be consumed entirely. If, on the other hand, you only require the first string to be consumed, any path terminating at the wall $\{(n,k):\, k=1,2,\ldots,m\}$ will do. In both cases, the available steps from node to node need to be equipped with price tags for the minimization problem to make sense. In the case of the HMM, the step from $(s_i,v_i)$ to $(s_{i+1},v_{i+1})$ should be assigned the logarithmic price $$ \log \frac{1}{p(s_{i+1}\, \,s_i)} + \frac{1}{\log p(e\, \, s_{i+1})}, $$ where $p(s_{i+1}\, \,s_i)$ is the transition probability, and $p(e\, \, s_{i+1})$ is the emission probability, assuming that the emitted symbol was $e$. Since the individual steps are independent, this logarithmic pricing scheme will make the step prices additive. In the case of string alignment, the prices should be the inverse logarithmic probabilities of various kinds of errors (like reversals, deletions, etc.). I hope this answers you question. You might also want to have a look at chapter 16 of David McKay's Information Theory, Inference, and Learning Algorithms, which discusses these and other algorithms from the perspective of message passing schemes. (You can download it from his website.) 


A HMM for local alignment is shown at http://books.google.com/books?id=R5P2GlJvigQC&pg=PA86 EDIT It's been 7 or 8 years since I really understood this stuff, but I have some old MATLAB code that implements SmithWaterman. Since a cursory search doesn't show any such code, I figured I'd post it here. Although I don't think this is what you're really asking for, perhaps it will help you (or someone else).


