Have you looked at existing genomic alignment algorithms? I'd be surprised if Needleman-Wunsch didn't fit your needs.

Viterbi and Needleman-Wunsch are essentially the same algorithm, developed in parallel for two different domains! The Viterbi formulation of the algorithm is the one usually applied to signal decoding, since that's what it was originally designed for.