DNA序列拼接中欧拉超路算法的新并行策略 | |
郑纬民 ; 林皎 ; 罗水华 ; ZHENG Wei-Min ; LIN Jiao ; LUO Shui-Hua | |
2010-06-09 ; 2010-06-09 | |
关键词 | 序列拼接 欧拉超路 并行拼接 哈希表 fragment assembly Eulerian superpath problem parallel assembly Hash table TP301.6 |
其他题名 | A Parallel DNA Fragment Assembly Algorithm Based on Eulerian Superpath Problem |
中文摘要 | 序列拼接是全基因组测序的核心问题之一.基于“overlap-layout-consensus”的传统拼接软件虽然被人们应用于人类基因组拼接等项目,但它们始终不能有效解决全基因组重复序列的拼装问题.为了克服上述不足,Pevzner等提出了欧拉超路拼接算法.由于该算法要求构造一个复杂的de B ru ijin图,因此用欧拉超路算法拼接大规模全基因组存在存储瓶颈问题.该文对欧拉超路拼接算法做了并行化研究并付诸实现,有效解决了欧拉超路算法中的存储瓶颈问题.测试结果表明,该并行算法具有良好的可扩缩性,能够解决较大规模全基因组的序列拼接.; Fragment assembly is one of the most important problems of Sequence Assembly.Many assembly tools based on the "overlap-layout-consensus" paradigm are used in all currently.But they still can't resolve the "repeat problem" in DNA sequencing.Pevzner put forward a new Euler algorithm that resolved this problem.Whereas the big de Bruijin graph required by the algorithm brings the bottleneck of memory.This paper presents a new fragment assembly method based on the theory of Eulerian Superpath Problem to solve the bottleneck of memory in current assembly program.The experimental results demonstrate that the program has good scalability,and can be used in DNA assembly of middle and large size of eukaryote genome.; 国家自然科学基金(60273007,60131160743); ChinaGrid项目基金资助 |
语种 | 中文 ; 中文 |
内容类型 | 期刊论文 |
源URL | [http://hdl.handle.net/123456789/55501] ![]() |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | 郑纬民,林皎,罗水华,等. DNA序列拼接中欧拉超路算法的新并行策略[J],2010, 2010. |
APA | 郑纬民,林皎,罗水华,ZHENG Wei-Min,LIN Jiao,&LUO Shui-Hua.(2010).DNA序列拼接中欧拉超路算法的新并行策略.. |
MLA | 郑纬民,et al."DNA序列拼接中欧拉超路算法的新并行策略".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论