【摘 要】
：
目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法.随着第二代基因测序仪的大量使用和基因测序在工业中的广泛应用,常常需要对长达数十亿bp长度的基
【机 构】
：
Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences,Shenzhen,518055,PR.China
论文部分内容阅读
目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法.随着第二代基因测序仪的大量使用和基因测序在工业中的广泛应用,常常需要对长达数十亿bp长度的基因组测序数据进行处理.针对海量的基因测序数据,快速、高效和可扩展的基因拼接算法变得非常重要.虽然已出现了一些并行拼接算法,如YAGA,开始研究这些问题,但是拼接过程中时间空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序(list ranking),而该方法需要多次对De Bruijn图的海量顶点信息作分布式的排序,产生了大量的计算顶点间的通信.发现单链化简可由一次De Bruijn图深度优先遍历完成而不再需要表排序,于是提出一种基于分布式海量图遍历方法对单链化简进行优化,极大的减少处理器间的通信和计算节点之前的数据移动,因而取得比较好的扩展性,其算法复杂度O(g),通讯复杂度为O(g),这里g为参考序列的长度.用Yeast和C.elegans数据集对算法进行测试,当处理器的核数从8个增加到128个时,该算法可以得到10倍的加速比.
其他文献
理论证明蒙特卡洛模拟法能够精确估计汇率的VaR,但此方法计算量较大,实际中较难运用。在CUDA平台下利用GPU加速运算能很好的解决海量数据运算问题。在此假设汇率基本服从
资源分配方法和技术一直是云计算领域中的热点问题。针对一定的用户任务，如何选择最合适的计算资源，使用户需求得到最大程度的满足，已成为决定云计算技术商业前景的关键。现
数据挖掘并行算法，应该以不牺牲挖掘效率和挖掘质量为前提。通过对数据挖掘原理和并行化的深入研究，在考虑到挖掘效率，负载平衡，运行环境，节点状态等多方面因素的基础上，提出了
作为承载云服务的基础设施,数据中心通常会在不同的应用和租户之间进行共享.传统的带宽分配需要预留带宽,但是流量行为难以预测.InfiniBand(IB)是HPC中主导的互联技术,同
在大数据时代,图的分析和挖掘是一类非常重要的应用.其中,一大类的图算法可以用遍历模式来实现.本文通过对图遍历算法的基本计算特征进行分析,给出了一个新的实现图遍历
本文对多尺度有限元程序msFEM的CPU、GPU双精度以及GPU混合精度三个版本进行了测试.msFEM_CPU在美国橡树岭国家实验室的Jaguar上实现了从2万到20万核的可扩展性测试,在80
深度包检测(Deep Packet Inspection,DPI)是一种先进的包过滤技术,广泛应用于防火墙中。基于正则表达式的模式匹配算法已成为实现DPI重要方法之一,传统的正则表达式匹配
冬天,老年人总喜欢热水浴,以舒经活血、去寒暖身,这是有益于身体健康的。但也有人在洗澡过程中感到头晕,甚至昏倒。为了防止类似事故的发生,请老人们注意以下几个方面: 一、
计算机体系结构设计同时具有艺术性和工程性。片上多核处理器为新型计算机体系结构的设计提供了机遇为了使构思有线索可循，本文给出了基于多核处理器的计算机体系结构构思
防火墙在网络安全中起到很重要的作用，其中防火墙策略中的规则决定了网络数据包“允许”或者“拒绝”进出网络。对于大型网络来说，由于规则太多管理者很难保证其中不出现冲