Extended Hidden Markov Models And Parameter Estimation Based On Genetic Algorithm

The Hidden Markov Models which consist of a hidden Markov process and an observation process are statistical models,and the abbreviation is HMM.They were brought forward by Baum and his colleagues in the late sixties and early seventies.In 1970s,they were applied into speech recognition by Jenik and some other people and have been one of the most efficient techniques in this area.Besides, they have also been widely used in biostatistics,gene recognition,character recognition and image processing etc nowadays.Genetic Algorithm,also known as GA brought forward by Holland in University of Chicago, is one of self-organized and self-adaptive artificial intelligence techniques for Extremum Problem by simulating the natural evolution process and mechanism.In this dessertation,we start with the extension of HMM.Firstly, we propose a new generalized Markov model Hierarchical Hidden Markov Model (HHMM), and several new analytic formulae for solving three basic problems which are similar to forward-backward algorithm,Viterbi algorithm and studying algorithm of HMM were theoretically derived. Secondly, based on the assumption that the sequence of observations could be segmented into a set of subsequences generated by a sub-process with only weak interactions with its neighbors, this dessertation provides an improvement method on Hidden Markov Models composed of blocks. Thirdly, this paper shows how to align biological sequences with HMM: pairwise alignment using Pair HMM and multiple alignment using Profile HMM. At last, a genetic algorithm is designed by employing Baum-Welch algorithm to estimate the parameters of profile HMM in multiple sequence alignment.