Memory-efficient dynamic programming backtrace and pairwise local sequence alignment.
BACKGROUND
A backtrace through a dynamic programming algorithm's intermediate results in search of an optimal path, or to sample paths according to an implied probability distribution, or as the second stage of a forward-backward algorithm, is a task of fundamental importance in computational biology. When there is insufficient space to store all intermediate results in high-speed memory (e.g. cache) existing approaches store selected stages of the computation, and recompute missing values from these checkpoints on an as-needed basis.


RESULTS
Here we present an optimal checkpointing strategy, and demonstrate its utility with pairwise local sequence alignment of sequences of length 10,000.


BACKGROUND
Sample C++-code for optimal backtrace is available in the Supplementary Materials.


BACKGROUND
Supplementary data is available at Bioinformatics online.
New York State Department of Health, Center for Bioinformatics, Wadsworth Center, Albany, NY 12208-3425, USA. leen@cs.rpi.edu
Lee A
LA
Newberg
D000465:Algorithms; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*