Cache-Oblivious Dynamic Programming for Bioinformatics

被引：18

作者：

Chowdhury, Rezaul Alam ^{[1
]}

Le, Hai-Son ^{[2
]}

Ramachandran, Vijaya ^{[3
]}

机构：

[1] Univ Texas Austin, Ctr Computat Visualizat, Inst Computat Engn & Sci, Austin, TX 78712 USA

[2] Carnegie Mellon Univ, Sch Comp Sci, Dept Machine Learning, Pittsburgh, PA 15213 USA

[3] Univ Texas Austin, Dept Comp Sci, Austin, TX 78712 USA

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2010年 / 7卷 / 03期

基金：

美国国家科学基金会;

关键词：

Sequence alignment; median; RNA secondary structure prediction; dynamic programming; cache-efficient; cache-oblivious; LINEAR-SPACE ALGORITHM; STRUCTURE PREDICTION; COMPLEXITY; SEQUENCES; ALIGNMENT;

D O I：

10.1109/TCBB.2008.94

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

We present efficient cache-oblivious algorithms for some well-studied string problems in bioinformatics including the longest common subsequence, global pairwise sequence alignment and three-way sequence alignment ( or median), both with affine gap costs, and RNA secondary structure prediction with simple pseudoknots. For each of these problems, we present cache-oblivious algorithms that match the best-known time complexity, match or improve the best-known space complexity, and improve significantly over the cache-efficiency of earlier algorithms. We present experimental results which show that our cache-oblivious algorithms run faster than software and implementations based on previous best algorithms for these problems.

引用

页码：495 / 510

页数：16

共 43 条

[11] Chow A, 2007, J INSECT SCI, V7, P3
[12] CHOWDHURY R, 2010, P 24 IEEE I IN PRESS
[13] CHOWDHURY R, 2010, THEORY COMP IN PRESS
[14] CHOWDHURY R, 2008, P 20 S PAR ALG ARCH, P207
[15] CHOWDHURY RA, 2007, P 19 ANN ACM S PAR A, P71
[16] Chowdhury Rezaul, 2007, THESIS U TEXAS AUSTI
[17] Cache-Oblivious Dynamic Programming
Chowdhury, Rezaul Alam
Ramachandran, Vijaya
[J]. PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 591 - 600
[18] Cormen T., 2001, Introduction to Algorithms
[19] CROCHEMORE M, 2006, SIAM J COMPUT, V32, P1654
[20] Comprehensive aligned sequence construction for automated design of effective probes (CASCADE-P) using 16S rDNA
DeSantis, TZ
Dubosarskiy, I
Murray, SR
Andersen, GL
[J]. BIOINFORMATICS, 2003, 19 (12) : 1461 - 1468

← 1 2 3 4 5 →