Home LiteratureArticle Details
PMID: 21685106 Published · ppublish English Journal Article Research Support, Non-U.S. Gov't

IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming.

Bioinformatics (Oxford, England) ·Vol. 27 ·No. 13 ·2011-07-01 ·Pages i85-93

Sato K, Kato Y, Hamada M, Akutsu T, Asai K

Abstract

Pseudoknots found in secondary structures of a number of functional RNAs play various roles in biological processes. Recent methods for predicting RNA secondary structures cover certain classes of pseudoknotted structures, but only a few of them achieve satisfying predictions in terms of both speed and accuracy. We propose IPknot, a novel computational method for predicting RNA secondary structures with pseudoknots based on maximizing expected accuracy of a predicted structure. IPknot decomposes a pseudoknotted structure into a set of pseudoknot-free substructures and approximates a base-pairing probability distribution that considers pseudoknots, leading to the capability of modeling a wide class of pseudoknots and running quite fast. In addition, we propose a heuristic algorithm for refining base-paring probabilities to improve the prediction accuracy of IPknot. The problem of maximizing expected accuracy is solved by using integer programming with threshold cut. We also extend IPknot so that it can predict the consensus secondary structure with pseudoknots when a multiple sequence alignment is given. IPknot is validated through extensive experiments on various datasets, showing that IPknot achieves better prediction accuracy and faster running time as compared with several competitive prediction methods. The program of IPknot is available at http://www.ncrna.org/software/ipknot/. IPknot is also available as a web server at http://rna.naist.jp/ipknot/. [email protected]; [email protected] Supplementary data are available at Bioinformatics online.

