Abstract: On the basis of dynamic weighted matching algorithm, this paper introduced an RNA secondary structure prediction algorithm based on fast dynamic weighted matching. In order to reduce time complicated degree and to improve the ability of pseudoknot prediction, we employed fast searching of max dynamic weight stem algorithm and expanded searching area of pseudoknot respectively. As a result, compared with dynamic weighted matching algorithm, the fast dynamic weighted matching algorithm not only has better time complicated degree which is O(n3), but also can predict more possibly existing pseudoknots.

Key words: RNA, pseudoknot, secondary structure, dynamic weight

摘要： 在动态权重匹配算法的基础上提出了基于快速动态权重匹配的RNA二级结构预测算法。通过引入最大动态权重茎区搜索算法降低时间复杂度和扩大搜索假结的区域提高预测假结的能力，使得快速动态权重匹配算法与动态权重匹配算法相比，不仅具有O(n3)的更加理想的时间复杂度，而且还能预测更多可能存在的假结。

关键词: RNA, 假结, 二级结构, 动态权重