Correspondence between Viterbi algorithm and Smith-Waterman
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 (Smith-Waterman), is also referred to as Viterbi. I'm trying to understand why Smith-Waterman 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?