DNA序列拼接中欧拉超路算法的新并行策略.pdfVIP

第 29卷 第 1期 计 算 机 学 报 VoI．29 No．I 2006年 1月 CHINESEJ0URNAL0FC0MPUTERS Jan．2006 DNA序列拼接中欧拉超路算法的新并行策略 郑纬民 林 皎 罗水华 (清华大学计算机科学与技术系 北京 100084) (教育部生物信息学重点实验室 北京 100084) 摘 要 序列拼接是全基因组测序的核心问题之一．基于 “overlap—layout—consensus”的传统拼接软件虽然被人们 应用于人类基因组拼接等项 目，但它们始终不能有效解决全基 因组重复序列的拼装问题．为了克服上述不足， Pevzner等提出了欧拉超路拼接算法．由于该算法要求构造一个复杂的deBruijin图，因此用欧拉超路算法拼接大 规模全基因组存在存储瓶颈问题．该文对欧拉超路拼接算法做了并行化研究并付诸实现，有效解决了欧拉超路算 法中的存储瓶颈问题．测试结果表明，该并行算法具有 良好的可扩缩性，能够解决较大规模全基因组的序列拼接． 关键词 序列拼接；欧拉超路；并行拼接；哈希表 中图法分类号 TP301 A ParallelDNA FragmentAssemblyAlgorithm Basedon EulerianSuperpath Problem ZHENGW el-Min LIN Jiao LUO ShubHua (DepartmentofComputerScienceandTechnology，TsinghuaUniversity，Beijing 100084) (MinistryofEducationKeyLaboratoryonBioinfomatics，Beijing 100084) Abstract Fragmentassembly isoneofthemostimportantproblemsofSequenceAssembly． M anyassemblytoolsbasedonthe “overlap—layout—consensus”paradigm areusedinallcurrently． Buttheystillcan’tresolvethe “repeatproblem”inDNA sequencing．Pevznerputforwardanew Euleralgorithm thatresolvedthisproblem．WhereasthebigdeBruijingraphrequiredbytheal— gorithm bringsthebottleneckofmemory．Thispaperpresentsanew fragmentassemblymethod basedonthetheoryofEulerianSuperpathProblem tosolvethebottleneckofmemoryincurrent assemblyprogram．Theexperimentalresultsdemonstratethattheprogram hasgoodscalability， andcanbeusedinDNA assemblyofmiddleandlargesizeofeukaryotegenome． Keywords fragmentassembly；Euleriansuperpathproblem ；parallelassembly；Hashtable 制，人们不可能将生物的全基因组全部测出来．现有 引 目 测序仪的测量能力仅为 500bp(basepairs)左右．而