Bioinformatics Advance Access originally published online on February 12, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics 20(10) © Oxford University Press 2004; all rights reserved.
A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences
Department of Genetics, Washington University, School of Medicine, St. Louis, MO 63110, USA
Received on September 9, 2003; revised on December 30, 2003; accepted on December 31, 2003
Advance Access Publication February 12, 2004
Motivation: RNA structure motifs contained in mRNAs have been found to play important roles in regulating gene expression. However, identification of novel RNA regulatory motifs using computational methods has not been widely explored. Effective tools for predicting novel RNA regulatory motifs based on genomic sequences are needed.
Results: We present a new method for predicting common RNA secondary structure motifs in a set of functionally or evolutionarily related RNA sequences. This method is based on comparison of stems (palindromic helices) between sequences and is implemented by applying graph-theoretical approaches. It first finds all possible stable stems in each sequence and compares stems pairwise between sequences by some defined features to find stems conserved across any two sequences. Then by applying a maximum clique finding algorithm, it finds all significant stems conserved across at least k sequences. Finally, it assembles in topological order all possible compatible conserved stems shared by at least k sequences and reports a number of the best assembled stem sets as the best candidate common structure motifs. This method does not require prior structural alignment of the sequences and is able to detect pseudoknot structures. We have tested this approach on some RNA sequences with known secondary structures, in which it is capable of detecting the real structures completely or partially correctly and outperforms other existing programs for similar purposes.
Availability: The algorithm has been implemented in C++ in a program called comRNA, which is available at http://ural.wustl.edu/softwares.html
Contact: stormo{at}genetics.wustl.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. Popenda, M. Blazewicz, M. Szachniuk, and R. W. Adamiak RNA FRABASE version 1.0: an engine with a database to search for the three-dimensional fragments within RNA structures Nucleic Acids Res., January 11, 2008; 36(suppl_1): D386 - D391. [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]
|
|
|
|
 |
|
 X. Xu, Y. Ji, and G. D. Stormo RNA Sampler: a new sampling based algorithm for common RNA secondary structure prediction and structural alignment Bioinformatics, August 1, 2007; 23(15): 1883 - 1891. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. Hamada, K. Tsuda, T. Kudo, T. Kin, and K. Asai Mining frequent stem patterns from unaligned RNA sequences Bioinformatics, October 15, 2006; 22(20): 2480 - 2487. [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]
|
|
|
|
|
|
Y. Tabei, K. Tsuda, T. Kin, and K. Asai SCARNA: fast and accurate structural alignment of RNA sequences by matching fixed-length stem fragments Bioinformatics, July 15, 2006; 22(14): 1723 - 1729. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H.-Y. Huang, C.-H. Chien, K.-H. Jen, and H.-D. Huang RegRNA: an integrated web server for identifying regulatory RNA motifs and elements. Nucleic Acids Res., July 1, 2006; 34(Web Server issue): W429 - W434. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Z. Yao, Z. Weinberg, and W. L. Ruzzo CMfinder--a covariance model based RNA motif finding algorithm Bioinformatics, February 15, 2006; 22(4): 445 - 452. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. Wang and G. D. Stormo Identifying the conserved network of cis-regulatory sites of a eukaryotic genome PNAS, November 29, 2005; 102(48): 17400 - 17405. [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]
|
|
|
|
 |
|
 K. Tan, L. A. McCue, and G. D. Stormo Making connections between novel transcription factors and their DNA motifs Genome Res., February 1, 2005; 15(2): 312 - 320. [Abstract] [Full Text] [PDF]
|
|