包含假结的RNA结构预测算法研究

【摘要】RNA(核糖核酸)作为生物大分子具有十分重要的生物学功能,RNA结构预测是计算分子生物学的基本课题之一,也是当今国际研究热点。RNA结构预测中很多问题都是NP-难的,与其设计不出精确算法,不如去设计其多项式时间近似算法,去指导该类问题的生物应用。RNA三级结构是比较稳定的结构,而预测RNA三级结构需先预测RNA二级结构。预测RNA二级结构方法主要有序列对比分析法和最小自由能量法,序列对比分析方法预测RNA二级结构,是通过在不同生物有机体中起相同生物功能的一级结构进行比对得到RNA碱基序列的二级结构。许多生物有机体RNA分子的同源序列不易得到,需要耗费大量人力,因而序列对比分析方法的预测效率较低,利用最小能量方法来预测RNA二级结构是广泛采用方法之一Zuker提出的Mfold算法是早期基于最小能量方法来研究的二级结构预测算法,最小能量方法的本质是基于热动力学模型寻找RNA碱基序列所能形成的各种结构中具有最小能量的结构。Mfold算法的预测正确率为70%左右,但该算法不能预测假结和更复杂的结构,因而其应用受到较大限制。假结是RNA分子中最广泛的三级结构单元,是较复杂但稳定的RNA结构。假结在不同的RNA分子中具有构造、干扰、催化、调节等重要功能,包含假结的RNA预测是当今国际RNA结构预测研究的关键点和研究热点,预测包含任意假结的RNA二级结构问题是NP难的,至今未找到该问题有效的多项式算法,近似算法则为求解NP难问题的核心方法。连续基对构成堆叠,基对的交叉形成假结点,茎区的交叉构成假结结构,目前现有的预测含假结的RNA二级结构的算法,对较大的RNA分子计算很困难。基于茎区组合来寻找RNA优化结构成为包含假结RNA结构预测重要方法,Benedeti等人提出基于茎区组合的能量集合算法来预测RNA二级结构,Ruan等人提出基于茎区的启发式算法来预测包含假结的RNA二级结构,其时间复杂度为O)(n4),空间复杂度为O(n2)。本文根据RNA假结表示模型,基于RNA茎区结构相对稳定的特征和最小自由能量原理,提出了预测含假结的RNA二级结构的启发式算法,时间复杂度为O(n3)和空间复杂度为O(n2),通过在RNA假结库实验表明,该算法有较好的预测特异性和敏感性。连续堆叠可构成茎区,针对基于茎区的RNA优化结构,将序列划分为长度不大于t(t>2)的子序列,计算由长度不大于t的子序列构成的最优结构作为整个序列的近似结构,设计出预测任意假结的1+ε(ε>0)多项式时间近似方案(PTAS)。通过对假结加以限制来预测简单假结的最小能量算法是目前较多的含假结二级结构预测方法,Rivas和Eddy提出的Rivas算法使用预测任意的平面假结和部分非平面假结,其时间复杂度为O(n6)和空间复杂度为O(n4)。Jens和Robert提出的JR算法可预测简单的嵌套假结,时间复杂度为O(n4)时间,空间复杂度为O(n2)空间,Lyngs(?)和Pedersen使用相容结构代替Rivas算法中的缺口矩阵,提出了Lyngso算法,算法时间复杂度为O(n5)和空间复杂度为O(n3),但该算法仅能预测一个平面假结。连续堆叠形成茎区,堆叠和茎区是稳定RNA结构的主要作用,Cary和Storm提出的最大权匹配算法可以折叠RNA假结结构,但以预测正确率降低为代价。堆叠最大化问题也是近年来人们十分关注的含假结RNA二级结构预测问题。在平面RNA二级结构中,允许假结的存在使计算最大堆叠数问题成为NP难的,Ieong.S等人提出了最大堆叠基对数问题,设计了带任意假结的RNA二级结构预测近似算法,分别设计出平面二级结构的近似算法和普通二级结构的近似算法,并且证明了平面RNA二级结构中求含假结的最大堆叠数问题也是NP难的。分析了包含假结的RNA二级结构,剖析连续堆叠对和假结的结构特性,分析求解最大堆叠数的近似算法,其近似性能比为1/3,给出了证明,讨论了最大堆叠数问题的计算复杂性,并且可以预测更复杂的假结。给出RNA碱基序列S和正整数h,通过把三划分匹配这一NP难问题规约到该问题,判断在平面RNA二级结构中是否可能存在大于等于h的最大堆叠数,从而证明了在平面RNA二级结构中含假结的最大堆叠数问题也是NP难的。本文的主要工作为：1、基于最小自由能量的RNA结构的表示建模是RNA结构预测的关键。对于假结而言,可分为平面假结和非平面假结,假结可形成嵌套或并列结构,由两个茎区结构可形成嵌套假结,由内环和凸起可构成平面假结,平面假结经常出现在RNA分子中,交叉假结也存在于RNA中。茎区在RNA结构稳定性中承担着重要作用,基于茎区的交叉可形成假结的特性,可利用茎区结构建立关于假结的表示模型。在PseudoBase假结数据库中,大部分为平面假结,也包含少量的非平面假结。通过设计启发函数、用恰当的假结表示建模来预测RNA假结结构可取得较好的效果。根据RNA假结表示模型,基于最小自由能量原理,设计了预测任意平面假结和非平面假结的启发式算法,通过在PseudoBase等假结数据库实验验证表明,算法的预测敏感性特异性和预测准确度均有所提高,其时间复杂度为O(n3),空间复杂度为O(n2)。2、一般来说,连续的堆叠可形成茎区结构,茎区结构可使RNA结构能量降低,结构更稳定。通过茎区的组合优化特性来预测RNA优化结构是我们采用的重要方法,茎区之间可形成并列结构、嵌套结构和交叉结构。含有交叉结构即包含假结,假结的存在是RNA结构预测变得复杂,是问题难解性的重要因素,使得设计多项式时间算法变得异常困难,设计该问题的近似算法或近似方案成为处理该问题的重要手段。针对基于茎区的RNA优化结构,把RNA碱基序列用短茎进行划分,计算由长度不大于t的茎区构成的结构作为整个序列的近似结构,重新分析了预测任意假结的1+ε(ε>0)多项式时间近似方案。3、在RNA碱基序列中,连续的两个碱基对可构成堆叠,从堆叠的角度看,多个连续碱基对可形成连续堆叠,连续堆叠中堆叠的个数越多,则RNA结构越稳定。在RNA结构预测中,包含假结的计算最大堆叠数问题也是NP难的,针对该类问题,与其设计不出多项式时间精确算法,不如退而求其次,通过其内在特性的深入分析,设计求解该类问题的多项式时间近似算法。分析其近似性能比,尝试降低近似比,指导该问题的求解。针对连续堆叠对的结构特性,重新分析了RNA二级结构最大堆叠数问题,通过在RNA折叠结构中查找连续堆叠,并对内在特性加以剖析,分析了计算最大堆叠数的近似算法,其近似性能比为3,并给出了近似性能比的证明。本文下一步的主要工作包括：1、设计包含任意平面假结的RNA结构预测近似算法,降低近似性能比和时间复杂度。2、设计求解包含假结的普通RNA结构最大堆叠数近似算法,进一步降低近似性能比,降低时间复杂度。3、针对平面和非平面RNA假结结构,其结构特性和组合特性仍需深入剖析挖掘,期望设计出更精确的预测算法。
【作者】刘振栋；
【导师】朱大铭；
【作者基本信息】山东大学，计算机软件与理论，2014，博士
【关键词】RNA结构；堆叠；假结；近似算法；近似方案；

