Analysis of internal loops within the RNA secondary structure in almost quadratic time

Bioinformatics. 2006 Jun 1;22(11):1317-24. doi: 10.1093/bioinformatics/btl083. Epub 2006 Mar 16.

Abstract

Motivation: Evaluating all possible internal loops is one of the key steps in predicting the optimal secondary structure of an RNA molecule. The best algorithm available runs in time O(L(3)), L is the length of the RNA.

Results: We propose a new algorithm for evaluating internal loops, its run-time is O(M(*)log(2)L), M < L(2) is a number of possible nucleotide pairings. We created a software tool Afold which predicts the optimal secondary structure of RNA molecules of lengths up to 28 000 nt, using a computer with 2 Gb RAM. We also propose algorithms constructing sets of conditionally optimal multi-branch loop free (MLF) structures, e.g. the set that for every possible pairing (x, y) contains an optimal MLF structure in which nucleotides x and y form a pair. All the algorithms have run-time O(M(*)log(2)L).

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Base Composition
  • Computational Biology / methods*
  • Nucleic Acid Conformation*
  • Programming Languages
  • RNA / chemistry*
  • Software
  • Thermodynamics

Substances

  • RNA