String Transducers can be "composed" to yield multi-sequence transducers and HMMs.
This page contains references and examples of transducer composition.
Descriptions of Transducer Composition
A colloquial introduction to transducer composition algorithms & notation can be found on this wiki page:
- Phylo Composer -- user's guide to the phylocomposer program, which implements the algorithm for biological sequence inference
The algorithms are described formally in the following paper
- Holmes &: Using guide trees to construct multiple-sequence evolutionary HMMs. Bioinformatics 2003;19 Suppl 1:i147-57.
- Local copy (PDF)
- Errata/supplementals to the paper, maintained on this wiki
Diagrams of Transducer Composition
The diagrams on these wiki pages illustrate the transducer composition algorithm in the case of a simple affine-gap transducer.
- Gotoh Transducer
- Serial Composition Of Gotoh Transducers
- Singlet Transducer
- Gotoh Pair HMM
- Renormalized Transducer Composition
Movies of Transducer Composition
References for Transducer Composition
- Holmes &: Using guide trees to construct multiple-sequence evolutionary HMMs. Bioinformatics 2003;19 Suppl 1:i147-57. (PDF) (errata)
- Contains algorithms for efficient transducer composition on phylogenetic trees
- algorithm for "collapsed EHMM" needs slight modification; see errata published on this wiki
- Computational linguistics
- Holmes & Bruno: Evolutionary HMMs: a Bayesian approach to multiple alignment. Bioinformatics 2001;17:803-20. (PDF)
- Statistical alignment literature (longer list of references)
- String Transducers wiki page