论文部分内容阅读
RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题,基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法.但RNA结构中假结的存在使MFE问题理论上成为一个NP-hard问题,即使采用动态规划等优化算法也会面临时间复杂度高的困难,同时研究还发现,由于受RNA折叠动力学机制以及环境因素的影响,真实的RNA二级结构往往并不处于自由能最小状态.根据RNA折叠的特点,提出了一种启发式搜索算法来预测带假结的RNA二级结构.该算法以RNA的茎为基本单元,采用启发式搜索策略在茎的组合空间中搜索自由