CAJ | 학술논문

RNA的二级结构预测是生物信息学中一个已经有30多年历史的经典问题,基于最小自由能模型(MFE)的优化算法是使用最为广泛的方法.但RNA结构中假结的存在使MFE问题理论上成为一个NP-bard问题,即使采用动态规划等优化算法也会面临时间复杂度高的困难,同时研究还发现,由于受RNA折叠动力学机制以及环境因素的影响,真实的RNA二级结构往往并不处于自由能最小状态.根据RNA折叠的特点,提出了一种启发式搜索算法来预测带假结的RNA二级结构.该算法以RNA的茎为基本单元,采用启发式搜索策略在茎的组合空间中搜索自由能最小并且出现频率最高的RNA二级结构,该算法不仅能显著降低搜索RNA二级结构的时间复杂度,还有助于弥补单纯依赖能量预测RNA二级结构的不足.在多种类型的RNA标准数据集上进行了检验,结果表明,该算法在预测的精度上优于目前国际上几个著名的RNA二级结构预测算法并且具有较高的运行效率.
RNA적이급결구예측시생물신식학중일개이경유30다년역사적경전문제,기우최소자유능모형(MFE)적우화산법시사용최위엄범적방법.단RNA결구중가결적존재사MFE문제이론상성위일개NP-bard문제,즉사채용동태규화등우화산법야회면림시간복잡도고적곤난,동시연구환발현,유우수RNA절첩동역학궤제이급배경인소적영향,진실적RNA이급결구왕왕병불처우자유능최소상태.근거RNA절첩적특점,제출료일충계발식수색산법래예측대가결적RNA이급결구.해산법이RNA적경위기본단원,채용계발식수색책략재경적조합공간중수색자유능최소병차출현빈솔최고적RNA이급결구,해산법불부능현저강저수색RNA이급결구적시간복잡도,환유조우미보단순의뢰능량예측RNA이급결구적불족.재다충류형적RNA표준수거집상진행료검험,결과표명,해산법재예측적정도상우우목전국제상궤개저명적RNA이급결구예측산법병차구유교고적운행효솔.