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

权利要求书

1.一种双向多步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图的构造。

2.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，所述步骤S12、S22中的滑动窗口为长度为k的滑动窗口，其中0<k<32且k为奇数。

3.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，所述步骤S13中的核酸编码表为{A:00,C:01,G:10,T:11}。

4.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，所述步骤S14中的对称互补表为{A->T,C->G， G->C,T->A}。

5.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，所述步骤S14具体为，将片段t的字符串进行反转，使用对称互补表将反转的字符串中每个字符变为其互补字符，得到互补字符的字符串v，并再次使用步骤S13中的核酸编码表将字符串v进行编码，并表示为一个64位的整数b；

6.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，所述步骤S22中，若片段t没有之前或之后的片段，则对pre或者lat值赋为空或NULL。

7.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，步骤S24中正向位置映射表为{A:0，C:1，G:2，T:3}，位置查询字符为pre的最后一个字符。

8.根据权利要求1所述的双向多步deBruijn图的压缩存储和构造方法，其特征在于，步骤S25中反向位置映射表为{A:4，C:5，G:6，T:7}，位置查询字符为lat的第一个字符的互补字符。