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.
Newberg
Lee A
LA
New York State Department of Health, Center for Bioinformatics, Wadsworth Center, Albany, NY 12208-3425, USA. leen@cs.rpi.edu
D000465:Algorithms; D016247:Information Storage and Retrieval / Q000379:methods*; D009716:Numerical Analysis, Computer-Assisted; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*