الگوي ماركوف پنهان دوطرفه با حافظۀ خطي

A Bidirectional Hidden Markov Model in Linear Memory

Hidden Markov models are widely used in Bioinformatics. They are applied to protein sequence alignment, protein family annotation and gene-finding. The Baum-Welch training is an expectation-maximization algorithm for training the emission and transition probabilities of hidden Markov models. For very long training sequence, even the most efficient algorithms are memory-consuming. In this paper we discuss different approaches to decrease the memory use and compare the performance of different algorithms. In addition, we propose a bidirection algorithm with linear memory. We apply this algorithm to simulated data of protein profile to analyze the strength and weakness of the algorithm.