Bioinformatics Vol. 16 no. 12 2000
Pages 1082-1090
© 2000 Oxford University Press
Original Paper |
Optimizing reduced-space sequence analysis
1 Department of Computer Engineering, Jack Baskin School of Engineering, University of California, Santa Cruz, CA 95064, USA
Received on October 5, 1999
; revised on May 15, 2000
; accepted on July 25, 2000
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.
Contact: rph{at}cse.ucsc.edu
2 Current address: Neomorphic, 2612 8th St., Berkeley, CA 94710, USA.
3 To whom correspondence may be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  L. A. Newberg Memory-efficient dynamic programming backtrace and pairwise local sequence alignment Bioinformatics, August 15, 2008; 24(16): 1772 - 1778. [Abstract] [PDF]
|
|
|
|
|
|
E. Keibler, M. Arumugam, and M. R. Brent The Treeterbi and Parallel Treeterbi algorithms: efficient, optimal decoding for ordinary, generalized and pair HMMs Bioinformatics, March 1, 2007; 23(5): 545 - 554. [Abstract] [Full Text] [PDF]
|
|