rna二级结构比对动态时间规整算法研究

《rna二级结构比对动态时间规整算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文MASTERDISSERTATION论文题目RNA二级结构比对动态时间规整算法研究作者姓名张璐学科专业计算机科学与技术指导教师王常武教授2016年5月中图分类号：TP391学校代码：10216UDC：004密级：公开工学硕士学位论文RNA二级结构比对动态时间规整算法研究硕士研究生：张璐导师：王常武教授申请学位：工学硕士学科专业：计算机科学与技术所在单位：信息科学与工程学院答辩日期：2016年5月授予学位单位：燕山大学ADissertationinComputerScienceandTechnologyRESEACHOFRNAS

2、ECONDARYSTRUCTURECOMPRISIONBASEDONDYNAMICTIMEWARPINGbyZhangLuSupervisor:ProfessorWangChangwuYanshanUniversityMay,2016燕山大学硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文《RNA二级结构比对动态时间规整算法研究》是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。

3、本声明的法律结果将完全由本人承担。作者签字：日期：年月日摘要摘要RNA研究是生物信息学领域的重要内容之一。RNA结构决定RNA功能。RNA二级结构比对是结构生物、结构化学和生物信息学中的基础性问题。RNA二级结构比对研究对RNA二级结构预测和RNA功能的研究有重要意义。首先，提出了一种新的RNA二级结构表示方法，将RNA二级结构表示成一条时间序列，序列元素为非负整数。这种表示法不受RNA二级结构是否含有假结的影响，能够完整地表示RNA二级结构的结构信息。其次，在这种表示法的基础上，提出一种新的、基于动态时间规整算法的RNA二级结构比对算法

4、，即DTW-RSC算法。算法将RNA二级结构转化成与RNA等长的时间序列，通过动态时间规整算法计算时间序列间规整距离，以此度量RNA二级结构间相似性，规整距离越小代表相似性越高。再次，针对DTW-RSC算法比对效果和计算时间花费两方面，对算法进行优化并提出基于带约束的加权动态时间规整的RNA二级结构比对算法，即CWDTW-RSC算法。算法加入全局约束半径限制，缩小规整路径搜索范围，并在计算过程中运用权重调整机制，提高计算时对结构差异性影响较大的序列点对的计算权重，使得差异性和相似性结果更加显著，提高RNA二级结构数据集比对结果的区分度。最

5、后，通过两组对比实验分别验证DTW-RSC算法和CWDTW-RSC算法的可行性。第一个实验分别在四组不同数据集上运用DTW-RSC算法进行比对实验。第二个实验以算法运行时间和比对结果分布情况为评价标准验证CWDTW-RSC算法的优化效果。实验结果表明，DTW-RSC算法具有可行性，CWDTW-RSC算法比对结果区分度更高。关键词：RNA二级结构；相似性比对；动态时间规整；全局约束；加权-I-燕山大学工学硕士学位论文AbstractTheresearchofRibonucleicAcidisoneofthemostimportantpart

6、softhefieldofbioinformatics.RNAstructuredeterminesthebiologicalfunctionofRNA.Instructuralchemistry,structuralbiologyandbioinformatics,RibonucleicAcidsecondarystructuressimilaritycomparisonisafundamentalproblem.RNAsecondarystructuressimilaritycomparisoncanpromoteRNAseconda

7、rystructurepredictionandtheresearchofRNAfunction.Firstly,thisthesisdescribesandpresentsanewrepresentationofRNAsecondarystructures,whichexpressesRNAsecondarystructureasasequenceserieswhichconsistofnon-negativeintegers.Thisrepresentationwon’tberestrictedbypseudoknotsandcanr

8、epresentRNAsecondarystructurescompletelyanduniquely.Secondly,thisthesisproposesanewalgorithmbase