Analysis of internal loops within the RNA secondary structure in almost quadratic time.
BACKGROUND
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).
Ogurtsov
Aleksey Y
AY
National Center for Biotechnology Information, National Library of Medicine, National Institutes of Health, Bethesda, MD 20894, USA.
Shabalina
Svetlana A
SA
Kondrashov
Alexey S
AS
Roytberg
Mikhail A
MA
D000465:Algorithms; D001482:Base Composition; D019295:Computational Biology / Q000379:methods*; D009690:Nucleic Acid Conformation; D011381:Programming Languages; D012313:RNA / Q000737:chemistry*; D012984:Software; D013816:Thermodynamics
D012313:RNA