Ontology highlight
ABSTRACT: Motivation
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.Availability
Sample C++-code for optimal backtrace is available in the Supplementary Materials.Supplementary information
Supplementary data is available at Bioinformatics online.
SUBMITTER: Newberg LA
PROVIDER: S-EPMC2668612 | biostudies-literature |
REPOSITORIES: biostudies-literature