MeSH Terms
Algorithms Nucleic Acid Conformation RNA/chemistry Sequence Analysis, RNA Software
Chemicals
RNA
Authors & Affiliations
5 authors, click to expand affiliations / ORCID
Sato Kengo
Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan. [email protected]
Kato Yuki
Hamada Michiaki
Akutsu Tatsuya
Asai Kiyoshi
References (44)
44 references, click to expand
  1. An iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots.
    Bioinformatics. 2004 Jan 1;20(1):58-66 PMID: 14693809
  2. A max-margin model for efficient simultaneous alignment and folding of RNA sequences.
    Bioinformatics. 2008 Jul 1;24(13):i68-76 PMID: 18586747
  3. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure.
    J Mol Biol. 1999 May 21;288(5):911-40 PMID: 10329189
  4. PseudoBase: structural information on RNA pseudoknots.
    Nucleic Acids Res. 2001 Jan 1;29(1):194-5 PMID: 11125088
  5. CentroidAlign: fast and accurate aligner for structured RNAs by maximizing expected sum-of-pairs score.
    Bioinformatics. 2009 Dec 15;25(24):3236-43 PMID: 19808876
  6. Prediction of RNA secondary structure with pseudoknots using integer programming.
    BMC Bioinformatics. 2009 Jan 30;10 Suppl 1:S38 PMID: 19208139
  7. A partition function algorithm for nucleic acid secondary structure including pseudoknots.
    J Comput Chem. 2003 Oct;24(13):1664-77 PMID: 12926009
  8. Prediction of RNA secondary structure by maximizing pseudo-expected accuracy.
    BMC Bioinformatics. 2010 Nov 30;11:586 PMID: 21118522
  9. Improved free energy parameters for RNA pseudoknotted secondary structure prediction.
    RNA. 2010 Jan;16(1):26-42 PMID: 19933322
  10. Prediction of consensus RNA secondary structures including pseudoknots.
    IEEE/ACM Trans Comput Biol Bioinform. 2004 Apr-Jun;1(2):66-77 PMID: 17048382
  11. Rfam: Wikipedia, clans and the "decimal" release.
    Nucleic Acids Res. 2011 Jan;39(Database issue):D141-5 PMID: 21062808
  12. Efficient parameter estimation for RNA secondary structure prediction.
    Bioinformatics. 2007 Jul 1;23(13):i19-28 PMID: 17646296
  13. Computational approaches for RNA energy parameter estimation.
    RNA. 2010 Dec;16(12):2304-18 PMID: 20940338
  14. K-partite RNA secondary structures.
    J Comput Biol. 2010 Jul;17(7):915-25 PMID: 20632871
  15. Novel features in the tRNA-like world of plant viral RNAs.
    Cell Mol Life Sci. 2001 Oct;58(11):1547-61 PMID: 11706983
  16. RactIP: fast and accurate prediction of RNA-RNA interaction using integer programming.
    Bioinformatics. 2010 Sep 15;26(18):i460-6 PMID: 20823308
  17. Pseudoknots in RNA secondary structures: representation, enumeration, and prevalence.
    J Comput Biol. 2006 Jul-Aug;13(6):1197-213 PMID: 16901237
  18. ProbCons: Probabilistic consistency-based multiple sequence alignment.
    Genome Res. 2005 Feb;15(2):330-40 PMID: 15687296
  19. Viral RNA pseudoknots: versatile motifs in gene expression and replication.
    Nat Rev Microbiol. 2007 Aug;5(8):598-610 PMID: 17632571
  20. Vienna RNA secondary structure server.
    Nucleic Acids Res. 2003 Jul 1;31(13):3429-31 PMID: 12824340
  21. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information.
    Nucleic Acids Res. 1981 Jan 10;9(1):133-48 PMID: 6163133
  22. Pseudoknots: RNA structures with diverse functions.
    PLoS Biol. 2005 Jun;3(6):e213 PMID: 15941360
  23. Mfold web server for nucleic acid folding and hybridization prediction.
    Nucleic Acids Res. 2003 Jul 1;31(13):3406-15 PMID: 12824337
  24. ProbKnot: fast prediction of RNA secondary structure including pseudoknots.
    RNA. 2010 Oct;16(10):1870-80 PMID: 20699301
  25. Non-coding RNA genes and the modern RNA world.
    Nat Rev Genet. 2001 Dec;2(12):919-29 PMID: 11733745
  26. High sensitivity RNA pseudoknot prediction.
    Nucleic Acids Res. 2007;35(2):656-63 PMID: 17179177
  27. Centroid estimation in discrete high-dimensional spaces with applications in biology.
    Proc Natl Acad Sci U S A. 2008 Mar 4;105(9):3209-14 PMID: 18305160
  28. RNA pseudoknot prediction in energy-based models.
    J Comput Biol. 2000;7(3-4):409-27 PMID: 11108471
  29. RNA STRAND: the RNA secondary structure and statistical analysis database.
    BMC Bioinformatics. 2008 Aug 13;9:340 PMID: 18700982
  30. RNAalifold: improved consensus structure prediction for RNA alignments.
    BMC Bioinformatics. 2008 Nov 11;9:474 PMID: 19014431
  31. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics.
    BMC Bioinformatics. 2004 Aug 04;5:104 PMID: 15294028
  32. CONTRAfold: RNA secondary structure prediction without physics-based models.
    Bioinformatics. 2006 Jul 15;22(14):e90-8 PMID: 16873527
  33. A dynamic programming algorithm for RNA structure prediction including pseudoknots.
    J Mol Biol. 1999 Feb 5;285(5):2053-68 PMID: 9925784
  34. RNA pseudoknots: folding and finding.
    F1000 Biol Rep. 2010 Jan 27;2:8 PMID: 20495679
  35. Improving the accuracy of predicting secondary structure for aligned RNA sequences.
    Nucleic Acids Res. 2011 Jan;39(2):393-402 PMID: 20843778
  36. The equilibrium partition function and base pair binding probabilities for RNA secondary structure.
    Biopolymers. 1990 May-Jun;29(6-7):1105-19 PMID: 1695107
  37. An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots.
    J Comput Chem. 2004 Jul 30;25(10):1295-304 PMID: 15139042
  38. Predicting RNA pseudoknot folding thermodynamics.
    Nucleic Acids Res. 2006 May 18;34(9):2634-52 PMID: 16709732
  39. Prediction of RNA secondary structure using generalized centroid estimators.
    Bioinformatics. 2009 Feb 15;25(4):465-73 PMID: 19095700
  40. Secondary structure prediction for aligned RNA sequences.
    J Mol Biol. 2002 Jun 21;319(5):1059-66 PMID: 12079347
  41. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice.
    Nucleic Acids Res. 1994 Nov 11;22(22):4673-80 PMID: 7984417
  42. Pfold: RNA secondary structure prediction using stochastic context-free grammars.
    Nucleic Acids Res. 2003 Jul 1;31(13):3423-8 PMID: 12824339
  43. HotKnots: heuristic prediction of RNA secondary structures including pseudoknots.
    RNA. 2005 Oct;11(10):1494-504 PMID: 16199760
  44. FlexStem: improving predictions of RNA secondary structures with pseudoknots by reducing the search space.
    Bioinformatics. 2008 Sep 15;24(18):1994-2001 PMID: 18586700
Article Info
Journal
Bioinformatics (Oxford, England)
Abbr.
Bioinformatics
ISSN
1367-4811
DOI
10.1093/bioinformatics/btr215
Email
[email protected]
Published
2011-07-01
Pages
i85-93
Language
English
Region
England
NLM ID
9808944
PMCID
PMC3117384
Subset
IM
External Links
PubMed source DOI: 10.1093/bioinformatics/btr215 PMC Full Text View journal details
Analysis Services
Analysis Services

Contact

No. 2 Wenbo Road, Zhangqiu District, Jinan, Shandong

Qilu Normal University · Genelibs Bioinformatics Lab

750 Shunhua Rd, Jinan

2F, Bldg F, University Science Park

Tel: 0531-88819269

WeChat Official Account

Follow our WeChat subscription account for real-time updates and the latest in medical and biological research.


Business Email

E-mail: [email protected]

Copyright © 2026.Genelibs Jinan Honghui Biotechnology Co., Ltd. 鲁ICP备20007159号-2