RNA-Seq Reads mapping中基于Spark的并行FM-Index算法研究

《RNA-Seq Reads mapping中基于Spark的并行FM-Index算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：１０１３５，论文分类号：ＴＰ３９１１－＾＾１：２０１５４０１９００２－Ｓｌ｛（Ｓ究生类别：全日制ｉ研姑娜火孕领士学位？＾文－ａｒｋＲＮＡＳｅｑＲｅａｄｓｍａｐｐｉｎ中基于Ｓｐ的并行ｇＦＭ－Ｉｎｄｅｘ算法研究－ｏｎＲｅｓｅａｒｃｈｏｎＰａｒａｌｌｅｌＦＭＩｎｄｅｘＡｌｇｏｒｉｔｈｍＢａｓｅｄ－ｉｎＳｐａｒｋｉｎＲＮＡＳｅｑＲｅａｄｓＭａｐｐｇ学科门类：工学一级学科：计算机科学与技术学科、专业：计算机应用技术研究方向：生物信息数据挖掘申请人姓名：ｍ

2、指导教师姓名：纪兆华二？一八年四月二十日内蒙古师范大学硕士学位论文内蒙古师范大学硕士学位论文中文摘要随着现阶段二代高通量测序技术的不断发展，RNA-Seq测序技术所产生的数据量不断增大，庞大的数据量虽然蕴含了大量生物学信息，但是为研究人员带来了生物信息学分析的难题。快速、高效分析这些海量生物数据，挖掘数据信息，是现今生物信息学急需解决的重要问题。对于海量生物信息学数据的存储和处理，利用数千台计算机来工作显然不太现实，因此把云计算技术应用到组学大数据中对庞大的数据集进行存储、处理和分析是最佳解决方案。在RNA-Seq数据分析流程中，Read

3、smapping序列比对过程是将RNA-Seq测序得到的reads片段通过Readsmapping算法，查找在参考基因组中的坐标信息（染色体号和在该染色体中的位置）。Readsmapping分析过程是RNA-Seq数据分析流程中的第一步，也是重要的一步，数据分析结果的质量、软件程序运行时间等会对之后的数据分析产生影响。随着高通量测序技术的发展，RNA-Seq所产生的数据量有着高通量、低成本、信息量巨大等特点，传统的序列比对工具在时间消耗和对计算机内存需求方面为生物信息学分析带来巨大难题，因此需要选择合适的Readsmapping算法，进行reads序列的

4、比对有着很重要的作用。Readsmapping序列比对过程可以抽象成计算机算法中字符串搜索问题，即在一个长字符串中搜索子字符串，确定子字符串的位置。常用的Readsmapping算法包括HashTable算法、SufferArray算法、Kart算法和FM-Index算法，本文对常用四种基本算法进行简单分析比对，通过模拟reads序列数据集将四种算法在内存需求、运行时间和序列比对正确率三方面进行比对，选择综合比较相对较好的FM-Index算法，进行之后的算法并行化。在基于Spark进行FM-Index算法并行化过程中，主要在Readsmapping过程中

5、参考基因组索引建立和reads序列比对两个部分进行并行化，将参考基因组索引建立通过Spark分布式计算框架进行并行化，参考基因组索引建立过程分为三个步骤，分别为参考基因组序列的切割、键值对的洗牌与排序、RDD索引的持久化。将大的参考基因组切分成小的reads序列分给不同的RDD缓存到内存中，然后通过键值对的洗牌与排序进行索引的建立；之后在reads序列比对过程中，将输入的大量reads内蒙古师范大学硕士学位论文序列分到不同的RDD中，与参考基因组进行序列比对，确定reads在参考基因组中的坐标信息，进而实现算法的并行化，优化串行算法，达到减少Readsm

6、apping过程的时间消耗和内存需求的目的。在组学大数据时代，海量的生物信息学数据，使传统的序列比对工具很难高效的完成Readsmapping序列比对，因此将传统的mapping算法与云计算技术结合，开发出适应于生物大数据的Readsmapping序列分析过程，成为解决RNA-Seq数据分析难题的一个有效方法。大数据与云计算技术的快速发展，对于解决生物学这一难题有着很大的帮助。在序列比对过程中，通过构建云计算环境，优化短reads序列的mapping问题，进一步推进RNA-Seq数据分析的发展，对生物信息学有着重大意义。关键词：生物信息学，RNA-Seq

7、，Readsmapping，Spark分布式框架，FM-Index算法内蒙古师范大学硕士学位论文ABSTRACTWiththecontinuousdevelopmentofthesecond-generationhigh-throughputsequencingtechnology,theamountofdatageneratedbytheRNA-Seqsequencingtechnologyhascontinuouslyincreased.Althoughthehugeamountofdatacontainsalotofbiologicalinform

8、ation,ithasbroughtresearcherstheproblemo