【参考文献】
[1]蔡灿鑫.中国上市企业海外并购绩效及动因的实证研究[D].复旦大学,财务管理,2012,硕士.
[2]崔海莉.关联规则挖掘法在CRM中的应用[J].安徽科技,2005,08:48-49.
[3]陈迪.邓小平社会建设思想研究[D].西南大学,科学社会主义与国际共产主义运动,2013,硕士.
[4]潘晓旭.旅游文本翻译中的信息重组策略研究[D].沈阳师范大学,翻译,2014,硕士.
[5]王晓璐.基于C8051F数据采集传输平台的研究与实现[D].东北大学,计算机应用技术,2010,硕士.
[6]赵双园.消费分层的制度变迁解释[D].吉林大学,社会学,2004,硕士.
[7]王帅.Ti_2AlC/Cu复合材料的制备表征及其摩擦磨损行为研究[D].哈尔滨工业大学,材料学,2014,硕士.
[8]于纯妍.基于SOAP分布式组件通信的研究[D].大连海事大学,计算机应用技术,2004,硕士.
[9]李盈莹.大学生采纳移动网络购物的影响因素研究[D].吉林大学,企业管理,2014,硕士.
[10]杨红.基于GIS的滇中引水工程昆明段岩溶区适宜性评价[D].成都理工大学,环境地质,2013,硕士.
[11]曾维顺.蒙古—鄂霍茨克洋俯冲的记录：额尔古纳地区八大关变质杂岩的证据[D].吉林大学,构造地质学,2014,硕士.
[12]焦豪.创业导向下企业动态能力提升机制研究[D].浙江大学,2007.
[13]张佳丽.电针预处理对兔心肌缺血再灌注损伤腺苷A1受体、PKC的影响[D].湖南中医药大学,针灸推拿学,2014,硕士.
[14]陈爽.确定利率下保险公司最优保费政策问题的研究[D].吉林大学,应用数学,2013,硕士.
[15]马立克,王成山.无差拍控制提高变速异步风力发电系统的故障承受能力(英文)[J].电力系统自动化,2007,22:50-55+69.
[16]曹涛.带叶间粘弹减摆器的旋翼耦合系统气弹动力学研究[D].南京航空航天大学,飞行器设计,2004,硕士.
[17]徐生年.星系中心大质量黑洞宇宙学演化模型[D].中国科学技术大学,天体物理学,2014,博士.
[18]陈婷.南京方言语音考察[D].南京师范大学,汉语言文字学,2012,硕士.
[19]罗五四,吴永强,谌仕涛,林屹,汪洋.基于VC++的汽车材料切削力测试系统研制[J].工具技术.2004(01)
[20]朱智飞.固相光催化氧化法处理印染废水的研究[D].广东工业大学,化学工艺,2004,硕士.
[21]潘笑,万敏.基于模糊神经网络的数据挖掘方法研究[J].微电子学与计算机,2005,12:48-50+54.
[22]孔维荣,张云灿.废旧轮胎胶脱硫再生方法研究进展[J].高分子通报,2014,02:78-96.
[23]赵一鸣.直埋敷设供热弯管的地震响应分析[D].哈尔滨工业大学,岩土工程,2013,硕士.
[24]吴达胜,方陆明,唐丽华,刘丽娟.XML技术在森林资源管理信息系统异构数据集成中的应用[J].浙江林学院学报,2003,04:75-79.
[25]张华宇.外资中小企业资金管理实践及问题研究[D].西南交通大学,工商管理,2013,硕士.
[26]魏强.论我国浮动抵押法律制度之完善[D].宁波大学,民商法学（专业学位）,2014,硕士.
[27]和明华.简单线性规划问题教学现状的调查与研究[D].河北师范大学,学科教学,2014,硕士.
[28]李岚.新型水泥混凝土路面嵌绑材料的研究[D].华南理工大学,交通运输工程,2012,硕士.
[29]汪俊逸.TiO_2基复合材料的制备与性能研究[D].南京航空航天大学,2014.
[30]常凯.管制性征收的原意阐释[D].郑州大学,宪法学与行政法学,2013,硕士.
[31]矫龙.一种柔性覆铜板用聚酰亚胺复合膜的制备及表征[D].吉林大学,有机化学,2014,硕士.
[32]马立松.1PSY185型单体喷油泵试验台[J].柴油机.1991(04)
[33]赖冠宙.深基坑空间共同变形法[D].广东工业大学,岩土工程,2004,硕士.
[34]王燕飞.面向旅游企业的客户定向性信息分析的研究[D].合肥工业大学,信息管理与信息系统,2013,硕士.
[35]孙晋博,余隋怀,陈登凯.基于证据理论融合多特征的物体识别算法[J].计算机工程与应用.
[36]张利君.《广东高等教育的发展与改革》讲座的口译研究报告[D].东北师范大学,翻译,2012,硕士.
[37]肖尧,郑建风.复杂交通运输网络上的拥挤与效率问题研究[J].物理学报,2013,17:547-552.
[38]徐勤勤.三峡水库鱼体中汞和甲基汞的分布特征[D].西南大学,环境工程,2014,硕士.
[39]石陶.分组密码算法SMS4的安全性分析[D].山东大学,计算机应用技术,2013,硕士.
[40]朱晓璐.基于叙事学的景观空间体验研究与应用[D].西南交通大学,设计艺术学,2013,硕士.
[41]刘胜洋.锂离子电池超薄型电极的制备研究[D].沈阳理工大学,应用化学,2012,硕士.
[42]朱旭,李春兰,刘琴,朱效华,张银堂,徐茂田.石墨烯/纳米金复合材料的无酶葡萄糖生物传感器制备[J].分析化学,2011,12:1846-1851.
[43]徐扬.电子产品PHM方法开发和验证实验平台研究[D].西安电子科技大学,材料物理与化学,2013,硕士.
[44]魏玲玲.一氧化碳释放分子CORM-2对大鼠实验性牙周炎的影响[D].山东大学,口腔临床医学,2013,硕士.
[45]邱丽娅.遂宁职业技术学校模具专业课在线辅助教学系统的设计与实现[D].电子科技大学,软件工程（专业学位）,2013,硕士.
[46]RajabM.R.Kassim（卡西姆）.香菇凝胶样多糖的结构分析及生物活性研究[D].东北师范大学,生物化学与分子生物学,2012,硕士.
[47]任倩倩.顺序注射微流控焦磷酸测序系统的改进及其应用[D].东北大学,分析化学,2010,硕士.
[48]王广伟.教室的室内定位系统的设计与开发[D].华东师范大学,通信与信息系统,2013,硕士.
[49]宗东升.数据挖掘在中药指纹图谱中的应用[D].沈阳药科大学,2005.
[50]毕思文.数字人体——人体系统数字学总论[J].中国医学影像技术,2003,S1:1-8.