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

Abstract

Motivation: 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.

Results: 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.

Availability: 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/.

Contact: satoken@k.u-tokyo.ac.jp; ykato@is.naist.jp

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

A typical H-type pseudoknot. (a) A pseudoknot represented by three-loop nomenclature. Note that Loop 2 typically has zero or one base (Liu et al., 2010). (b) An arc representation of the pseudoknot.

Fig. 2.

An illustration of the decomposition of a pseudoknotted secondary structure y∈𝒮(x) into pseudoknot-free substructures (y⁽¹⁾,y⁽²⁾,y⁽³⁾).

Fig. 3.

An illustration of the constraints of the IP formulation. The diagrams (a) and (b) correspond to the constraints (5) and (6), respectively. Note that at most one variable shown by a broken curved line can take a value 1. The diagram (c) corresponds to the constraint (7).

Fig. 4.

A schematic diagram of the iterative refinement algorithm for the base-pairing probability matrix. A constraint on secondary structure for each level is denoted by a variant of the dot-parenthesis format: a matching parenthesis ‘()’ denotes an allowed base pair, a character ‘x’ indicates an unpaired base, and a dot ‘.’ is used for an unconstrained base.

Fig. 5.

The PPV–Sensitivity plots of the experiment on the RS-pk388 dataset.

Fig. 6.

The PPV–Sensitivity plots of the experiment on the pk168 dataset.

Fig. 7.

The PPV–Sensitivity plots of the experiment on the Rfam-PK dataset. (a) The results for reference alignments. (b) The results for sequence-based alignments produced by Clustal W.