RNA二级结构预测算法的设计与实现

Design and Implementation of an Algorithm for the RNA Secondary Structure Prediction

本文提出了一个预测RNA二级结构的计算模型和动态规划算法。该算法采用子序列的组合策略和RNA二级结构的内在特性,计算多个平面伪结点和一个非平面伪结点结构。与Rivas算法相比,该算法减少了2n4的空间,并将时间复杂度由O(n6)降为O(n5)。实验结果验证了算法的有效性。

A computational model and dynamic programming algorithm is presented to predict the RNA secondary structure. A combinatorial strategy of subsequences and the intrinsic characteristics of RNA secondary structure are adopted to compute the structures of planar multi-pseudoknots and a non-planar pseudoknot. Compared with the Rivas algorithm, 2n^4 space is subtracted and the time complexity is reduced from O（n^6） to O（n^5 ）. The experiments demonstrate that the proposed algorithm is effective.