Phylogenetic automata, pruning, and multiple alignment

Code

• github.com/ihh/transducer-tutorial
  OfficialIn papernone★ 0
• github.com/evoldoers/historian
  none★ 0

Abstract

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.

Tasks

Reproductions