Vol. 20 no. 1 2004, pages 58-66
Bioinformatics © Oxford University Press 2004; all rights reserved.
An Iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots
1 Department of Computer Science and 2 Department of Genetics, Washington University in St. Louis, St. Louis, MO 63130, USA
Received on March 16, 2003
; revised on June 20, 2003
; accepted on July 9, 2003
Motivation: Pseudoknots have generally been excluded from the prediction of RNA secondary structures due to its difficulty in modeling. Although, several dynamic programming algorithms exist for the prediction of pseudoknots using thermodynamic approaches, they are neither reliable nor efficient. On the other hand, comparative methods are more reliable, but are often done in an ad hoc manner and require expert intervention. Maximum weighted matching, an algorithm for pseudoknot prediction with comparative analysis, suffers from low-prediction accuracy in many cases.
Results: Here we present an algorithm, iterated loop matching, for reliably and efficiently predicting RNA secondary structures including pseudoknots. The method can utilize either thermodynamic or comparative information or both, thus is able to predict pseudoknots for both aligned and individual sequences. We have tested the algorithm on a number of RNA families. Using 8–12 homologous sequences, the algorithm correctly identifies more than 90% of base-pairs for short sequences and 80% overall. It correctly predicts nearly all pseudoknots and produces very few spurious base-pairs for sequences without pseudoknots. Comparisons show that our algorithm is both more sensitive and more specific than the maximum weighted matching method. In addition, our algorithm has high-prediction accuracy on individual sequences, comparable with the PKNOTS algorithm, while using much less computational resources.
Availability: The program has been implemented in ANSI C and is freely available for academic use at http://www.cse.wustl.edu/~zhang/projects/rna/ilm/
Supplementary information: http://www.cse.wustl.edu/~zhang/projects/rna/ilm/
Contact: jruan{at}cse.wustl.edu; zhang{at}cse.wustl.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. Sperschneider and A. Datta DotKnot: pseudoknot prediction using the probability dot plot under a refined energy model Nucleic Acids Res., January 31, 2010; (2010): gkq021v1 - gkq021. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Engelen and F. Tahi Tfold: efficient in silico prediction of non-coding RNA secondary structures Nucleic Acids Res., January 4, 2010; (2010) gkp1067v1. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 M. S. Andronescu, C. Pop, and A. E. Condon Improved free energy parameters for RNA pseudoknotted secondary structure prediction RNA, January 1, 2010; 16(1): 26 - 42. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Zhang, J. Dundas, M. Lin, R. Chen, W. Wang, and J. Liang Prediction of geometrically feasible three-dimensional structures of pseudoknotted RNA through free energy estimation RNA, December 1, 2009; 15(12): 2248 - 2263. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. H. Bernhart and I. L. Hofacker From consensus structure prediction to RNA gene finding Briefings in Functional Genomics, November 1, 2009; 8(6): 461 - 471. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Fan, P. B. Bitterman, and O. Larsson Regulatory element identification in subsets of transcripts: Comparison and integration of current computational methods RNA, August 1, 2009; 15(8): 1469 - 1482. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. J. Schroeder Advances in RNA Structure Prediction from Sequence: New Tools for Generating Hypotheses about Viral RNA Structure-Function Relationships J. Virol., July 1, 2009; 83(13): 6326 - 6334. [Full Text] [PDF]
|
|
|
|
|
|
S. Cao and S.-J. Chen Predicting structures and stabilities for H-type pseudoknots with interhelix loops RNA, April 1, 2009; 15(4): 696 - 706. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 X. Chen, S.-M. He, D. Bu, F. Zhang, Z. Wang, R. Chen, and W. Gao FlexStem: improving predictions of RNA secondary structures with pseudoknots by reducing the search space Bioinformatics, September 15, 2008; 24(18): 1994 - 2001. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. L. Cerrone-Szakal, D. M. Chadalavada, B. L. Golden, and P. C. Bevilacqua Mechanistic characterization of the HDV genomic ribozyme: The cleavage site base pair plays a structural role in facilitating catalysis RNA, September 1, 2008; 14(9): 1746 - 1760. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Sperschneider and A. Datta KnotSeeker: Heuristic pseudoknot detection in long RNA sequences RNA, April 1, 2008; 14(4): 630 - 640. [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]
|
|
|
|
|
|
C. U. T. Hellen and S. de Breyne A Distinct Group of Hepacivirus/Pestivirus-Like Internal Ribosomal Entry Sites in Members of Diverse Picornavirus Genera: Evidence for Modular Exchange of Functional Noncoding RNA Elements by Recombination J. Virol., June 1, 2007; 81(11): 5850 - 5863. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
X. Huang and H. Ali High sensitivity RNA pseudoknot prediction Nucleic Acids Res., January 28, 2007; 35(2): 656 - 663. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Lindgreen, P. P. Gardner, and A. Krogh Measuring covariation in RNA alignments: physical realism improves information measures Bioinformatics, December 15, 2006; 22(24): 2988 - 2995. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Voss Structural analysis of aligned RNAs Nucleic Acids Res., November 14, 2006; 34(19): 5471 - 5481. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. BINDEWALD and B. A. SHAPIRO RNA secondary structure prediction from sequence alignments using a network of k-nearest neighbor classifiers. RNA, March 1, 2006; 12(3): 342 - 352. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. REN, B. RASTEGARI, A. CONDON, and H. H. HOOS HotKnots: Heuristic prediction of RNA secondary structures including pseudoknots RNA, October 1, 2005; 11(10): 1494 - 1504. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C.-H. Huang, C. L. Lu, and H.-T. Chiu A heuristic approach for detecting RNA H-type pseudoknots Bioinformatics, September 1, 2005; 21(17): 3501 - 3508. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Y. DING, C. Y. CHAN, and C. E. LAWRENCE RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble RNA, August 1, 2005; 11(8): 1157 - 1166. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. Xayaphoummine, T. Bucher, and H. Isambert Kinefold web server for RNA/DNA folding path and structure prediction including pseudoknots and knots Nucleic Acids Res., July 1, 2005; 33(suppl_2): W605 - W610. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Matsui, K. Sato, and Y. Sakakibara Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures Bioinformatics, June 1, 2005; 21(11): 2611 - 2617. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. H. Mathews Predicting a set of minimal free energy RNA secondary structures common to two sequences Bioinformatics, May 15, 2005; 21(10): 2246 - 2253. [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]
|
|
|
|
|
|
J. Ruan, G. D. Stormo, and W. Zhang ILM: a web server for predicting RNA secondary structures with pseudoknots Nucleic Acids Res., July 1, 2004; 32(suppl_2): W146 - W149. [Abstract] [Full Text] [PDF]
|
|