Viterbi algorithm

The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states — the Viterbi path — in a Hidden Markov Model, given a sequence of observations. Developed by Andrew Viterbi in 1967 for decoding convolutional codes in digital communications, it was later adapted to bioinformatics, speech recognition, and natural language processing, becoming one of the most widely applied algorithms in probabilistic inference.

The algorithm operates by maintaining a probability for each state at each time step, representing the maximum probability of any path leading to that state. It recursively computes:

Vₜ(k) = maxₓ [ Vₜ₋₁(x) · aₓₖ · bₖ(oₜ) ]

where Vₜ(k) is the Viterbi probability for state k at time t, aₓₖ is the transition probability from state x to state k, and bₖ(oₜ) is the emission probability of observation oₜ from state k. A backpointer matrix records which predecessor state achieved the maximum, enabling reconstruction of the optimal path by backtracking from the final state.

The Viterbi algorithm is structurally identical to the Needleman-Wunsch algorithm: both fill a dynamic programming matrix where each cell represents an optimal subproblem, and both use backtracking to reconstruct the optimal solution. This isomorphism reveals that sequence alignment and hidden-state decoding are the same problem in different substrates — finding the best path through a graph of possibilities.

In bioinformatics, Viterbi is used to predict protein secondary structure, find genes, and align sequences to profile HMMs. In communications, it remains the standard decoder for convolutional codes. Its O(T·N²) complexity for T observations and N states is efficient enough for real-time applications, making it a rare example of an algorithm that is both theoretically elegant and practically indispensable.