Back to search

University of Southampton

Evolving the structure of Hidden Markov Models for biological sequence analysis

Abstract

dc:description.abstract

<p>Hidden Markov Models (HMMs) are widely used for biological sequence analysis because of their ability to incorporate biological information in their structure. An automatic method of optimising the structure of HMMs for biological sequence analysis is highly desirable.</p> <p>In this thesis, we explore the possibility of using a genetic algorithm (GA) for optimising the HMM structure. The Baum-Welch algorithm is hybridised within its evolutionary cycle. To prevent overfitting, a separate dataset is used for comparing the performance of the HMMs to that used for the Baum-Welch training.</p> <p>The proposed GA for hidden Markov models (GA-HMM) allows HMMs with different number of states to evolve. The GA-HMM was capable of finding an HMM comparable to a hand-coded HMM designed for the same task, which has been published previously.</p> <p>We also propose Block-HMMs where the topology of HMMs was assembled from biologically meaningful building blocks. New genetic operators are designed to evolve the HMM structure while preserving the blocks.</p> <p>We applied the evolving HMM structure methods to modelling the promoter and coding region of a prokaryote and predicting the secondary structure of proteins. The Block-HMM method could generate HMM structures and find conserved promoter region and triplet codon model without any prior information on the sequences. When the Block-HMM is tested for the protein secondary structure prediction problem, it showed superior performance to other prediction methods using HMMs and was comparable to the best known techniques for this problem.</p>

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Won, Kyoung-Jae

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Won, Kyoung-Jae. Evolving the structure of Hidden Markov Models for biological sequence analysis. doctoral thesis, University of Southampton, 2005.