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

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

作　　者：李恒武[1,2] 朱大铭[1] 纪秀花[3] 

机构地区：[1]山东大学计算机学院 [2]山东经济学院计算机学院,山东济南250014 [3]山东经济学院计算机学院

出　　处：《计算机工程与科学》2006年第7期82-84,94,共4页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60273032)

摘　　要：本文提出了一个预测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.

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

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