基于启发式算法预测含假结RNA二级结构的研究进展

Review of prediction of RNA secondary structure with pseudoknots based on heuristic algorithms

RNA二级结构的预测算法研究已有近40年的发展历程,研究假结也将近30年的历史。在此期间,RNA二级结构的预测算法取得了很大进步,但假结预测的正确率依然偏低。其中启发式算法能较好地处理复杂假结,使其成为率先解决假结预测难题可能性最大的算法。迄今为止,未见系统地专门总结预测假结的各种启发式算法及其优点与缺点的报道。本文详细介绍了近年来国际上流行的贪婪算法、遗传算法、ILM算法、HotKnots算法以及FlexStem算法等五种算法,并总结分析了每种算法的优点与不足,最后提出在未来一段时期内,利用启发式算法提高假结预测准确度应从建立更完善的假结模型、加入更多影响因素、借鉴不同算法的优势等方面入手。为含假结RNA二级结构预测的研究提供参考。

Studies on prediction algorithms of RNA secondary structure last for nearly 40 years,of RNA secondary structure with pseudoknots for about 30 years.Although great progress has been made in general prediction ability,the prediction accuracy of RNA secondary structure with pseudoknots is not satisfied up to now.Among all those algorithms,the heuristic algorithms can consider complex pseudoknots very well and are most likely the algorithms to solve the problem.So far,we have not found a review which summarizes the progress,advantages and disadvantages of various heuristic algorithms for pseudoknot prediction.We selected five heuristic algorithms most popularly used,i.e.greedy algorithm,genetic algorithm,ILM,HotKnots and FlexStem algorithm.We described their principles and computing procedures,and analyzed their fortes and weaknesses.Finally,we prospected the future directions to improve the accuracy of pseudoknot prediction：to develop a better pseudoknot model,to incorporate more influence factors,to integrate advantages of different algorithms in the new algorithm.Our review could supply a useful reference for investigators for prediction of RNA secondary structure with pseudoknots.