Prediction of RNA secondary structure with pseudoknots using integer programming.
Prediction of RNA secondary structure with pseudoknots using integer programming.
复制标题
DOI：
10.1186/1471-2105-10-s1-s38
复制
发表时间：
2009-01-30
影响因子：
3
通讯作者：
Akutsu T
中科院分区：
文献类型：
--
作者：
Poolsap U;Kato Y;Akutsu T
RNA二级结构预测是生物信息学中的一个重要研究课题，目前已经提出了多种计算方法。假结是存在于多种RNA中的典型亚结构之一，在某些生物学过程中起着重要作用。具有伪结的RNA二级结构的预测仍然具有挑战性，因为当考虑任意伪结时，该问题是NP-难的。提出了一种基于整数规划的带伪结点的RNA二级结构预测方法。在我们的公式中，我们的目标是最小化目标函数的值，该目标函数反映了输入RNA序列的折叠结构的自由能。我们专注于一个实用的类的伪结适当地设置约束。一组真实的RNA序列的实验结果表明，我们提出的方法优于现有的几种方法的灵敏度。此外，对于一组小长度的序列，我们的方法在灵敏度和特异性方面都取得了良好的性能。我们的基于整数规划的RNA结构预测方法是灵活和可扩展的。
RNA secondary structure prediction is one major task in bioinformatics, and various computational methods have been proposed so far. Pseudoknot is one of the typical substructures appearing in several RNAs, and plays an important role in some biological processes. Prediction of RNA secondary structure with pseudoknots is still challenging since the problem is NP-hard when arbitrary pseudoknots are taken into consideration. We introduce a new method of predicting RNA secondary structure with pseudoknots based on integer programming. In our formulation, we aim at minimizing the value of the objective function that reflects free energy of a folding structure of an input RNA sequence. We focus on a practical class of pseudoknots by setting constraints appropriately. Experimental results for a set of real RNA sequences show that our proposed method outperforms several existing methods in sensitivity. Furthermore, for a set of sequences of small length, our approach achieved good performance in both sensitivity and specificity. Our integer programming-based approach for RNA structure prediction is flexible and extensible.