Vol. 20 no. 2 2004, pages 186-190
Bioinformatics © Oxford University Press 2004; all rights reserved.
Prediction of locally stable RNA secondary structures for genome-wide surveys
1 Institut für Theoretische Chemie und Molekulare Strukturbiologie, Universität Wien, Währingerstraße 17, Vienna, A-1090, Austria, 2 Bioinformatik, Institut für Informatik, Universität Leipzig, Leipzig, D-04103, Germany and 3 The Santa Fe Institute, Santa Fe, New Mexico, USA
Received on April 10, 2003
; revised on July 1, 2003
; accepted on July 11, 2003
Motivation: Recently novel classes of functional RNAs, most prominently the miRNAs have been discovered, strongly suggesting that further types of functional RNAs are still hidden in the recently completed genomic DNA sequences. Only few techniques are known, however, to survey genomes for such RNA genes. When sufficiently similar sequences are not available for comparative approaches the only known remedy is to search directly for structural features.
Results: We present here efficient algorithms for computing locally stable RNA structures at genome-wide scales. Both the minimum energy structure and the complete matrix of base pairing probabilities can be computed in 
(N x L2) time and (N + L2) memory in terms of the length N of the genome and the size L of the largest secondary structure motifs of interest. In practice, the 100 Mb of the complete genome of Caenorhabditis elegans can be folded within about half a day on a modern PC with a search depth of L = 100. This is sufficient example for a survey for miRNAs.
Availability: The software described in this contribution will be available for download at http://www.tbi.univie.ac.at/~ivo/RNA/ as part of the Vienna RNA Package.
Contact: ivo{at}tbi.univie.ac.at
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  H. Kiryu, T. Kin, and K. Asai Rfold: an exact algorithm for computing local base pairing probabilities Bioinformatics, February 1, 2008; 24(3): 367 - 373. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 I. M. Meyer A practical guide to the art of RNA gene prediction Brief Bioinform, November 1, 2007; 8(6): 396 - 414. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Kiryu, T. Kin, and K. Asai Robust prediction of consensus secondary structures using averaged base pairing probability matrices Bioinformatics, February 15, 2007; 23(4): 434 - 441. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. H. Bernhart, I. L. Hofacker, and P. F. Stadler Local RNA base pairing probabilities in large sequences Bioinformatics, March 1, 2006; 22(5): 614 - 615. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Clote RNALOSS: a web server for RNA locally optimal secondary structures Nucleic Acids Res., July 1, 2005; 33(suppl_2): W600 - W604. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. CLOTE, F. FERRE, E. KRANAKIS, and D. KRIZANC Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency RNA, May 1, 2005; 11(5): 578 - 591. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. H. Havgaard, R. B. Lyngso, G. D. Stormo, and J. Gorodkin Pairwise local structural alignment of RNA sequences with sequence similarity less than 40% Bioinformatics, May 1, 2005; 21(9): 1815 - 1824. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
P. P. Gardner, A. Wilm, and S. Washietl A benchmark of multiple sequence alignment programs upon structural RNAs Nucleic Acids Res., April 28, 2005; 33(8): 2433 - 2439. [Abstract] [Full Text] [PDF]
|
|