Viterbi training of Hidden Markov Models for labeled sequences
Margarita C. Theodoropoulou, Ioannis Mintsopoulos, Pantelis G. Bagos · 2017
Hidden Markov Models (HMMs) are probabilistic models that have been successfully applied during the last years for various tasks in molecular biology (usually Class HMMs). There are two types of problems that must be solved while building an HMM: a. estimating the model parameters (transition and emission probabilities) from the observed sequence and b. finding the hidden sequence of states given the observed sequence (decoding). Traditionally, the parameters of a HMM are optimized according to the Maximum Likelihood criterion, mainly using the efficient Baum-Welch algorithm and the decoding is performed using the standard Viterbi algorithm or the N-best algorithm. A different approach to parameter estimation is Viterbi Training (VT). VT estimates the parameters only of the most probable hidden state sequence already produced by the Viterbi algorithm, rather than maximizing the likelihood of the observed data. Here, we present the development of VT algorithm for labeled sequences. In order to evaluate the VT algorithm we performed tests in a number of important biological problems previously studied by our team (prediction of transmembrane proteins and prediction of signal peptides). In all five biological problems using the VT algorithm, we managed to diminish considerably both the iterations needed and the total time spent on training, with a negligible (if any) decrease in the model’s efficiency. In the era of big data, the efficient and, yet, fast algorithms are an urgent need and we believe that the new algorithm will be useful in this respect.