Memory-efficient dynamic programming backtrace and pairwise local sequence alignment.
Bioinformatics
; 24(16): 1772-8, 2008 Aug 15.
Article
em En
| MEDLINE
| ID: mdl-18558620
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.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Algoritmos
/
Análise Numérica Assistida por Computador
/
Armazenamento e Recuperação da Informação
/
Alinhamento de Sequência
/
Análise de Sequência
Idioma:
En
Revista:
Bioinformatics
Assunto da revista:
INFORMATICA MEDICA
Ano de publicação:
2008
Tipo de documento:
Article
País de afiliação:
Estados Unidos