Bioinformatics Advance Access published online on June 27, 2008
Bioinformatics, doi:10.1093/bioinformatics/btn327
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
FlexStem: Improving Predictions of RNA Secondary Structures With Pseudoknots by Reducing the Search Space
1Key Lab of Intelligent Information Processing, Chinese Academy of Sciences
2Institute of Computing Technology, Chinese Academy of Sciences
3Insitute of Biophysics, Chinese Academy of Sciences
4Peking University
5Shanghai Key Lab of Intelligent Information Processing, Department of Computer Science and Engineering, Fudan University
6Graduate University of Chinese Academy of Sciences
*To whom correspondence should be addressed. Dr. Xiang Chen, E-mail: xchen{at}jdl.ac.cn
 |
Abstract |
|---|
Motivation: RNA secondary structures with pseudoknots are often predicted by minimizing free energy, which is proved to be NP-hard. Due to kinetic reasons the real RNA secondary structure often has local instead of global minimum free energy. This implies that we may improve the performance of RNA secondary structure prediction by taking kinetics into account and minimize free energy in a local area.
Results: we propose a novel algorithm named FlexStem to predict RNA secondary structures with pseudoknots. Still based on MFE criterion, FlexStem adopts comprehensive energy models that allow complex pseudoknots. Unlike classical thermo-dynamic methods, our approach aims to simulate the RNA folding process by successive addition of maximal stems, reducing the search space while maintaining or even improving the prediction accuracy. This reduced space is constructed by our maximal stem strategy and stem-adding rule induced from elaborate statistical experiments on real RNA secondary structures. The strategy and the rule also reflect the folding characteristic of RNA from a new angle and help compensate for the deficiency of merely relying on MFE in RNA structure prediction. We validate FlexStem by applying it to tRNAs, 5SrRNAs and a large number of pseudoknotted structures and compare it with the well-known algorithms such as RNAfold, PKNOTS, PknotsRG, HotKnots and ILM according to their overall sensitivities and specificities, as well as positive and negative controls on pseudoknots. The results show that FlexStem significantly increases the prediction accuracy through its local search strategy.
Contact: xchen{at}jdl.ac.cn
Availability: Software is available at http://pfind.ict.ac.cn/FlexStem/
Associate Editor: Prof. Ivo Hofacker
Received on March 14, 2008; revised on June 19, 2008; accepted on June 22, 2008
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  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]
|
|