GTfold: A scalable multicore code for RNA secondary structure prediction

Amrita Mathuriya, David A. Bader, Christine E. Heitsch, Stephen C. Harvey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

The prediction of the correct secondary structures of large RNAs is one of the unsolved challenges of computational molecular biology. Among the major obstacles is the fact that accurate calculations scale as O(n 4), so the computational requirements become prohibitive as the length increases. Existing folding programs implement heuristics and approximations to overcome these limitations. We present a new parallel multicore and scalable program called GTfold, which is one to two orders of magnitude faster than the de facto standard programs and achieves comparable accuracy of prediction. Development of GTfold opens up a new path for the algorithmic improvements and application of an improved thermodynamic model to increase the prediction accuracy. In this paper we analyze the algorithm's concurrency and describe the parallelism for a shared memory environment such as a symmetric multiprocessor or multicore chip. In a remarkable demonstration, GTfold now optimally folds 11 picornaviral RNA sequences ranging from 7100 to 8200 nucleotides in 8 minutes, compared with the two months it took in a previous study. We are seeing a paradigm shift to multicore chips and parallelism must be explicitly addressed to continue gaining performance with each new generation of systems. We also show that the exact algorithms like internal loop speedup can be implemented with our method in an affordable amount of time. GTfold is freely available as open source from our website.

Original languageEnglish (US)
Title of host publication24th Annual ACM Symposium on Applied Computing, SAC 2009
Pages981-988
Number of pages8
DOIs
StatePublished - 2009
Externally publishedYes
Event24th Annual ACM Symposium on Applied Computing, SAC 2009 - Honolulu, HI, United States
Duration: Mar 8 2009Mar 12 2009

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Other

Other24th Annual ACM Symposium on Applied Computing, SAC 2009
Country/TerritoryUnited States
CityHonolulu, HI
Period3/8/093/12/09

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Computational biology
  • Parallel algorithms
  • Ribosomal and viral RNA

Fingerprint

Dive into the research topics of 'GTfold: A scalable multicore code for RNA secondary structure prediction'. Together they form a unique fingerprint.

Cite this