Multicore and GPU algorithms for Nussinov RNA folding

BMC Bioinformatics

Research

Sanjay Ranka¹  Junjie Li¹  Sartaj Sahni¹ 

[1] Department of Computer and Information Science and Engineering, University of Florida, 32611, Gainesville, USA;

关键词: Nussinov;    Multicore;    CUDA;    GPU;    RNA;   

DOI  :  10.1186/1471-2105-15-S8-S1

来源: Springer

【 摘 要 】

BackgroundOne segment of a RNA sequence might be paired with another segment of the same RNA sequence due to the force of hydrogen bonds. This two-dimensional structure is called the RNA sequence's secondary structure. Several algorithms have been proposed to predict an RNA sequence's secondary structure. These algorithms are referred to as RNA folding algorithms.ResultsWe develop cache efficient, multicore, and GPU algorithms for RNA folding using Nussinov's algorithm.ConclusionsOur cache efficient algorithm provides a speedup between 1.6 and 3.0 relative to a naive straightforward single core code. The multicore version of the cache efficient single core algorithm provides a speedup, relative to the naive single core algorithm, between 7.5 and 14.0 on a 6 core hyperthreaded CPU. Our GPU algorithm for the NVIDIA C2050 is up to 1582 times as fast as the naive single core algorithm and between 5.1 and 11.2 times as fast as the fastest previously known GPU algorithm for Nussinov RNA folding.

【 授权许可】

CC BY   
© Li et al.; licensee BioMed Central Ltd. 2014