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

Abstract:

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 pseudokn ot. 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 demonstra ate that the proposed algorithm is effective.

Key words: RNA secondary structure, dynamic programming, thermodynamics