[发明专利]双向多步deBruijn图的压缩存储和构造方法

摘要

本发明涉及一种双向多步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；S23、若t的编码小于其互补片段编码，则交换pre,lat的值;S24、在cur的正向位置映射表的相应bit位置1来表示指向pre的边;S25、在cur的反向位置映射表的相应bit位置1来表示指向lat的边;S26、重复步骤S22‑S25，处理序列s的其他片段t，直至完成序列s的全部片段t，执行步骤S27；S27、读取一个新的序列s，重复步骤S22‑S26；直至处理完所有的序列，执行步骤S28;S28、完成双向多步de Bruijn图的构造。