计算最大堆迭的RNA二级结构预测算法  

The Predicting Algorithm of RNA Secondary Structure for Computing Maximum Stacking

作　　者：刘振栋[1] 李恒武[2] 朱大铭[1] 

机构地区：[1]山东大学计算机科学与技术学院,济南250100 [2]山东经济学院计算机科学与技术系,济南250014

出　　处：《南京大学学报（自然科学版）》2005年第5期532-537,共6页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(60273032)

摘　　要：RNA二级结构预测用于蛋白质功能分析,在生物信息学研究中具有重要意义.提出了一个时间复杂度为O(n2)的基于Greedy算法思想的算法.基于“堆迭结构相对稳定”的RNA分子结构特征,算法思想为计算具有最多堆迭的RNA二级结构.用VC++编程实现了该算法,采用PseudoBase的RNA分子片段进行了计算实验,结果表明该算法具有良好的准确度.该算法可预测RNA分子的嵌套二级结构和伪结点二级结构.The prediction of RNA secondary structure is used in the functional analysis of the protein. It has important significance in bioinformatics. The problem for predicting RNA secondary structure containing pseudoknots is NPcomplete. It is one of the two basic methods to predict RNA secondary structure by themodynamics minimal free energy method. With the number of new published sequences increasing by index, this method is applied more and more, and it has become the first method selected to predict RNA secondary structure. Mfold algorithm used widely can only compute nested RNA secondary structure that pseudoknots aren＇ t permitted in it. Most methods for RNA that are capable of folding pseudoknots adopt heuristic search procedures, but their results are not surely of optimal value. Rivas algorithm and LyngsФ algorithm are the best as we know to predict RNA secondary structure including pseudoknots. LyngsФ algorithm can only compute one planar pseudoknot, and its time complexity is O （ n^5 ） and its space complexity is O （ n^3 ）. In this paper, an algorithm based on Greedy with time complexity O（ n^2 ） is presented to predict the secondary structure of RNA sequence. Based on the principle that the stacking stems in RNA molcule.s are relatively more stable, the algorithm targets to compute the secondary structure with maximum stackings. We implement the algorithm in VC ＋ ＋ and use the RNA sub-sequence in the PseudoBase to computational experiment. The experiment results indicate that the algorithm has gcxxt accuracy of prediction. The algorithm can predict nested secondary structures and pseudoknoted secondary structures of RNA predict molecules.

关 键 词：RNA二级结构 伪结点 NPC 动态规划 热动力学 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]