Open AccessMemory-efficient dynamic programming backtrace and pairwise local sequence alignment
Author(s) -
Lee A. Newberg
Publication year - 2008
Publication title -
bioinformatics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.599
H-Index - 390
eISSN - 1367-4811
pISSN - 1367-4803
DOI - 10.1093/bioinformatics/btn308
Subject(s) - computer science , pairwise comparison , dynamic programming , sequence (biology) , computation , path (computing) , cache , code (set theory) , sample (material) , algorithm , parallel computing , basis (linear algebra) , multiple sequence alignment , theoretical computer science , sequence alignment , set (abstract data type) , artificial intelligence , mathematics , programming language , biology , chemistry , genetics , geometry , chromatography , biochemistry , gene , peptide sequence
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.