Bioinformatics, Vol 15, 440-445, Copyright © 1999 by Oxford University Press
RB Lyngso, M Zuker and CN Pedersen
MOTIVATION: Though not as abundant in known biological processes as
proteins, RNA molecules serve as more than mere intermediaries between DNA
and proteins. Research in the last 15 years demonstrates that RNA molecules
serve in many roles, including catalysis. Furthermore, RNA secondary
structure prediction based on free energy rules for stacking and loop
formation remains one of the few major breakthroughs in the field of
structure prediction, as minimum free energy structures and related
quantities can be computed with full mathematical rigor. However, with the
current energy parameters, the algorithms used hitherto suffer the
disadvantage of either employing heuristics that risk (though highly
unlikely) missing the optimal structure or becoming prohibitively time
consuming for moderate to large sequences. RESULTS: We present a new method
to evaluate internal loops utilizing currently used energy rules. This
method reduces the time complexity of this part of the structure prediction
from O(n4) to O(n3), thus reducing the overall complexity to O(n3). Even
when the size of evaluated internal loops is bounded by k (a commonly used
heuristic), the method presented has a competitive edge by reducing the
time complexity of internal loop evaluation from O(k2n2) to O(kn2). The
method also applies to the calculation of the equilibrium partition
function. AVAILABILITY: Source code for an RNA secondary structure
prediction program implementing this method is available at
ftp://www.ibc.wustl.edu/pub/zuker/zuker .tar.Z
ARTICLES
Fast evaluation of internal loops in RNA secondary structure prediction
Department of Computer Science, University of Aarhus, DK 8000 Arhus, Denmark. rlyngsoe@daimi.au.dk
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  Z. J. Lu, D. H. Turner, and D. H. Mathews A set of nearest neighbor parameters for predicting the enthalpy change of RNA secondary structure formation Nucleic Acids Res., October 18, 2006; 34(17): 4912 - 4924. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Y. Ogurtsov, S. A. Shabalina, A. S. Kondrashov, and M. A. Roytberg Analysis of internal loops within the RNA secondary structure in almost quadratic time Bioinformatics, June 1, 2006; 22(11): 1317 - 1324. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Li, Z. He, and J. Zhou Selection of optimal oligonucleotide probes for microarrays using multiple criteria, global alignment and parameter estimation Nucleic Acids Res., October 24, 2005; 33(19): 6114 - 6123. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Z. He, L. Wu, X. Li, M. W. Fields, and J. Zhou Empirical Establishment of Oligonucleotide Probe Design Criteria Appl. Envir. Microbiol., July 1, 2005; 71(7): 3753 - 3760. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
F. Tanaka, A. Kameda, M. Yamamoto, and A. Ohuchi Design of nucleic acid sequences for DNA computing based on a thermodynamic approach Nucleic Acids Res., February 8, 2005; 33(3): 903 - 911. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. O. Hodas and D. P. Aalberts Efficient computation of optimal oligo-RNA binding Nucleic Acids Res., December 17, 2004; 32(22): 6636 - 6642. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. H. MATHEWS Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization RNA, August 1, 2004; 10(8): 1178 - 1190. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. Pavesi, G. Mauri, M. Stefani, and G. Pesole RNAProfile: an algorithm for finding conserved secondary structure motifs in unaligned RNA sequences Nucleic Acids Res., June 15, 2004; 32(10): 3258 - 3269. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. A. Rodionov, A. G. Vitreschak, A. A. Mironov, and M. S. Gelfand Regulation of lysine biosynthesis and transport genes in bacteria: yet another RNA riboswitch? Nucleic Acids Res., December 1, 2003; 31(23): 6748 - 6757. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. G. VITRESCHAK, D. A. RODIONOV, A. A. MIRONOV, and M. S. GELFAND Regulation of the vitamin B12 metabolism and transport in bacteria by a conserved RNA structural element RNA, September 1, 2003; 9(9): 1084 - 1097. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. A. Rodionov, A. G. Vitreschak, A. A. Mironov, and M. S. Gelfand Comparative Genomics of Thiamin Biosynthesis in Procaryotes. NEW GENES AND REGULATORY MECHANISMS J. Biol. Chem., December 6, 2002; 277(50): 48949 - 48959. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Garvis, J.-M. Mei, J. Ruiz-Albert, and D. W. Holden Staphylococcus aureus svrA: a gene required for virulence and expression of the agr locus Microbiology, October 1, 2002; 148(10): 3235 - 3243. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Schuster, C. Isel, I. Imbert, C. Ehresmann, R. Marquet, and M. P. Kieny Secondary Structure of the 3' Terminus of Hepatitis C Virus Minus-Strand RNA J. Virol., July 17, 2002; 76(16): 8058 - 8068. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. G. Vitreschak, D. A. Rodionov, A. A. Mironov, and M. S. Gelfand Regulation of riboflavin biosynthesis and transport genes in bacteria by transcriptional and translational attenuation Nucleic Acids Res., July 15, 2002; 30(14): 3141 - 3151. [Abstract] [Full Text] [PDF]
|
|