1 Abstract

1.1 Motivation

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.

1.2 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\sqrt{n})$ with only a 10% slowdown for small m and n and vast speedup for the larger values, such as m=n=2000, that cause excessive paging on a 96MByte workstation. The results are applicable to other types of dynamic programming.

1.3 Availability

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.

1.4 Contact

Richard Hughey, Department of Computer Engineering, Jack Baskin School of Engineering, University of California, Santa Cruz, California 95064. Email: rph@cse.ucsc.edu. WWW: http://www.cse.ucsc.edu/~rph. Phone: (408) 459-2939. Fax: (408) 459-4829.