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

Sato K, Kato Y, Hamada M, Akutsu T, Asai K - Bioinformatics (2011)

Bottom Line: Pseudoknots found in secondary structures of a number of functional RNAs play various roles in biological processes.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.

View Article: PubMed Central - PubMed

Affiliation: Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan. satoken@k.u-tokyo.ac.jp

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.

Show MeSH
An illustration of the decomposition of a pseudoknotted secondary structure y∈𝒮(x) into pseudoknot-free substructures (y(1),y(2),y(3)).
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3117384&req=5

Figure 2: An illustration of the decomposition of a pseudoknotted secondary structure y∈𝒮(x) into pseudoknot-free substructures (y(1),y(2),y(3)).

Mentions: We assume that a secondary structure y∈𝒮(x) can be decomposed into a set of pseudoknot-free substructures (y(1),y(2),…,y(m)) that satisfies the following conditions: (i) y∈𝒮(x) should be decomposed into a mutually-exclusive set, that is, for all 1≤i<j≤/x/, ∑1≤p≤my(p)ij≤1; and (ii) every base pair in y(p) should be pseudoknotted to at least one base pair in y(q) for ∀q<p. Each pseudoknot-free substructure y(p) is said to belong to the level p (see Fig. 2). For any RNA secondary structure y∈𝒮(x), there exists a positive integer m such that y can be decomposed into m pseudoknot-free substructures [see Supplementary Section S6 and Jiang et al. (2010) for further details]. From this viewpoint, we can say that the above decomposition enables our method to model arbitrary pseudoknots.Fig. 2.


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

Sato K, Kato Y, Hamada M, Akutsu T, Asai K - Bioinformatics (2011)

An illustration of the decomposition of a pseudoknotted secondary structure y∈𝒮(x) into pseudoknot-free substructures (y(1),y(2),y(3)).
© Copyright Policy - creative-commons
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3117384&req=5

Figure 2: An illustration of the decomposition of a pseudoknotted secondary structure y∈𝒮(x) into pseudoknot-free substructures (y(1),y(2),y(3)).
Mentions: We assume that a secondary structure y∈𝒮(x) can be decomposed into a set of pseudoknot-free substructures (y(1),y(2),…,y(m)) that satisfies the following conditions: (i) y∈𝒮(x) should be decomposed into a mutually-exclusive set, that is, for all 1≤i<j≤/x/, ∑1≤p≤my(p)ij≤1; and (ii) every base pair in y(p) should be pseudoknotted to at least one base pair in y(q) for ∀q<p. Each pseudoknot-free substructure y(p) is said to belong to the level p (see Fig. 2). For any RNA secondary structure y∈𝒮(x), there exists a positive integer m such that y can be decomposed into m pseudoknot-free substructures [see Supplementary Section S6 and Jiang et al. (2010) for further details]. From this viewpoint, we can say that the above decomposition enables our method to model arbitrary pseudoknots.Fig. 2.

Bottom Line: Pseudoknots found in secondary structures of a number of functional RNAs play various roles in biological processes.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.

View Article: PubMed Central - PubMed

Affiliation: Graduate School of Frontier Sciences, University of Tokyo, 5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan. satoken@k.u-tokyo.ac.jp

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.

Show MeSH