Published online 15 June 2004
Nucleic Acids Research, 2004, Vol. 32, No. 10 3258-3269
© 2004 Nucleic Acids Research, Vol. 32 No. 10 © Oxford University Press 2004; all rights reserved
RNAProfile: an algorithm for finding conserved secondary structure motifs in unaligned RNA sequences
Department of Computer Science and Communication-(D.I.Co.), University of Milan, Via Comelico 39, 20135 Milan, Italy, 1 Department of Computer Science, Systems and Communication, University of Milano-Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milan, Italy and 2 Department of Biomolecular Science and Biotechnology, University of Milan, Via Celoria 26, 20133 Milan, Italy
* To whom correspondence should be addressed. Tel: +39 02 50314915; Fax: +39 02 50314912; Email: graziano.pesole{at}unimi.it
Received December 23, 2004; Revised April 5, 2004; Accepted May 21, 2004
The recent interest sparked due to the discovery of a variety of functions for non-coding RNA molecules has highlighted the need for suitable tools for the analysis and the comparison of RNA sequences. Many trans-acting non-coding RNA genes and cis-acting RNA regulatory elements present motifs, conserved both in structure and sequence, that can be hardly detected by primary sequence analysis alone. We present an algorithm that takes as input a set of unaligned RNA sequences expected to share a common motif, and outputs the regions that are most conserved throughout the sequences, according to a similarity measure that takes into account both the sequence of the regions and the secondary structure they can form according to base-pairing and thermodynamic rules. Only a single parameter is needed as input, which denotes the number of distinct hairpins the motif has to contain. No further constraints on the size, number and position of the single elements comprising the motif are required. The algorithm can be split into two parts: first, it extracts from each input sequence a set of candidate regions whose predicted optimal secondary structure contains the number of hairpins given as input. Then, the regions selected are compared with each other to find the groups of most similar ones, formed by a region taken from each sequence. To avoid exhaustive enumeration of the search space and to reduce the execution time, a greedy heuristic is introduced for this task. We present different experiments, which show that the algorithm is capable of characterizing and discovering known regulatory motifs in mRNA like the iron responsive element (IRE) and selenocysteine insertion sequence (SECIS) stem–loop structures. We also show how it can be applied to corrupted datasets in which a motif does not appear in all the input sequences, as well as to the discovery of more complex motifs in the non-coding RNA.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Hiller, R. Pudimat, A. Busch, and R. Backofen Using RNA secondary structures to guide sequence motif finding towards single-stranded regions Nucleic Acids Res., October 18, 2006; 34(17): e117 - e117. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. D. Baird, M. Turcotte, R. G. Korneluk, and M. Holcik Searching for IRES RNA, October 1, 2006; 12(10): 1755 - 1785. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. Pavesi, P. Mereghetti, F. Zambelli, M. Stefani, G. Mauri, and G. Pesole MoD Tools: regulatory motif discovery in nucleotide sequences from co-regulated or homologous genes. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W566 - W570. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 E. Borenstein and E. Ruppin Direct evolution of genetic robustness in microRNA PNAS, April 25, 2006; 103(17): 6593 - 6598. [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]
|
|