Back to search

Georgia Institute of Technology

Prediction of secondary structures for large RNA molecules

Abstract

dc:description.abstract

The prediction of 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⁴), so the computational requirements become prohibitive as the length increases. 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 mfold and RNAfold for folding large RNA viral sequences and achieves comparable accuracy of prediction. We analyze the algorithm's concurrency and describe the parallelism for a shared memory environment such as a symmetric multiprocessor or multicore chip. 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 provide a rigorous proof of correctness of an optimized algorithm for internal loop calculations called internal loop speedup algorithm (ILSA), which reduces the time complexity of internal loop computations from O(n⁴) to O(n³) and show that the exact algorithms such as ILSA are executed with our method in affordable amount of time. The proof gives insight into solving these kinds of combinatorial problems. We have documented detailed pseudocode of the algorithm for predicting minimum free energy secondary structures which provides a base to implement future algorithmic improvements and improved thermodynamic model in GTfold. GTfold is written in C/C++ and freely available as open source from our website.

Degree

thesis:*
Department dc:contributor.department
Computing
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mathuriya, Amrita
Advisors dc:contributor.advisor
  • Bader, David A.
  • Heitsch, Christine E.
Committee members dc:contributor.committeemember
  • Bolter, Jay D.
  • Grinter, Rebecca
  • Edwards, W. Keith
  • Kellogg, Wendy A.

Subjects

dc:subject × 8

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/28195

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mathuriya, Amrita. Prediction of secondary structures for large RNA molecules. Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/28195