Reduced space hidden Markov model training.
BACKGROUND
Complete forward-backward (Baum-Welch) hidden Markov model training cannot take advantage of the linear space, divide-and-conquer sequence alignment algorithms because of the examination of all possible paths rather than the single best path.


RESULTS
This paper discusses the implementation and performance of checkpoint-based reduced space sequence alignment in the SAM hidden Markov modeling package. Implementation of the checkpoint algorithm reduced memory usage from O(mn) to O (m square root n) with only a 10% slowdown for small m and n, and vast speed-up for the larger values, such as m = n = 2000, that cause excessive paging on a 96 Mbyte workstation. The results are applicable to other types of dynamic programming.


BACKGROUND
A World-Wide Web server, as well as information on obtaining the Sequence Alignment and Modeling (SAM) software suite, can be found at http://www.cse.ucsc. edu/research/compbio/sam.html.


BACKGROUND
rph@cse.ucsc.edu
Tarnas
C
C
Department of Computer Engineering, Jack Baskin School of Engineering, University of California, Santa Cruz, CA 95064, USA.
Hughey
R
R
D000465:Algorithms; D019295:Computational Biology; D008390:Markov Chains; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D012984:Software; D013997:Time Factors