Motivation: Dynamic programming is the core algorithm of sequence comparison, alignment and linear hidden Markov model (HMM) training. For a pair of sequence lengths m and n, the problem can be solved readily in O(mn)time and O(mn)space. The checkpoint algorithm introduced by Grice et al. (CABIOS , 13, 45–53, 1997) runs in O(Lmn)time and O(LmL√n)space, where Lis a positive integer determined by m, n, and the amount of available workspace. The algorithm is appropriate for many string comparison problems, including all-paths and single-best-path hidden Markov model training, and is readily parallelizable. The checkpoint algorithm has a diagonal version that can solve the single-best-path alignment problem in O(mn)time and O(m + n)space.
Results: In this work, we improve performance by analyzing optimal checkpoint placement. The improved row checkpoint algorithm performs up to one half the computation of the original algorithm. The improved diagonal checkpoint algorithm performs up to 35% fewer computational steps than the original. We modified the SAM hidden Markov modeling package to use the improved row checkpoint algorithm. For a fixed sequence length, the new version is up to 33% faster for all-paths and 56% faster for single-best-path HMM training, depending on sequence length and allocated memory. Over a typical set of protein sequence lengths, the improvement is ~10%.
Availability: The SAM hidden Markov modeling package is freely available for academic use from http://www.cse.ucsc.edu/research/compbio/sam.html. The C++code used to find optimal checkpoint placements is available from http://www.cse.ucsc.edu/research/kestrel.
Current address: Neomorphic, 2612 8th St., Berkeley, CA 94710, USA.
To whom correspondence may be addressed.