title: Multicore and GPU algorithms for Nussinov RNA folding.
abstract: BACKGROUND
  One 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.
  
  
  RESULTS
  We develop cache efficient, multicore, and GPU algorithms for RNA folding using Nussinov's algorithm.
  
  
  CONCLUSIONS
  Our 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.
authors.forename: Junjie
authors.initials: J
authors.lastname: Li
authors.forename: Sanjay
authors.initials: S
authors.lastname: Ranka
authors.forename: Sartaj
authors.initials: S
authors.lastname: Sahni
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000295:instrumentation* / Q000379:methods; D003201:Computers; D008838:Microcomputers; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D059370:RNA Folding
chemical_list: D012313:RNA
references.citation: BMC Bioinformatics. 2009 Jan 30;10 Suppl 1:S37
references.pmid: 19208138
references.citation: BMC Res Notes. 2012 Jul 02;5:341
references.pmid: 22747589
references.citation: Nucleic Acids Res. 1981 Jan 10;9(1):133-48
references.pmid: 6163133