Sywise in the latest Genewise release does this I think.
& follow Wise* links.
Alternatively the package that Sywise is written in - Dynamite - allows
flexible design of finite state automata. If Ewan Birney hasn't already
written an automaton to align protein at the DNA level then it would be
very easy to do so, or mail him on birney at sanger.ac.uk