科创中国

本发明涉及一种双向多步deBruijn图的压缩存储和构造方法，包括压缩存储步骤，和deBruijn图构造步骤。本发明提供的双向多步deBruijn图的压缩存储和构造方法，（1）结合DNA序列互补双螺旋结构的特点，对de Bruijn图结构进行结构优化，使用双向多步de Bruijn图，可以将需要存储的图的节点减半；（2）针对序列组装的原始de Bruijn图规模异常庞大，对内存造成存储压力等问题，使用双向多步de Bruijn图的压缩存储技术，使得存储双向多步de Bruijn图的内存消耗控制在参考序列大小的100倍以内；（3）构造双向多步de Bruijn图，可将DNA序列组装问题分解为边融合子问题，更适合并行计算

一种双向多步deBruijn图的压缩存储和构造方法，其特征在于，包括压缩存储步骤，具体为S11、读取一个序列s；S12、将序列s用滑动窗口切割为多个片段t；S13、对每个片段t，使用核酸编码表进行编码，并表示为一个64位的整数a；S14、将片段t进行反转，使用对称互补表将反转的片段互补处理，得到互补片段v，并再次使用步骤S13中的核酸编码表将互补片段进行编码，并表示为一个64位的整数b；S15、取整数a和整数b的最大数，作为片段t和互补片段v的k分子的标志数；S16、重复步骤S11‑S15，直至所有序列完成；和deBruijn图构造步骤，具体为S21、读取一个序列s；S22、将序列s用滑动窗口切割为多个片段t，选取一片段t其标志数为cur、并标记其前、后的片段的标志数分别为pre、lat

新一代基因测序技术所产生的序列片段具有序列短、高覆盖率、额外的双端信息 等特点，使得原有传统的序列拼接技术无法使用，加大了序列拼接技术的复杂度和难点。面 对海量的数据，高效的序列拼接技术成为处理测序数据的关键。 W03] 序列拼接技术问题主要转化为图论的知识进行求解。当前，序列拼接 技术问题解决途径主要有两条。一种途径是传统的先重叠后扩展方法，即化C (Overlap-Layout-Consensus)方法。该方法主要是将序列拼接技术转化为哈密尔顿路径进 行求解。0LC的拼接过程主要分为Ξ个步骤：1)Overlap:对获得的所有read顶点进行排 序，通过序列比对算法，寻找DNA序列片段间的重叠信息；2儿ayout:根据read之间的重叠 信息，排列所有DNA序列片段，形成新的链接体结构，该步骤主要是为了寻找经过每个顶点 一次且仅一次的路径，即寻找哈密尔顿路径；3)Consensus:根据新的链接体结构中原始质 量数据，在链接体中寻找质量最重的路径，从而组合成最终的DNA序列。

中国科学院深圳先进技术研究院提升了粤港地区及我国先进制造业和现代服务业的自主创新能力，推动我国自主知识产权新工业的建立，成为国际一流的工业研究院。 深圳先进院目前已初步构建了以科研为主的集科研、教育、产业、资本为一体的微型协同创新生态系统，由九个研究平台，国科大深圳先进技术学院，多个特色产业育成基地、多支产业发展基金、多个具有独立法人资质的新型专业科研机构等组成。开展先进技术研究，促进科技发展。信息、电子、通讯技术研究新材料、新能源技术研究高性能计算、自动化、精密机械研究生物医学与医疗仪器研究相关学历教育、博士后培养与学术交流。

本发明提供的双向多步de化uUn图的压缩存储和构造方法，采用压缩存储步骤 和de化uUn图构造步骤，（1)结合DNA序列互补双螺旋结构的特点，对de化uUn图结构 进行结构优化，使用双向多步deBruijn图，可W将需要存储的图的节点减半；（2)针对序 列组装的原始de化uijn图规模异常庞大，对内存造成存储压力等问题，使用双向多步de 化uUn图的压缩存储技术，使得存储双向多步de化uUn图的内存消耗控制在参考序列大 小的100倍W内；（3)构造双向多步de化uUn图，可将DNA序列组装问题分解为边融合子 问题，更适合并行计算。本发明的方法提高了现有技术序列拼接运行速度、降低了单机内存 消耗。

技术合作

上所述本发明的具体实施方式，并不构成对本发明保护范围的限定。任何根据 本发明的技术构思所作出的各种其他相应的改变与变形，均应包含在本发明权利要求的保 护范围内。