Download:
[PostScript] [PDF]

Titel:
Prediction of Locally Stable RNA Secondary Structures for Genome-Wide Surveys

Author(s):
Ivo L. Hofacker, Barbara Priwitzer, Peter F. Stadler

Appeared in:
Bioinformatics 20: 191-198 (2004)

Abstract:
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 O(N L²) time and O(N + L²) 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 100Mb 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 e.g. 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

Keywords:
RNomics, functional RNAs, RNA secondary structure, folding algorithms

Return to 2003 working papers list.
Last modified: 2004-05-05 14:31:48 ivo