Memory-efficient dynamic programming backtrace and pairwise local sequence alignment

作者：Newberg Lee A^*

来源：Bioinformatics, 2008, 24(16): 1772-1778.

DOI：10.1093/bioinformatics/btn308

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.

• 出版日期2008-8-15
• 单位上海生物信息技术研究中心