  We present an extension of Felsenstein's algorithm to indel models defined on
entire sequences, without the need to condition on one multiple alignment. The
algorithm makes use of a generalization from probabilistic substitution
matrices to weighted finite-state transducers. Our approach may equivalently be
viewed as a probabilistic formulation of progressive multiple sequence
alignment, using partial-order graphs to represent ensemble profiles of
ancestral sequences. We present a hierarchical stochastic approximation
technique which makes this algorithm tractable for alignment analyses of
reasonable size.
