高通量转录组测序片段快速比对算法研究

《高通量转录组测序片段快速比对算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文高通量转录组测序片段快速比对算法研究HIGH-THROUGHPUTTRANSCRIPTOMESEQUENCINGFRAGMENTSFASTALIGNMENTALGORITHM卢山哈尔滨工业大学2015年6月国内图书分类号：TP39学校代码：10213国际图书分类号：004.9密级：公开工程硕士学位论文高通量转录组测序片段快速比对算法研究硕士研究生：卢山导师：王亚东教授申请学位：工程硕士学科：计算机技术所在单位：计算机科学与技术学院答辩日期：2015年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP39U.D.C:004.9Disse

2、rtationfortheMasterDegreeinEngineeringHIGH-THROUGHPUTTRANSCRIPTOMESEQUENCINGFRAGMENTSFASTALIGNMENTALGORITHMCandidate：LuShanSupervisor：Prof.WangYadongAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：J

3、une,2015Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工程硕士学位论文摘要基因序列比对技术是基因序列数据分析的重要组成部分，也是人们深入了解生物的遗传特性,分析各种疾病,预防和抵御各种传染疾病的基础。新一代测序技术产生序列数据的速度更快，通量更高。因此出现了很多新型的RNA序列比对工具。然而，高速，精确地比对高通量RNA序列数据是一项非常具有挑战性的任务，当前新型的RNA序列比对工具在速度和准确率方面仍然有一定的不足。因此，开发一款速度快，准确率高的RNA序列比对工具是一项非

4、常有意义的工作。本文提出了一个高通量转录组测序片段快速比对工具RNA-fat。RNA-fat利用种子在read和参考基因组上位置的关系识别种子间的剪切点和结构性变异，并且通过对种子构图，高效地寻找种子覆盖read的最优路径。由于选择出的最优路径对read具有很高的覆盖度，算法在序列比对阶段的计算量大幅降低。RNA-fat对参考基因组构建DeBruijn图，提取DeBruijn图中所有的单一路径并进行排序，最终生成RNA-fat的索引。该索引由三个相互关联的子索引构成，且具有非常高的查询效率。在剪切和结构性变异的影响下，read未覆盖区域的比对边界在read上会出现

5、交叉，在参考基因组上会出现长空位。为了保证序列比对的准确性，RNA-fat对每一种情况进行判断，精确计算出read未覆盖区域在read和参考基因组上的比对边界，并采用不同的比对策略进行序列比对。通过实验数据，我们首先验证了最优覆盖路径的准确性，这就为未覆盖区域比对边界搜索的准确性打下了基础。通过对寻找最优路径的动态规划算法优化前后的效率对比，我们验证了二维线段树对RNA-fat性能优化的显著作用。最后，我们将RNA-fat和现有的RNA序列比对工具在相同的实验环境和实验数据下进行性能对比，我们发现RNA-fat具有高通量，速度快的优势，且在read比对的正确率和碱

6、基比对的正确率方面与现有RNA序列比对工具相当。关键词：DeBruijn图；二维线段树；序列比对；动态规划-I-哈尔滨工业大学工程硕士学位论文AbstractSequencealignmenttechnologyisanimportantpartofgenesequencedataanalysis.Understandingthegeneticcharacteristicsofhumanorganism,athoroughanalysisofvariousdiseases,preventionandagainstvariousinfectiousdiseasesa

7、reonthebasisofsequencealignmenttechnique.Thenextgenerationsequencingtechnologyproducedatafasterandbigger,whichleadtoarapiddevelopmentofmanynewRNAsequencealignmenttools.However,accuratealignmentofhigh-throughputRNA-seqdataisachallengingproblem,andcurrentlyRNAsequencealignmenttoolshavep

8、roble