论文部分内容阅读
【摘 要】假结是RNA分子结构中一类特殊三级结构且决定多种生物功能。早期的RNA结构预测算法为简化操作多避开假结仅研究二级结构，降低了预测结果的精确度。随着算法研究的逐步成熟，假结研究成为预测重点。文中介绍了近几年提出的四类带假结的RNA二级结构预测算法，通过对算法效率及精确度的比较展望了未来算法的发展方向。
【关键词】RNA二级结构；假结；自由能；启发式算法
上世纪八十年代Pleij与Kolk等人在对几种毒菌RNA分子的结构分析中，证实了假结作为一类复杂而稳定的RNA结构广泛存在于多种生物细胞中，是实现其功能的重要因素，如端粒酶RNA分子的活性取决于其假结结构、某些病毒细胞利用假结结构模仿宿主的tRNA分子入侵生物体[1]。因此，要分析RNA分子的真实结构，假结预测是必须解决的问题。为提高假结预测的准确性，1990年Pleij利用数学方法提出了14种理论上存在的RNA假结结构，并利用弧图进行了分析和归纳。2009年刘元宁等人在Pleij的基础上利用平面图对假结结构的表示法进行了改进[2]。由于假结种类繁多、结构复杂，在RNA二级结构研究早期假结预测就已被证明为NP-hard问题，经过对预测算法的不断完善，目前也只有发夹环与单链形成的H型假结可被精确预测 [3]。本文将重点介绍最新提出的几类带假结RNA二级结构预测算法，再对其预测精度、复杂度和假结预测能力进行比较，最后还将展望未来预测算法的发展方向。
1.预测算法
针对待测序列本身以自由能为评判标准，利用计算机算法预测可能的RNA二级结构，是目前预测算法的主要发展方向，本部分将介绍四类带假结的RNA二级结构预测算法。
1.1 基于动态权重匹配的RNA折叠算法
2008年陆健和刘海军等人提出基于动态权重匹配的RNA折叠算法（Dynamic Weighted Matching，DWM），该算法在重大权重匹配算法的基础上引入了与茎区长度相关的动态权重，并结合碱基配对的固定权重作为茎区筛选的检验标准，通过茎区优化组合的方式预测出包含假结的RNA二级结构[4]。在DWM算法中将动态权重和固定权重合称为复合权重，若给定一段茎区S（i，j，k），则其计算公式（1）如下：
其中，第一项是配对碱基的固定权重之和，第二项为动态权重，其值由三类碱基配对的平均权重与茎区长度的平方根之积确定。DWM算法的运行流程是：首先在序列R=r1r2…rn中找出具有最大权重的茎区S（i，j，k），该茎区将序列分为三部分即：单链区L1（1，i），茎区S（i，j，k），单链区L2（j，n）；然后分别L1、L2中搜索最大权重和茎区，如此递归搜索下去，直到序列首尾处的单链都不再具备形成茎区的条件为止；最后，再对第一次划分得到的单链L1，L2中尚未配对的碱基进行联合搜索，当搜索到最大权重茎区后再对剩余段继续递归搜索。该算法利用RNA回折规律，优先考虑短程碱基之间的配对，通过逐步搜索简化了自由能计算及算法复杂度，并且大幅提高了算法预测假结的能力。仿真实验结果表明，由于优先考虑短程碱基配对，DWM算法可以有效预测出tRNA序列的二级结构及假结，但针对非编码的RNA序列的预测效果则不理想[4]。
1.2 RnaPredict算法
RnaPredict算法是由Wiese等人于2002年提出的一类基于进化算法的RNA二级结构预测算法，其核心内容是利用十进制编码为初始种群中的单元结构（一个茎区及其顶端的发夹环）分配序号，然后利用选择、交叉、变异算子对结构集进行逐代优化，最终具备最小自由能的结构集即为预测到的RNA二级结构[5]。其后，Wiese等人对该算法进行了改进，2005年在文献[6]中尝试研究利用并行遗传算法提高计算效率，解决长链RNA序列的二级结构预测问题；2008年在文献[7]中对热力学模型进行了改进，提出了最近邻居模型（Individual Nearest Neighbor Model，INN）和最近邻居氢键模型（Individual Nearest Neighbor Hydrogen Bond Model，INN-HB），这两类模型额外考虑了各类碱基对组合对茎区稳定性的影响，以及不同碱基间形成的氢键对自由能的贡献；2009年在文献[8]中结合HotKnots的假结热力学模型利用进化算法尝试预测含假结的RNA二级结构并取得良好效果；2010年在文献[9]中将退火模拟算法与遗传算法相结合推
1.3 ProbKnot算法
2010年Bellaousov和Mathews等人提出了基于碱基配对概率的ProbKnot算法，该算法能够预测任意类型的假结，且时间复杂度仅为O（n2） [10]。算法原理是：首先利用机器学习法和热力学模型推导出一个用于计算碱基配对概率的配分函数，根据该配分函数计算出任意碱基i在其序列中的最大配对概率pmax（i）；然后，搜索出当前拥有最大配对概率的碱基对（i，j），若p（i，j）=pmax（i）= pmax（j）则将该序列纳入到最终预测结构中；接着在剩余序列中沿用上述方法搜索最大概率配对碱基，直到没有符合配对条件的碱基为止；最后，对形成的结构进行合法性处理，即解除碱基对数量小于3的茎区，若两非法茎区间只存在一个由单碱基构成的凸环时，则优先考虑将两非法茎区合并为一个合法茎区。仿真实验表明，算法在预测长度小于700的RNA序列时运行时间不超过10分钟，且预测精度可达到60%以上。该算法的缺点是阳性检测概率低，这是由于算法仅以配对概率作为预测依据而对结构特征没有任何限制，因而阴性配对大量出现，影响了预测准确性。这一问题在后期Matthew和Mathews两人提出的TurboKnot算法中得到了改进[11]，在TurboKnot算法中序列合成不仅依赖于碱基配对概率，另外还引入了同源序列的结构特征数据，从而提高了检测的准确性。 1.4 MCGenus算法
McGenus算法于2013年由Micheal和Micheletti等人提出，该算法利用基于随机搜索的蒙特卡罗算法，以最小自由能为依据预测RNA二级结构[12]。该算法可预测长度小于1000的RNA序列，其不限制假结类型。算法流程是：先根据给定序列计算出所有可能的单元结构集{h1，h2，…hN}，该单元结构中包括一个规模为1的凸环或规模为1×1的内环，并计算出其自由能贡献为e（hi），然后由算法随机生成一个由0和1构成的序列{δ1， δ2，…δN}，其中δi对应hi，当δi=1则表示对应单元结构入选待测结构，反之则未被选中。在初始序列中有且仅有一个单元结构被选中。随后进入蒙特卡罗迭代过程，在迭代过程中算法按概率W选中单元结构做移入或移出操作，其选择移入移出操作的标准为自由能F的增减，其中概率w和自由能F的计算公式（2）、（3）如下：
2.算法性能比较
本部分将就上述四类算法的仿真实验结果进行比较，内容包括算法时间复杂度、空间复杂度、算法运行时长、敏感度、特异性等方面，比较结果如表1所示。四类算法中效率最高的是ProbKnot；针对短序列时DWM算法的精确度最高，但该算法无法预测长链序列；针对长链序列则ProbKnot算法相对性能较好。此外，除DWM算法外，其余算法均提供了基于对应算法的RNA二级结构预测工具，方便后续研究者做实验数据对比。
3.总结及展望
本文介绍了四类带假结RNA二级结构预测算法，算法体现了较好的预测效率和精度。在假结预测方面，排除了对假结类型的限制，但预测结果不算理想，例如，精度最高的ProbKnot算法其假结预测精度也不到5%。此外，算法的效率也有待提高，如RnaPredict算法基本没有提到其在运算时间上的表现；ProbKnot算法预测长度为2904的RNA序列二级结构时用时63 min 18.6 sec；MCGenus算法需在并行计算机上才能达到表1所述的运行效率。因此，在今后的RNA二级结构预测算法研究中，应从提高假结预测精度及简化算法复杂度两方面提高算法的精度与效率。可行的提高途径包括：（1）利用愈发先进的物理化学实验手段提高对RNA结构的认识，优化热力学模型参数特别是假结数据；（2）通过对已知结构序列的分析，细化RNA自我折叠的过程，提高算法的仿真程度进而提高预测精度；（3）利用多种算法设计混合预测算法，使其综合各家之长，互补其短，提高算法预测的精度及效率。
参考文献：
[1]van-Batenburg F H， Gultyaev A P， Pleij C W. PseudoBase： structural information on RNA pseudoknots[J].Nucleic Acids Research，2001，29（1）：194-195.
[2]刘元宁，张浩，李志，崔广迪，苗轶蝉.RNA假结结构分析[J].吉林大学学报（工学版），2009，39（1）：265-269.
[3]A P Gultyaev， F H D van Batenburg， C W A Pleij. An approximation of loop free energy values of RNA h-pseudoknots[J].RNA，1999，5（1）：609-617.
[4]陆健，刘海军，姚勤，等.基于动态权重匹配的RNA折叠算法[J].生物数学学报， 2008，23（4）：
743-749.
[5]Kay C Wiese， E Glen. A permutation base genetic algorithm for RNA secondary structure prediction[C].Advances in Artificial Intelligence，2002.
[6]Kay C Wiese， Andrew Hendriks， Alain Deschênes， Belgacem Ben Youssef. P-RnaPredict-A parallel evolutionary algorithm for RNA folding：effects of pseudorandom number quality[J].IEEE Transactions on NanoBioscience，2005，4（3）：219-227.
[7]Kay C Wiese， Alain A Deschenes， Andrew G Hendriks. RnaPredict—An evolutionary algorithm for RNA secondary structure prediction[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics，2008，5（1）：25-41.
[8]Kay C Wiese， A Hendriks. RNA pseudoknot prediction via an evolutionary algorithm[C].IEEE Congress on Evolutionary Computation，2009.
[9]Herbert H Tsang， Kay C Wiese. SARNA-Predict：Accuracy improvement of RNA secondary structure prediction using permutation-based simulated annealing[J].IEEE/ACM Transactions on Computational Bioilgy and Bioinformatics，2010，7（4）：727-740.
[10]Statslav Bellaousov， David H Mathews. ProbKnot：Fast prediction of RNA secondary structure including pseudoknots[J].Bioinformatics，2010，16（10）：1870-1880.
[11]Matthew G Seetin， David H Mathews. TurboKnot： rapid prediction of conserved RNA secondary structures including pseudoknots [J].Bioinformatics，2012，28（6）：792-798.
[12]M. Bon， C Micheletti， H Orland. McGenus： A monte carlo algorithm to predict RNA secondary structures with pseudoknots [J].Nucleic Acids Research，2013，41（3）：1895-1900.
【关键词】RNA二级结构；假结；自由能；启发式算法
上世纪八十年代Pleij与Kolk等人在对几种毒菌RNA分子的结构分析中，证实了假结作为一类复杂而稳定的RNA结构广泛存在于多种生物细胞中，是实现其功能的重要因素，如端粒酶RNA分子的活性取决于其假结结构、某些病毒细胞利用假结结构模仿宿主的tRNA分子入侵生物体[1]。因此，要分析RNA分子的真实结构，假结预测是必须解决的问题。为提高假结预测的准确性，1990年Pleij利用数学方法提出了14种理论上存在的RNA假结结构，并利用弧图进行了分析和归纳。2009年刘元宁等人在Pleij的基础上利用平面图对假结结构的表示法进行了改进[2]。由于假结种类繁多、结构复杂，在RNA二级结构研究早期假结预测就已被证明为NP-hard问题，经过对预测算法的不断完善，目前也只有发夹环与单链形成的H型假结可被精确预测 [3]。本文将重点介绍最新提出的几类带假结RNA二级结构预测算法，再对其预测精度、复杂度和假结预测能力进行比较，最后还将展望未来预测算法的发展方向。
1.预测算法
针对待测序列本身以自由能为评判标准，利用计算机算法预测可能的RNA二级结构，是目前预测算法的主要发展方向，本部分将介绍四类带假结的RNA二级结构预测算法。
1.1 基于动态权重匹配的RNA折叠算法
2008年陆健和刘海军等人提出基于动态权重匹配的RNA折叠算法（Dynamic Weighted Matching，DWM），该算法在重大权重匹配算法的基础上引入了与茎区长度相关的动态权重，并结合碱基配对的固定权重作为茎区筛选的检验标准，通过茎区优化组合的方式预测出包含假结的RNA二级结构[4]。在DWM算法中将动态权重和固定权重合称为复合权重，若给定一段茎区S（i，j，k），则其计算公式（1）如下：
其中，第一项是配对碱基的固定权重之和，第二项为动态权重，其值由三类碱基配对的平均权重与茎区长度的平方根之积确定。DWM算法的运行流程是：首先在序列R=r1r2…rn中找出具有最大权重的茎区S（i，j，k），该茎区将序列分为三部分即：单链区L1（1，i），茎区S（i，j，k），单链区L2（j，n）；然后分别L1、L2中搜索最大权重和茎区，如此递归搜索下去，直到序列首尾处的单链都不再具备形成茎区的条件为止；最后，再对第一次划分得到的单链L1，L2中尚未配对的碱基进行联合搜索，当搜索到最大权重茎区后再对剩余段继续递归搜索。该算法利用RNA回折规律，优先考虑短程碱基之间的配对，通过逐步搜索简化了自由能计算及算法复杂度，并且大幅提高了算法预测假结的能力。仿真实验结果表明，由于优先考虑短程碱基配对，DWM算法可以有效预测出tRNA序列的二级结构及假结，但针对非编码的RNA序列的预测效果则不理想[4]。
1.2 RnaPredict算法
RnaPredict算法是由Wiese等人于2002年提出的一类基于进化算法的RNA二级结构预测算法，其核心内容是利用十进制编码为初始种群中的单元结构（一个茎区及其顶端的发夹环）分配序号，然后利用选择、交叉、变异算子对结构集进行逐代优化，最终具备最小自由能的结构集即为预测到的RNA二级结构[5]。其后，Wiese等人对该算法进行了改进，2005年在文献[6]中尝试研究利用并行遗传算法提高计算效率，解决长链RNA序列的二级结构预测问题；2008年在文献[7]中对热力学模型进行了改进，提出了最近邻居模型（Individual Nearest Neighbor Model，INN）和最近邻居氢键模型（Individual Nearest Neighbor Hydrogen Bond Model，INN-HB），这两类模型额外考虑了各类碱基对组合对茎区稳定性的影响，以及不同碱基间形成的氢键对自由能的贡献；2009年在文献[8]中结合HotKnots的假结热力学模型利用进化算法尝试预测含假结的RNA二级结构并取得良好效果；2010年在文献[9]中将退火模拟算法与遗传算法相结合推
1.3 ProbKnot算法
2010年Bellaousov和Mathews等人提出了基于碱基配对概率的ProbKnot算法，该算法能够预测任意类型的假结，且时间复杂度仅为O（n2） [10]。算法原理是：首先利用机器学习法和热力学模型推导出一个用于计算碱基配对概率的配分函数，根据该配分函数计算出任意碱基i在其序列中的最大配对概率pmax（i）；然后，搜索出当前拥有最大配对概率的碱基对（i，j），若p（i，j）=pmax（i）= pmax（j）则将该序列纳入到最终预测结构中；接着在剩余序列中沿用上述方法搜索最大概率配对碱基，直到没有符合配对条件的碱基为止；最后，对形成的结构进行合法性处理，即解除碱基对数量小于3的茎区，若两非法茎区间只存在一个由单碱基构成的凸环时，则优先考虑将两非法茎区合并为一个合法茎区。仿真实验表明，算法在预测长度小于700的RNA序列时运行时间不超过10分钟，且预测精度可达到60%以上。该算法的缺点是阳性检测概率低，这是由于算法仅以配对概率作为预测依据而对结构特征没有任何限制，因而阴性配对大量出现，影响了预测准确性。这一问题在后期Matthew和Mathews两人提出的TurboKnot算法中得到了改进[11]，在TurboKnot算法中序列合成不仅依赖于碱基配对概率，另外还引入了同源序列的结构特征数据，从而提高了检测的准确性。 1.4 MCGenus算法
McGenus算法于2013年由Micheal和Micheletti等人提出，该算法利用基于随机搜索的蒙特卡罗算法，以最小自由能为依据预测RNA二级结构[12]。该算法可预测长度小于1000的RNA序列，其不限制假结类型。算法流程是：先根据给定序列计算出所有可能的单元结构集{h1，h2，…hN}，该单元结构中包括一个规模为1的凸环或规模为1×1的内环，并计算出其自由能贡献为e（hi），然后由算法随机生成一个由0和1构成的序列{δ1， δ2，…δN}，其中δi对应hi，当δi=1则表示对应单元结构入选待测结构，反之则未被选中。在初始序列中有且仅有一个单元结构被选中。随后进入蒙特卡罗迭代过程，在迭代过程中算法按概率W选中单元结构做移入或移出操作，其选择移入移出操作的标准为自由能F的增减，其中概率w和自由能F的计算公式（2）、（3）如下：
2.算法性能比较
本部分将就上述四类算法的仿真实验结果进行比较，内容包括算法时间复杂度、空间复杂度、算法运行时长、敏感度、特异性等方面，比较结果如表1所示。四类算法中效率最高的是ProbKnot；针对短序列时DWM算法的精确度最高，但该算法无法预测长链序列；针对长链序列则ProbKnot算法相对性能较好。此外，除DWM算法外，其余算法均提供了基于对应算法的RNA二级结构预测工具，方便后续研究者做实验数据对比。
3.总结及展望
本文介绍了四类带假结RNA二级结构预测算法，算法体现了较好的预测效率和精度。在假结预测方面，排除了对假结类型的限制，但预测结果不算理想，例如，精度最高的ProbKnot算法其假结预测精度也不到5%。此外，算法的效率也有待提高，如RnaPredict算法基本没有提到其在运算时间上的表现；ProbKnot算法预测长度为2904的RNA序列二级结构时用时63 min 18.6 sec；MCGenus算法需在并行计算机上才能达到表1所述的运行效率。因此，在今后的RNA二级结构预测算法研究中，应从提高假结预测精度及简化算法复杂度两方面提高算法的精度与效率。可行的提高途径包括：（1）利用愈发先进的物理化学实验手段提高对RNA结构的认识，优化热力学模型参数特别是假结数据；（2）通过对已知结构序列的分析，细化RNA自我折叠的过程，提高算法的仿真程度进而提高预测精度；（3）利用多种算法设计混合预测算法，使其综合各家之长，互补其短，提高算法预测的精度及效率。
参考文献：
[1]van-Batenburg F H， Gultyaev A P， Pleij C W. PseudoBase： structural information on RNA pseudoknots[J].Nucleic Acids Research，2001，29（1）：194-195.
[2]刘元宁，张浩，李志，崔广迪，苗轶蝉.RNA假结结构分析[J].吉林大学学报（工学版），2009，39（1）：265-269.
[3]A P Gultyaev， F H D van Batenburg， C W A Pleij. An approximation of loop free energy values of RNA h-pseudoknots[J].RNA，1999，5（1）：609-617.
[4]陆健，刘海军，姚勤，等.基于动态权重匹配的RNA折叠算法[J].生物数学学报， 2008，23（4）：
743-749.
[5]Kay C Wiese， E Glen. A permutation base genetic algorithm for RNA secondary structure prediction[C].Advances in Artificial Intelligence，2002.
[6]Kay C Wiese， Andrew Hendriks， Alain Deschênes， Belgacem Ben Youssef. P-RnaPredict-A parallel evolutionary algorithm for RNA folding：effects of pseudorandom number quality[J].IEEE Transactions on NanoBioscience，2005，4（3）：219-227.
[7]Kay C Wiese， Alain A Deschenes， Andrew G Hendriks. RnaPredict—An evolutionary algorithm for RNA secondary structure prediction[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics，2008，5（1）：25-41.
[8]Kay C Wiese， A Hendriks. RNA pseudoknot prediction via an evolutionary algorithm[C].IEEE Congress on Evolutionary Computation，2009.
[9]Herbert H Tsang， Kay C Wiese. SARNA-Predict：Accuracy improvement of RNA secondary structure prediction using permutation-based simulated annealing[J].IEEE/ACM Transactions on Computational Bioilgy and Bioinformatics，2010，7（4）：727-740.
[10]Statslav Bellaousov， David H Mathews. ProbKnot：Fast prediction of RNA secondary structure including pseudoknots[J].Bioinformatics，2010，16（10）：1870-1880.
[11]Matthew G Seetin， David H Mathews. TurboKnot： rapid prediction of conserved RNA secondary structures including pseudoknots [J].Bioinformatics，2012，28（6）：792-798.
[12]M. Bon， C Micheletti， H Orland. McGenus： A monte carlo algorithm to predict RNA secondary structures with pseudoknots [J].Nucleic Acids Research，2013，41（3）：1895-1900.