Evolving the structure of hidden Markov models

Author

Won, Kyoung-Jae ; Prügel-Bennett, Adam ; Krogh, Anders

Author_Institution

Sch. of Electron. & Comput. Sci., Univ. of Southampton, UK

Volume

10

Issue

1

fYear

2006

Firstpage

39

Lastpage

49

Abstract

A genetic algorithm (GA) is proposed for finding the structure of hidden Markov Models (HMMs) used for biological sequence analysis. The GA is designed to preserve biologically meaningful building blocks. The search through the space of HMM structures is combined with optimization of the emission and transition probabilities using the classic Baum-Welch algorithm. The system is tested on the problem of finding the promoter and coding region of C. jejuni. The resulting HMM has a superior discrimination ability to a handcrafted model that has been published in the literature.

Keywords

biology; genetic algorithms; hidden Markov models; probability; Baum-Welch algorithm; C. jejuni; biological sequence analysis; coding region; emission probability; genetic algorithm; hidden Markov models; promoter region; transition probability; Algorithm design and analysis; Approximation error; Bioinformatics; Biological system modeling; Estimation error; Genetic algorithms; Hidden Markov models; Machine learning; Machine learning algorithms; System testing; Biological sequence analysis; genetic algorithm (GA); hidden Markov model (HMM); hybrid algorithm; machine learning;

fLanguage

English

Journal_Title

Evolutionary Computation, IEEE Transactions on

Publisher

ieee

ISSN

1089-778X

Type

jour

DOI

10.1109/TEVC.2005.851271

Filename

1583626