Hidden Markov Models and their Applications in Biological Sequence Analysis

Abstract

Hidden Markov models (HMMs) have been extensively used in biological sequence analysis. In this paper, we give a tutorial review of HMMs and their applications in a variety of problems in molecular biology. We especially focus on three types of HMMs: the profile-HMMs, pair-HMMs, and context-sensitive HMMs. We show how these HMMs can be used to solve various sequence analysis problems, such as pairwise and multiple sequence alignments, gene annotation, classification, similarity search, and many others.

Keywords: Hidden Markov model (HMM); context-sensitive HMM (csHMM); pair-HMM; profile-HMM; profile-csHMM; sequence analysis..

Fig. (1)

A simple HMM for modeling eukaryotic genes.

Fig. (2)

Profile hidden Markov model. (a) Multiple sequence alignment for constructing the profile-HMM. (b) The ungapped HMM that represents the consensus sequence of the alignment. (c) The final profile-HMM that allows insertions and deletions.

Fig. (3)

Example of a pair hidden Markov model. A pair-HMM generates an aligned pair of sequences. In this example, two DNA sequences x and z are simultaneously generated by the pair-HMM, where the underlying state sequence is y. Note that the state sequence y uniquely determines the pairwise alignment between x and z .

Fig. (4)

A context-sensitive HMM that generates only symmetric sequences, or palindromes.

Fig. (5)

Constructing a profile-csHMM from a multiple RNA sequence alignment. (a) Example of an RNA sequence alignment. The consensus RNA structure has two base-pairs. (b) An ungapped csHMM constructed from the given alignment. (c) The final profile-csHMM that can handle symbol matches, insertions, and deletions.