Efficient algorithms for training the parameters of hidden Markov models using stochastic expectation maximization (EM) training and Viterbi training

We introduce two computationally efficient training algorithms, one for Viterbi training and one for stochastic expectation maximization (EM) training, which render the memory requirements independent of the sequence length. Unlike the existing algorithms for Viterbi and stochastic EM training which require a two-step procedure, our two new algorithms require only one step and scan the input sequence in only one direction. We also implement these two new algorithms and the already published linear-memory algorithm for EM training into the hidden Markov model compiler HMM-CONVERTER and examine their respective practical merits for three small example models.Bioinformatics applications employing hidden Markov models can use the two algorithms in order to make Viterbi training and stochastic EM training more computationally efficient. Using these algorithms, parameter training can thus be attempted for more complex models and longer training sequences. The two new algorithms have the added advantage of being easier to implement than the corresponding default algorithms for Viterbi training and stochastic EM training.Hidden Markov models (HMMs) and their variants are widely used for analyzing biological sequence data. Bioinformatics applications range from methods for comparative gene prediction (e.g. [1,2]) to methods for modeling promoter grammars (e.g. [3]), identifying protein domains (e.g. [4]), predicting protein interfaces (e.g. [5]), the topology of transmembrane proteins (e.g. [6]) and residue-residue contacts in protein structures (e.g. [7]), querying pathways in protein interaction networks (e.g. [8]), predicting the occupancy of transcription factors (e.g. [9]) as well as inference models for genome-wide association studies (e.g. [10]) and disease association tests for inferring ancestral haplotypes (e.g. [11]).Most of these bioinformatics applications have been set up for a specific type of analysis and a specific biological data set, at least initially. Th