Efficient algorithms for training the parameters of hidden Markov models using stochastic expectation maximization...

Area of Science:

• Bioinformatics
• Computational Biology
• Machine Learning

Background:

• Hidden Markov models (HMMs) are fundamental in bioinformatics for tasks like gene prediction and time-series analysis.
• Accurate HMM application relies on parameter training tailored to specific datasets (e.g., species genomes).
• Developing computationally efficient training algorithms is crucial for maximizing the utility of HMMs in bioinformatics.

Purpose of the Study:

• To introduce novel, computationally efficient algorithms for Viterbi and stochastic expectation maximization (EM) training of HMMs.
• To reduce the memory requirements of HMM parameter training, making them independent of sequence length.
• To simplify the implementation of HMM training algorithms.

Main Methods:

• Developed two novel, single-pass algorithms for Viterbi and stochastic EM training.
• Implemented these algorithms alongside a linear-memory EM algorithm in the HMM-CONVERTER software.
• Evaluated the practical performance of the new algorithms using three small example models.

Main Results:

• Introduced Viterbi and stochastic EM training algorithms with memory requirements independent of sequence length.
• These algorithms perform training in a single pass, unlike existing two-step methods.
• Empirical evaluation in HMM-CONVERTER demonstrated the practical utility of the new algorithms.

Conclusions:

• The new algorithms offer significant computational and memory efficiency improvements for Viterbi and stochastic EM training in HMMs.
• These advancements allow for parameter training on more complex models and extended sequences.
• The developed algorithms are simpler to implement compared to existing default methods, enhancing usability in bioinformatics.