zipHMMlib: a highly optimised HMM library exploiting repetitions in the input to speed up the forward algorithm

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Hidden Markov models (HMMs) are essential for genome analysis due to their flexible modeling and efficient algorithms.
• The forward algorithm, commonly used for HMM likelihood calculation, faces computational challenges with large genomic sequences.
• Optimizing the forward algorithm is crucial for efficient HMM-based genome analysis.

Purpose of the Study:

• To develop a time-efficient software library for computing Hidden Markov Model likelihoods.
• To address the computational bottlenecks of HMM analysis in large-scale genomic datasets.

Main Methods:

• Developed a software library that preprocesses sequence data to identify and exploit common substrings.
• Implemented a structure to reuse computations within the forward algorithm based on identified substrings.
• The preprocessing step is independent of specific HMMs, allowing reuse across different models.

Main Results:

• Achieved significant speedups, with wall-clock times reduced by up to 78 times for realistic whole-genome analyses.
• Demonstrated a case where analysis time was reduced from 9.6 hours to under 8 minutes.
• The library effectively reuses computations, drastically improving efficiency for complex HMMs.

Conclusions:

• Implemented the optimized forward algorithm and preprocessing as a C++ library named zipHMM.
• Provided Python bindings for easy integration into scripting workflows.
• The zipHMM library is publicly available for use in genomic research.