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

被引：28

作者：

Ogurtsov, Aleksey Y.

Shabalina, Syetlana A.

Kondrashov, Alexey S.

Roytberg, Mikhail A. ^{[1
]}

机构：

[1] Russian Acad Sci, Inst Math Problems Biol, Pushchino 142290, Moscow Region, Russia

[2] Natl Lib Med, Natl Ctr Biotechnol Informat, NIH, Bethesda, MD 20894 USA

来源：

BIOINFORMATICS | 2006年 / 22卷 / 11期

基金：

俄罗斯基础研究基金会; 美国国家卫生研究院;

关键词：

D O I：

10.1093/bioinformatics/btl083

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

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).

引用

页码：1317 / 1324

页数：8

共 28 条

[1]

Aho A.V., 1974, The Design and Analysis of Computer Algorithms

[2] The efficacy of small interfering RNAs targeted to the type 1 insulin-like growth factor receptor (IGF1R) is influenced by secondary structure in the IGF1R transcript [J].