In:
Bioinformatics, Oxford University Press (OUP), Vol. 22, No. 11 ( 2006-06-01), p. 1317-1324
Kurzfassung:
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(L3), L is the length of the RNA. Results: We propose a new algorithm for evaluating internal loops, its run-time is O(M*log2L), M & lt;L2 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*log2L). Availability: Executables of Afold software tool, precompiled for Linux and Windows, are available at . Contact: MRoytberg@impb.psn.ru Supplementary information:
Materialart:
Online-Ressource
ISSN:
1367-4811
,
1367-4803
DOI:
10.1093/bioinformatics/btl083
Sprache:
Englisch
Verlag:
Oxford University Press (OUP)
Publikationsdatum:
2006
ZDB Id:
1468345-3
SSG:
12