含假结的RNA折叠结构预测算法及复杂性研究

The project aims at the special subject of algorithm and the computational complexity for RNA folding structure prediction including pseudoknots. Based on RNA folding structure model, pseudoknotted model,Probabilistically Checkable Proof,the theory and method of the approximation algorithm, and theirs computational complexity,it is the important method for predicting RNA pseudoknotted structure which is NP-hard problem in theory, the method is nichetargeting and essential. The research content of the project comprises RNA structure modeling, pseudoknots structure modeling,RNA stem modeling,the theory and technology of approximation algorithms,randomized algorithms,parameter optimal,combinatoral optimization. the approximation algorithms is a kind of essential method for solving NP-hard problem,the technical route of the suject is for calculating possible RNA pseudoknotted structures which are folded by base pairings, through the theory and technique of approximation algorithm, randomized algorithm,analyze the computational complexity, and solve the puzzle of higher time complexity, space complexity and lower predicting accuracy by dynamic programing algorithms.The research goal is to design the rapid and effective approximation algorithms for NP-hard problem of RNA pseudoknotted structure prediction, and break through the specific research method of limit pseudoknotted types. The research will enrich the theory and methods of approximation algorithm for RNA pseudoknotted structure prediction, and effectively solve some important frontier problems of RNA pseudoknotted structure prediction.

本项目针对含假结的RNA折叠结构预测算法及复杂性专题开展研究。基于RNA折叠结构模型、假结模型、PCP、近似算法及其计算复杂性理论和方法，是对RNA假结结构预测这一理论上是NP困难问题，具有针对性和本质性研究的重要手段。研究内容主要包括RNA结构建模、假结结构建模、茎环结构建模、近似算法、随机算法、参数优化理论、组合优化理论和技术等。针对近似算法是处理NP困难问题的一种本质方法，课题采取的技术路线包括通过近似算法、随机算法理论与技术来计算RNA碱基序列折叠配对可能产生的RNA假结结构，分析计算复杂性，解决采用动态规划算法时间复杂度和空间复杂度高而预测准确性不高的困惑。研究目标是针对若干NP困难RNA假结结构预测问题，设计快速有效的近似算法，突破过去对假结类型限制而采用的特定研究设计方法。项目研究将丰富RNA假结结构预测近似算法理论和方法，有效解决RNA假结结构预测算法及计算复杂性前沿问题。

1、项目背景：随着21世纪初人类基因组计划（HGP）的完成,人类进入后基因时代，HGP的成功极大促进了生物信息学和计算生物学学科的发展。RNA 在遗传信息从DNA 表达为蛋白质过程中起转录作用，RNA 结构预测，特别是含假接的RNA折叠结构预测研究是当今学术界研究热点。预测中也存在准确度不高，特异性和敏感性仍需改进，预测算法时空复杂度不理想等问题。2、主要研究内容：包含假结的RNA结构预测问题被证明是NP 完全问题，主要包括RNA结构建模、假结结构建模、茎环结构建模、近似算法、随机算法、参数优化理论、组合优化理论和技术等。针对近似算法是处理NP困难问题的一种本质方法，课题采取的技术路线包括通过近似算法、随机算法理论与技术来计算RNA碱基序列折叠配对可能产生的RNA假结结构，分析计算复杂性，解决采用动态规划算法时间复杂度和空间复杂度高而预测准确性不高的困惑。3、重要结果、关键数据：（1）建立了RNA假接模型、茎环模型、能量模型，设计了包含任意假结的RNA 结构预测计算最大堆叠数问题的多项式时间近似算法.（2）利用随机算法和PCP理论与技术，分析了含交叉快的计算最大堆叠数问题的计算复杂性和不可近似性（3）对RNA假结结构预测问题中的限制性计算堆叠数和堆叠基对数问题，设计了精确求解的确定型算法，分析了该类问题精确求解的时间复杂性和空间复杂性上界，提高了预测的准确度和精确度。（4）通过典型的RNA数据库实验，提高了RNA结构预测算法的效率，验证了计算最大堆叠数算法，堆叠基对数的算法和交叉快算法的有效性，提高预测算法的特异性、敏感性和准确度。4、科学意义：项目研究可促进RNA 结构预测理论在计算实践中，特别是在生物制药，疫苗研发及健康医学行业的应用。在获知生物分子的生物学功能（如2020年在全球肆虐的新型冠状病毒就是RNA病毒），为寻找非编码RNA 基因，也为了解密RNA病毒机理和靶向核糖核酸药物研制，揭开RNA 编码秘密，探索生命起源、进化和人类健康防护具有重要意义。