Memory-efficient dynamic programming backtrace and pairwise local sequence alignment

Motivation: A backtrace through a dynamic programming algorithms 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 forwardbackward algorithm, is a task of fundamental importance in computational biology. When there is insuf.cient 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.