Memory-efficient dynamic programming backtrace and pairwise local sequence alignment Export

@article{newberg:dynamic, 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. Contact: leen@cs.rpi.edu 10.1093/bioinformatics/btn308}, author = {Newberg, Lee A.}, citeulike-article-id = {2902512}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/bioinformatics/btn308}, citeulike-linkout-1 = {http://bioinformatics.oxfordjournals.org/cgi/content/abstract/24/16/1772}, citeulike-linkout-2 = {http://view.ncbi.nlm.nih.gov/pubmed/18558620}, citeulike-linkout-3 = {http://www.hubmed.org/display.cgi?uids=18558620}, day = {16}, doi = {10.1093/bioinformatics/btn308}, journal = {Bioinformatics}, keywords = {alignment, dynamic, programming}, month = {June}, pages = {btn308+}, posted-at = {2008-06-17 14:58:26}, priority = {2}, title = {Memory-efficient dynamic programming backtrace and pairwise local sequence alignment}, url = {http://dx.doi.org/10.1093/bioinformatics/btn308}, year = {2008} }

TY - JOUR ID - newberg:dynamic L3 - citeulike-article-id:2902512 N2 - 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. Contact: leen@cs.rpi.edu 10.1093/bioinformatics/btn308 JF - Bioinformatics TI - Memory-efficient dynamic programming backtrace and pairwise local sequence alignment SP - btn308 KW - alignment KW - dynamic KW - programming AU - Newberg, Lee PY - 2008/06/16/ UR - http://dx.doi.org/10.1093/bioinformatics/btn308 ER -