• Miklos I, Lunter GA, Holmes I.  A "Long Indel" model for evolutionary sequence alignment.  Mol Biol Evol. 2004 Mar;21(3):529-40. Epub 2003 Dec 23. (pdf)

It does so at the expense of expanding the finite state transducer into a conditional generalized Pair HMM with arbitrary length distributions for indels, which effectively has a number of states bounded by the product of the sequence lengths.

Finite-state transducer approximations to this model exist (Gotoh Transducer, Knudsen Miyamoto Transducer). A related approximation is the TKF92 model which breaks a sequence into indivisible fragments. (The transducer approximations assume that the branch length is short enough to neglect overlapping indels, whereas the TKF92 model assumes that overlapping indels never occur.)

In fact, it is known that any "concave" gap penalty (i.e. monotonically decreasing gap length distribution) can be well-approximated by a finite state machine, at least for Viterbi alignment:

• Miller W, Myers EW.  Sequence comparison with concave weighting functions.  Bull Math Biol. 1988;50(2):97-120.

-- IanHolmes - 23 Apr 2008

• cited by at least one person as their "favourite paper ever"