吴宏杰，汤 烨，陆卫忠，崔志明，2，付保川，GAO Zhen，3(苏州科技大学电子与信息工程学院，江苏苏州25009)

2(苏州大学智能信息处理及应用研究所，江苏苏州215006)

3(School of Engineering Technology McMaster University，Hamilton Ontario Canada 45011)

E-mail:luwz@mail.usts.edu.cn

1 引言

RNA(核糖核苷酸)是遗传信息的关键载体，其二维结构与基因的成熟、调节和功能密切相关［1］.研究RNA功能与结构的关系，确定RNA折叠的形式和频率对于揭示RNA分子在生命过程中的作用具有重要意义［2，3］RNA分子的二级结构描述了碱基之间的相互作用关系.确定RNA的二级结构不仅是RNA分子从一级结构到三级结构的必经之路，可以有效缩小RNA三级结构的解空间，降低搜索复杂度;而且二级结构也是RNA功能推断的重要依据.

从计算机角度，将长度为n的RNA碱基序列视为字符序列.序列中的每个碱基用i(0≤i≤n－1)作为下标，二级结构中的两个相互作用的碱基称为碱基对(i，j)［5］.我们把 RNA的碱基序列称为一级结构，把序列中的碱基对信息称为二级结构.从RNA一级结构推断其相应二级结构的过程称为二级结构预测.确定RNA的二级结构后，该RNA在二维平面中的实际排列图形也就随之确定.

假结是指序列中存在交叉的碱基对(i，j)和(k，l)且i＜k＜j＜l，它是RNA二级结构的一种子结构，在生命科学邻域中具有重要意义［4］.不带假结的RNA二级结构预测问题，已被 Zuker［5］和 Mathews［6，7］的 动 态 规 划 算 法 及 其 改 进 算 法mfold［8］，GTfold［9］等充分研究，其时间复杂度是 O(n3)，空间复杂度是O(n2).带假结的RNA二级结构预测问题是一个NP完全的优化问题［10］.依据组合数学方法，对于长度为n的RNA序列可以折叠出1.8n种可能的RNA二级结构，随着序列长……