浅议基于堆积的rna假结预测算法

《浅议基于堆积的rna假结预测算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东大学博士学位论文基于堆积的RNA假结预测算法姓名：李恒武申请学位级别：博士专业：计算机软件与理论指导教师：朱大铭20080405山东大学博士学位论文摘要RNA结构预测是计算生物学的基本课题之一。RNA二级结构预测是由RNA序列预测其三级结构的第一步。早期采用序列对比分析方法预测RNA二级结构，对于在不同有机体中起相同生物功能的一级结构进行比较得到RNA序列的二级结构。许多RNA分子的同源序列不易得到，需要耗费大量人力，因而序列对比分析方法的预测效率较低。目前人们广泛采用最小能量方法预测RNA二级结构。最小能量方法是基于热动力学模型寻找序列所能形成的各种构象中具有最小能量的结构。Zuk

2、er提出的MFOLD算法是目前应用较为广泛的二级结构预测算法，其预测正确率为73％左右。但该算法不能预测假结和更复杂的结构。假结(pseudoknot)是RNA中最广泛的三级结构单元，是较复杂但稳定的RNA结构。假结预测是目前RNA结构预测研究的关键点和研究热点。假结在不同的RNA分子中具有调节、催化、构造等重要功能。预测包含任意假结的RNA二级结构属于NP-hard类。预测简单假结的最小能量算法是人们讨论较多的含假结二级结构预测方法。Rivas和Eddy提出的PKNOTS算法使用o(n6)时间和o(n4)空间预测任意的平面假结和部分非平面假结，Jens和Robert提出的PknotsR

3、G算法使用D仍4)时间和O(n2)空NNN简单的嵌套假结，Lyngso和Pedersen提出的LP算法使用O(n5)时间和D(矿)空间预测一个平面假结。组合优化算法只考虑RNA序列中的部分主要作用，如Cary和Storm提出的最大权匹配算法可以折叠RNA假结，但以预测正确率降低为代价。也有将遗传算法、模拟退火算法、神经网络算法应用到RNA假结预测中的计算尝试。相邻基对构成堆积(mack)，碱基配对和堆积作用是稳定RNA结构的主要作用。堆积最大化问题也是近年来人们十分关注的含假结RNA二级结构预测问题。Ieong等人于2001年提出最大堆积基对数问题，并设计出该问题的近似性能比为3的近似算

4、法。Lyngse于2004年给出了最大堆积基对数问题的精确算法，并且提出最大堆积数问题，证明最大堆积数问题属于NP·hard类，给出了其多项式时山东大学博士学位论文间近似方案。Lyngsa将所有堆积等同看待，但RNA结构实验的结果表明，不同类型的堆积有不同的能量，堆积的能量由构成堆积的基对类型所决定。因此我们基于生物学的碱基配对和基对堆积作用，提出了最大权堆积问题，并讨论最大权堆积问题的求解算法和计算复杂性。我们将堆积划分为(Xa,SB)和㈣丑4)两类，利用∞剐)类构成团的特性计算其最优结构，利用堆积的划分特性计算似4』髓)类的3／2近似的结构，取权值最大者作为整个序列的近似结构，给出了

5、预测任意假结的多项式时间近似算法，其近似性能比为3，时间复杂度为O(nlogn)，空间复杂度为∞)。我们将序列划分为长度小于K+1(2鳓的子序列，使用动态规划计算和保存各类子序列的已配对权值和未配对子序列数，删除不可能结构和权值小的结构，计算长度小于K+1的子序列构成的最优结构作为整个序列的近似结构，给出预测任意假结的多项式时间近似方案。目前预测含假结RNA二级结构的多项式时间算法，难以计算大的RNA分子。连续的堆积构成茎(stem)，茎的交叉构成假结。因此基于茎区组合来寻找RNA最优结构成为新的RNA结构预测方法，如Benedeti等人提出的茎区堆积算法和李伍举等人提出的茎区随机堆积算

6、法，预测嵌套的RNA二级结构。最近Ruan等人提出基于茎区的启发式算法预测包含假结的二级结构，其时间复杂度为0(玎4)，空间复杂度为o(n2)。我们设计了一个预测任意假结的茎最大化的启发式算法。首先搜索序列可能构成的全部茎，找出具有最小能量的最大茎，然后在序列中标记最大茎对应的碱基，使其不再参与后面的配对，再在剩余的碱基中找出次最大茎，依次类推，直至无茎为止。该算法的时间复杂度为O(n3)，空间复杂度为O(n)，可以预测长度达5000个碱基的RNA序列。我们的算法使用茎代替基对，使用标记代替删除，消除了大量冗余基对和无意义的堆积，提高了预测的正确率。相对D03)时间和0(矛)空间的最大权

7、匹配算法，其空间复杂度由O(n2)降至∞)；实验表明其敏感性由80％提高到87．8％，特异性由53．7％提高到75．9％。与83．3％的预测正确率的遗传算法Ⅱ山东大学博士学位论文和79．70,6的预测正确率的模拟退火算法相比，我们的算法将预测正确率提高到87．5％。最小自由能量方法预测RNA结构的关键是结构的表示建模。基于妣～分子茎区相对稳定的结构特征，我们引入半扩展结构和k茎，使用k茎计算半扩展结构，使用半扩展结构的交叉计算嵌套和