欢迎来到天天文库
浏览记录
ID:35103521
大小:6.94 MB
页数:66页
时间:2019-03-17
《高效的分布式大规模基因组序列组装》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、;TP39910058^、:;iiW勝!HftDSS^ff隨f!D)J'-■■xtrV,0’:’''-、觸;、梓^Wmp^_巧e_難_/雨^论文题目:高效的分布式大规模基因组K'睦计算欄学与技术::Iili学科专业fi^gs;'、.‘’作親名:^__-:fl!!:^Afe指导教师:陈科I201日.12完成日期:i^h誦i独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研巧工作和取得的,研巧成果,除了文
2、中特别加W标注和致谢之处外论文中不包含其他人己经发表化不旬含为巧得夫津女送或其化教育机构的学位或_下#或撰写过的研巧成果,证书而使用过的材料一。与我同工作的同志对本研巧所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名:签字日期户年言月日fI学位论文版权使用授权书本学位论文作者完全了解韦津工业女當有关保留、使用学位论文的规定。特授权弄津T#女摩可W将学位论义的全部或部分内容编入有关数据库进行。、、汇编W供查阅和借阅同意学检索,并采用影印缩印或扫描等复制手
3、段保存校向国家有关部口或机构送交论文的复印件巧磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名:导师签名:"签字曰期7>诉!?年月9>曰签字曰期:曰^>£^^^妾是学位论文的主要创新点一一、设计种基于重叠图结构的算法使得通过读长的重新映射,并利用重叠群之间的很好的互补特点,使得重叠群可继续组装,我们的思路是首先将重叠群-建立索引,然后把读长对(readpairs向重叠群上映射(Ma),每个重叠群都会得)p一到个被长对所映射的集合(Reduce),然后通过比对验证,这
4、些集合就形成了一个潜在可组装的类,然后构建类中的重叠图,从而将序列拼接问题转化成图论中的问题来进斤求解。二、减少运行时间;在减少运行时间方面,采用更高效的分布式框架aReduce.Mp,设计分布式算法,来34行序列拼接,并且在算法的在各个不同的阶段进行任务均衡并行化。使用布隆过滤器(BloomFilter)将较慢的0批勺的时间复杂度的映射操作降低为0巧W。H、降低软件包对大内存的要求;针对大规模数据集在降低算法的内存开销一,是将任务合理的分配在集群上方面,利用集群中的单机的内存做子
5、任务二;是在任务执行过程中,对于超过系统内存或设定内存大小的任务采取线程等待()的策略;H是将处理过程的数据在Hadoop平台中的HDFS文件系统和内存进行交换。四、在提高基因组拼接的指标上,我们在N90、N50lil及最长的支架等指栋上均有较大幅度的提高,尤其是在真实的数据集上表现明显。摘要一在基因组序列组装算法中,个最基本的问题就是如何合适的选择上T游的一一短序列用于组装成个长序列。当单独从个种子序列进行扩展的时候,大量的重复的区域将会导致非常多的扩展的候选,从而导致序列姐装
6、问题非常的复杂。--目前通用的方法就是选择个基于短序列(巧端序列)之间的重叠信息然后进行沮装的。然而当所组装的基因组序列是非常高重复的复杂数据的时候,这种方法将面临巨大的挑战,尤其是序列数据中还包含有错误、高重复的序列W及不均衡的测序深度导致基因组中某些区域只有少量的序列覆盖或者大量的序列覆盖。所有的这些原因导致了现在的组装程序得不到最完美的组装基因组数据。本文提出了通过原始读长信息寻找基于多个无参考序列的拼接算法产生的重叠群么间的重叠信息,来进行再组装。算法通过首先将重叠群建立扛mer
7、位置索引,然后进行读长映射、潜在聖叠群聚类、可组装重叠群聚类等步骤进斤搭支架。整个算法流程能高效率便捷的运行,我们将整个算法流程设计为基于化doop的分布式平台,并在多个部分使用MapReduce算法,且在较小的内存机器上就可LU运行。在大肠杆菌的基因组数据集上运行结果表明,本文提出的算法在组装的多项指标上据表现出良好的性能,在N50指标上有将近46%的提高,整体的组装化[io覆盖度更加接近参考序列,并且算法能在op平台±高效的运斤。educe关键词:基因组组装MapR;重:搭支架;;叠
8、群化隆过滤器AbstractInenomeassembthermari巧uesowtoetermneustreamangly,piyihdipddow打streamsequenceregio打sofsequenceseedsforCO打structinglongcontigsorscaffo.Wlds
此文档下载收益归作者所有