Abstract: RNA secondary structure prediction is the hot topic in bioinformatics. Especially, the RNA secondary structure prediction with pseudoknot has been proved a NP-hard problem. According to the characteristics of RNA folding, a heuristic algorithm — QuasiRP to predict RNA secondary structure was presented. Using stem as the unit, combining graph theory and fundamental theory of binary relations, QuasiRP can find the optimal stem-combination based on Minimal Free Energy (MFE) criterion. The time complexity is O(n3) while the space complexity is O(n2), and pseudoknot can be found. The results show the validity of the algorithm.

Key words: RNA secondary structure, stem, pseudoknot, quasi-order set (QOS), maximal chain

摘要： RNA二级结构预测是生物信息学的研究热点和难点,特别是对于含假结的RNA二级结构的预测,已经被证明是NP问题。根据RNA折叠的特点,提出了一种基于茎区组合的智能优化算法来预测RNA 的二级结构。该算法以RNA的茎区为基本单元,结合图论思想,通过二元关系的基本理论,依据自由能最小原则获取茎区的最优组合。该算法的时间复杂度为O(n3),空间复杂度为O(n2),而且可以发现假结。实验结果证明了算法的有效性。

关键词: RNA二级结构, 茎区, 假结, 拟序集, 极大链