Aarhus University Seal / Aarhus Universitets segl

Topology and prediction of RNA pseudoknots

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Christian Reidys, Nankai University, China
  • Fenix Huang, Nankai University, China
  • Jørgen Ellegaard Andersen, Denmark
  • Robert Penner, Denmark
  • Peter Stadler, Leipzig University, Germany
  • Markus Nebel, University of Kaiserslautern, Germany
Motivation: Several dynamic programming algorithms for predicting RNA structures with pseudoknots have been proposed that differ dramatically from one another in the classes of structures considered.

Results: Here, we use the natural topological classification of RNA structures in terms of irreducible components that are embeddable in the surfaces of fixed genus. We add to the conventional secondary structures four building blocks of genus one in order to construct certain structures of arbitrarily high genus. A corresponding unambiguous multiple context-free grammar provides an efficient dynamic programming approach for energy minimization, partition function and stochastic sampling. It admits a topology-dependent parametrization of pseudoknot penalties that increases the sensitivity and positive predictive value of predicted base pairs by 10–20% compared with earlier approaches. More general models based on building blocks of higher genus are also discussed.
Original languageEnglish
JournalBioinformatics
Volume27
Issue8
Pages (from-to)1076-1085
Number of pages10
ISSN1367-4803
DOIs
Publication statusPublished - 2011

See relations at Aarhus University Citationformats

ID: 32796749