预测RNA二级结构的新算法

摘要

应用热动力学最小自由能量方法从RNA序列预测其二级结构起始于Tinoco等人,Zuker将动态规划算法用于复杂的Tinoco模型,设计了Mfold算法,算法的时间复杂度为O(n3).Mfold算法不允许伪结点存在,但伪结点在几种已知RNA中具有重要功能.包含伪结点的RNA二级结构预测问题是NPC问题.Rivas与Eddy提出了简化的包含多个伪结点的热动力学模型,并首次相应的多项式时间算法,算法的时间复杂度为O(n6).B.1yngs(φ)等人提出仅包含一个平面伪结点的模型及算法,其时间复杂度为O(n5),空间复杂度为O(n3). 本文提出了一个新算法，其时间复杂度为O（n5），空间复杂度为O（n4）。算法使用六段子序列的组合表示包含伪结点的＊＊A二级结构，并利用Lsnns巾算法的一个计算技巧，可预测包含多个平面伪结点和一个非平面伪结点的二级结构。