Title | ||
---|---|---|
Analysis of internal loops within the RNA secondary structure in almost quadratic time |
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(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), ML2 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 ftp://ftp.ncbi.nlm.nih.gov/pub/ogurtsov/Afold. Contact: MRoytberg@impb.psn.ru Supplementary information: ftp://ftp.ncbi.nlm.nih.gov/pub/ogurtsov/Afold |
Year | DOI | Venue |
---|---|---|
2006 | 10.1093/bioinformatics/btl083 | Bioinformatics |
Keywords | Field | DocType |
bioinformatics,rna secondary structure,prediction,nucleotides,evaluation,secondary structure,loop group,rna | Data mining,Discrete mathematics,RNA,Computer science,Algorithm,Pairing,Software,Computer program,Loop group,Time complexity,Protein secondary structure,Nucleic acid secondary structure | Journal |
Volume | Issue | ISSN |
22 | 11 | 1367-4803 |
Citations | PageRank | References |
4 | 0.52 | 8 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Aleksey Y. Ogurtsov | 1 | 41 | 4.42 |
S A Shabalina | 2 | 42 | 5.55 |
A S Kondrashov | 3 | 13 | 3.32 |
Mikhail A. Roytberg | 4 | 114 | 54.66 |