HMM sampling and applications to gene finding and alternative splicing.

Area of Science:

• Computational Biology
• Bioinformatics
• Genomics

Background:

• Hidden Markov models (HMMs) are standard for biological sequence analysis, typically using the Viterbi algorithm to find the most likely state path.
• The Viterbi algorithm employs dynamic programming to identify optimal sequences, commonly applied in gene finding to predict DNA structures.

Purpose of the Study:

• To explore the underutilized applications of sampling methods for HMMs in biological sequence analysis.
• To demonstrate how sampling can identify alternative splicing events, including conserved instances across related species.
• To present sampling as a natural method for calculating probabilities of predicted gene structures and exons.

Main Methods:

• Utilizing forward-backward and backtrack algorithms, variants of which are applied in Gibbs sampling.
• Developing a novel, memory-efficient sampling algorithm for specific HMM classes as an alternative to the Hirschberg algorithm for optimal alignment.
• Applying posterior distribution sampling to assess the accuracy of predicted gene structures and exons.

Main Results:

• Sampling methods reveal previously overlooked applications in HMM analysis, particularly for gene finding.
• Identified conserved alternative splicing events between genes of related organisms using HMM sampling.
• Demonstrated the utility of sampling for computing probabilities of predicted exons and gene structures.

Conclusions:

• Sampling methods offer a powerful and versatile approach to HMM analysis in bioinformatics, extending beyond traditional Viterbi pathfinding.
• The presented sampling techniques provide practical solutions for gene finding, alternative splicing analysis, and RNA structure prediction.
• This work highlights the potential of sampling for stochastic context-free grammars and related computational biology problems.