IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming.
IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming.
复制标题
DOI：
10.1093/bioinformatics/btr215
复制
发表时间：
2011-07-01
期刊：
影响因子：
--
通讯作者：
Asai K
中科院分区：
文献类型：
--
作者：
Sato K;Kato Y;Hamada M;Akutsu T;Asai K
动机：在许多功能性RNA的二级结构中发现的假结在生物过程中起着各种作用。最近用于预测RNA二级结构的方法涵盖了某些类的伪结结构，但其中只有少数在速度和准确性方面实现了令人满意的预测。结果如下：我们提出了IPknot，一种新的计算方法，用于预测RNA二级结构与伪结的基础上最大限度地提高预期的预测结构的准确性。IPknot将伪结结构分解为一组无伪结的子结构，并近似考虑伪结的碱基配对概率分布，从而能够对广泛的伪结进行建模，并且运行速度相当快。此外，我们提出了一种启发式算法，用于改进基配对概率，以提高IPknot的预测精度。采用带阈值截割的整数规划方法求解最大期望精度问题。我们还扩展了IPknot，使它可以预测的共识二级结构与伪结时，多序列比对。通过在各种数据集上的大量实验验证了IPknot，与几种竞争性预测方法相比，IPknot实现了更好的预测精度和更快的运行时间。可用性：IPknot的程序可在http://www.ncrna.org/software/ipknot/上获得。IPknot也可以作为Web服务器在http://rna.naist.jp/ipknot/上使用。联系方式：satoken@k.u-tokyo.ac.jp; ykato@is.naist.jp补充信息：补充数据可在生物信息学在线获得。
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.
登录
查看更多内容
影响因子：
14.9
作者：
Hamada M;Sato K;Asai K
通讯作者：
Asai K
影响因子：
1.8
作者：
HOFACKER, IL;FONTANA, W;SCHUSTER, P
通讯作者：
SCHUSTER, P
影响因子：
5.8
作者：
Andronescu, Mirela;Condon, Anne;Murphy, Kevin P.
通讯作者：
Murphy, Kevin P.
预测RNA伪折叠热力学。
影响因子：
14.9
作者：
Cao, Song;Chen, Shi-Jie
通讯作者：
Chen, Shi-Jie
影响因子：
3
作者：
Dirks, RM;Pierce, NA
通讯作者：
Pierce, NA