基于特殊内码和汉明、VT码的DNA优化存储编解码方法

基于特殊内码和汉明、vt码的dna优化存储编解码方法
技术领域
1.本发明涉及一种分布式存储领域的信息编码技术，具体是一种基于特殊内码和汉明、vt码的dna优化存储编解码方法。


背景技术：

2.近年来，全球数据信息呈现爆炸性增长，这一数据增长趋势将很快超过现有硬盘等存储介质的承受能力，dna分子由于存储密度高、保存时间长、维护成本低等优点成为下一代新型存储介质的首选。dna存储编码技术通过引入冗余数据来保证dna数据存储的可靠性，编码后的数据信息经过dna合成加以存储。
3.根据dna分子的结构特性和生物存储技术，适用于dna存储的编码方法要求：1)能够纠正dna序列中的碱基替换、插入、删除错误；2)dna序列满足鸟嘌呤-胞嘧啶(gc)-平衡(gc含量为50％)和游程约束(连续出现同一碱基的长度不超过6)，以降低存储过程中的错误率，提高鲁棒性；3)冗余度低，降低编码成本；4)原始数据能够通过译码恢复。现有的编码方法包括以下几类：第一类利用传统纠错码(rs码、bch码、ldpc码等)作数据编码，这种方法只能纠正dna序列中的碱基替换或擦除错误，无法处理插入或删除错误。第二类直接利用levenshtein码编码，这种方法生成的dna序列可以纠正插入、删除或替换错误，但不满足gc平衡和游程约束，鲁棒性差。第三类将levenshtein码与一种平衡技术相结合，来达到gc-平衡的目的，但不满足游程约束，鲁棒性欠佳。


技术实现要素：

4.本发明针对现有技术存在的上述不足，提出一种基于特殊内码和汉明、vt码的dna优化存储编解码方法，适用于dna存储系统，编码后的dna序列，能够同时满足gc-平衡和游程约束，具有高鲁棒性，而且具备纠错性能，解决现有方法无法做到的：同时达到高鲁棒性、低冗余度，并且纠正碱基替换、插入、删除错误的问题。当码长为n时，本方法的译码复杂度最高为o(nlogn)。
5.本发明是通过以下技术方案实现的：
6.本发明涉及一种基于特殊内码和汉明、vt码的dna优化存储编解码方法，包括：参数初始化阶段、预处理阶段、编码阶段和译码阶段。
7.所述的参数初始化阶段是指：初始化具有高鲁棒性的特殊内码、汉明码和vt码的参数，具体为：选取内码的码长为6，构建四元域为包含四个元素的有限域，为内码的作用域；选取汉明码作用的有限域的大小参数q和汉明码的余维数r，其中q为不超过1280的素数幂，r为正整数；选取α为有限域的生成元，生成有限域选取β满足β2+β+1＝0作为生成元，生成四元域
8.所述的汉明码的码长维数
9.所述的vt码的码长为
10.所述的预处理阶段是指：将待存储的二进制数据序列转化为q元数据序列m待编码。
11.所述的编码阶段包括：
12.步骤1：对经过预处理的q元数据序列m，利用汉明码进行编码，得到长为n的汉明码码字，构成q元汉明码ham(r；q)，该汉明码
13.步骤2：生成高鲁棒性内码集合具体为：初始化内码集合依次考虑四元域上的6维向量按照映射0
→
c，1
→
g，β
→
a，β2→
t，转化为一条长为6的dna序列y，并判断当y中碱基c和g的个数为3时将x加入集合否则舍弃；当遍历四元域上全部的6维向量后得到高鲁棒性内码集合
14.步骤3：对步骤2得到的内码集合中的码字进行排序，具体为：对四元域的元素排序：0＞1＞β＞β2；对任意两个不同的码字从左向右依次比较c和c
′
的每一位分量，找到c和c
′
中出现的第一个分量不同的位置i，并判断当ci大于ci′
时，构建c＞c
′
，否则构建c＜c
′
。
15.步骤4：对步骤1中的q元汉明码ham(r；q)与步骤2生成的高鲁棒性内码集合作级联编码：
16.步骤5：构建从有限域到高鲁棒性内码集合的单射π：将0映射为的第1个码字；对0≤i≤q-2，将αi映射为的第i+2个码字。
17.步骤6：利用映射π对每个汉明码码字c＝(c1，c2，
…
，cn)∈ham(r；q)做级联编码，具体为：将c的每一位分量ci映射为中的向量π(ci)，得到长为6n的四元向量并按照0
→
0，1
→
1，β
→
2，β2→
3的映射关系，转化为长为6n的四进制序列，构成级联码该级联码
18.所述的级联码的码长为6n，码字个数为极小汉明距离大于等于3，即可以纠正一位替换错误。
19.步骤7：对级联码进行四元vt码编码，具体为：选取整数a和b为四元vt码的校验参数，利用(a，b)型四元vt码对编码，得到四元dna码编码，得到四元dna码
20.所述的校验参数满足：0≤a≤6n-1,0≤b≤3，该校验参数a和b通过以下方式得到：对四进制序列x＝(x1，...，x
6n
)∈{0，1，2，3}
6n
，构建其二进制相伴序列为a(x)＝(a1，...，a
6n
)∈{0，1}
6n
，其中：a1取值为0，对2≤i≤6n，当xi≥x
i-1
时，ai取值为1；当xi＜x
i-1
时，ai取值为0；对于根据鸽笼原理，存在整数a和b使得：遍历所有0至6n-1之间的整数a以及0至3之间的整数b，选取满足的一组整数a和b。
21.步骤8：按照映射关系：0
→
c，1
→
g，2
→
a，3
→
t，将四元dna码中的四进制序列转化为由a、t、c、g构成的dna序列进行存储，序列长度为6n。
22.优选地，所述的步骤2中高鲁棒性内码集合中的四元向量，都满足gc-平衡和游程约束，具有高鲁棒性，具体为：根据步骤4中的映射关系“0
→
c，1
→
g，β
→
a，β2→
t”，四元向量中碱基g和c的含量相当于其中符号1和0的含量，恰好为50％。同时，每个四元向量长度为6，故其中连续出现同一符号的长度至多为3，即游程长度不超过3，即高鲁棒性内码集合是一个具有高鲁棒性的内码，并且码字个数为
23.优选地，所述的步骤6中级联码的所有码字满足gc-平衡和游程约束，具有高鲁棒性，具体为：令(π(c1)，π(c2)，...，π(cn))为级联码的任意码字，则，(c1，c2，
…
，cn)是一个汉明码码字。对i＝1，...，n，有π(ci)是的码字。根据步骤4所述的，π(ci)的gc-含量为50％，游程长度不超过3，则(π(c1)，π(c2)，...，π(cn))的gc-含量为50％，游程长度不超过6，即的所有码字满足gc-平衡和游程约束，能够降低存储过程中的出错率，达到高鲁棒性的要求。
24.优选地，所述的步骤7中的四元dna码满足gc-平衡和游程约束，具有高鲁棒性。具体为：的每个码字也是级联码的码字，故而满足gc-平衡和游程约束。
25.优选地，所述的步骤7中的dna码的码字个数并且并且令n＝6n表示dna码的码长，可以计算得到码的冗余度为的冗余度为比特。
26.所述的译码阶段包括：将经过dna测序后的dna序列按照c
→
0，g
→
1，a
→
2，t
→
3的关系，转化为一条四进制序列y＝(y1，...，yn′
)∈{0，1，2，3}n′
，序列长度为n
′
，并比较n
′
与6n的大小关系：
27.①
当n
′
＝6n，则判定发生一位替换错误，并进行恢复：建立四进制序列集合{0，1，2，3}6到的映射σ：若四进制序列x在映射π的像集中(这里v指的是编码阶段-步骤7中给出的映射π)，即存在一个中的元素z使得，π(z)＝x，则，σ将x映射为元素否则，σ将x映射为0，再将四进制序列y按照每6位一组，根据映射关系σ，转化为一条上长为n的序列c，则c为至多在一个位置发生替换错误的汉明码码字，利用汉明码译码器对向量c进行译码，得到原始的q元数据序列m，并还原成二进制数据读取。
28.②
当n
′
＝6n+1或6n-1，则判定发生一位插入或删除错误，并进行恢复：利用四元vt码的译码算法，将四进制序列y译码，得到长为6n的原始vt码码字c。对c每6位一组，经映射σ转化为一条长度为n的q元序列，此序列为一个汉明码码字，进而可得到q元数据序列m，并还原成二进制数据读取。
29.优选地，所述的译码阶段中dna码可以纠正单个碱基替换错误，采用汉明码译码算法进行译码，译码复杂度为o(nlogn)，n为码长。
30.优选地，所述的译码阶段中dna码可以纠正单个碱基插入或删除错误，采用四元vt码的译码算法进行译码，译码复杂度为o(n)，n为码长。
技术效果
31.本发明通过对原始数据预处理、进行汉明码编码、利用特殊构造的内码级联、级联后再编码、转化为dna序列存储的步骤，从而在每个编码过程中，分别实现dna序列纠正替换错误、高鲁棒性以及纠正插入删除错误的特性。。与现有技术直接对二进制数据序列编码，再转化为四元序列存储相比，本发明优先对二进制数据序列预处理，得到q元序列，从而可以在有限域上进行数据编码。通过建立到的映射，再转化为四元序列编码并存储，显著增加编码的灵活性。
附图说明
32.图1为本发明的流程示意图。
具体实施方式
33.如图1所示，为本实施例涉及一种基于特殊内码和汉明、vt码的dna优化存储编解码方法，包括以下步骤：
34.步骤1：初始化高鲁棒性内码、汉明码和vt码的参数。选取内码的码长为6，构建内码作用的四元域这里β满足β2+β+1＝0为的生成元。选取q＝127炔(素数)，构建汉明码作用的有限域选取汉明码的余维数r＝2，则汉明码的码长维数k＝1278。选取vt码的码长为6n＝7680。在实际操作中，汉明码的参数q和r可以按需要进行调整，本实施例作为特殊举例说明，不影响本发明在其他参数下的作用效果。
35.步骤2：从计算机中随机输入16k的二进制数据作为原始数据，并转化为127炔元的数据序列m待编码。
36.步骤3：利用汉明码进行数据编码。利用汉明码编码器对预处理后的序列m编码，得到长度为1280的汉明码码字，构成127炔元汉明码，并记作ham(2；127炔)。具体地，对一条信息序列m＝(m1，...，m
1278
)作为信息位，按照以下汉明码的两个校验方程生成两位校验位p1，p2：(1)m1+m2+
…m1278
+p1＝0(mod127炔)；(2)0
·
m1+1
·
m2+2
·
m3+
…
+1277
·m1278
+1278
·
p1+p2＝0(mod127炔).则编码后的汉明码码字为(m1，...，m
1278
，p1，p2)。
37.步骤4：生成高鲁棒性内码步骤4：生成高鲁棒性内码的具体生成过程为：
38.初始化内码集合依次考虑上的6维向量按照映射0
→
c，1
→
g，β
→
a，β2→
t转化为dna序列y，并判断y中碱基c和g的个数是否为3，若是，将x加入集合否则舍弃。当遍历上的全部6维向量后，最终得到集合通过计算得到，的码字个数为1280。根据所述的{0，1，β，β2}到dna碱基集合{a，t，c，g}的映射，中每个向量的gc-含量等价于该向量中0和1的含量，正好为50％。
39.步骤5：对内码中的码字进行排序。首先对的元素按如下排序：0＞1＞β＞β2。对任意两个不同的码字从左向右依次比较c和c
′
的
每一位分量，找到c和c
′
中出现的第一个分量不同的位置i，并比较ci和ci′
的大小。若ci＞ci′
，则构建c＞c
′
，否则构建c＜c
′
。根据所述的排序规则，通过计算机搜索和排序，可以将内码中的码字排列开来。考虑到的码字数量有1280个，下面只按顺序列出的前16个码字如下(格式：序号/码字)：1(0，0，0，β，β，β)5(0，0，0，β2，β，β)9(0，0，1，β，β，β)13(0，0，1，β2，β，β)2(0，0，0，β，β，β2)6(0，0，0，β2，β，β2)10(0，0，1，β，β，β2)14(0，0，1， β2，β，β2)3(0，0，0，β，β2，β)7(0，0，0，β2，β2，β)11(0，0，1，β，β2，β)15(0，0，1，β2，β2，β)4(0，0，0，β，β2，β2)8(0，0，0，β2，β2，β2)12(0，0，1，β，β2，β2)16(0，0，1，β2，β2，β2)
40.步骤6：对步骤3中编码后的汉明码码字，利用步骤4构造的内码作级联编码：
41.步骤7：构造从有限域到内码的映射π：π将中的元素i映射为的第i+1个码字，0≤i≤1278。
42.步骤8：利用内码和映射π，对汉明码码字c＝(c1，c2，...，c
1280
)做级联，将每一位ci映射为中的向量π(ci)，得到长度为7680的四元向量再再按照0
→
0，1
→
1，β
→
2，β2→
3的映射关系，将级联后的码字转化为一条四进制序列，构成级联码并且并且中的每条四进制序列的gc含量(0、1的含量)为50％，而且游程长度小于等于6，具备高鲁棒性的要求，能够显著降低在存储过程中的错误出现率。每条四进制序列的极小汉明距离大于等于3，可以纠正一位替换错误。
43.步骤9：对四进制序列x＝(x1，...，x
7680
)∈{0，1，2，3}
7680
，构建其二进制相伴序列为a(x)＝(a1，
…
，a
7680
)∈{0，1}
7680
，其中：a1取值为0，对2≤i≤7680，当xi≥x
i-1
时，ai取值为1；当xi＜x
i-1
时，ai取值为0。
44.步骤10：对中的四进制序列，利用(0，0)型四元vt码进行编码得到四元dna码
45.步骤11：按照映射关系：0
→
c，1
→
g，2
→
a，3
→
t，将dna码中的四进制序列转化为由a、t、c、g构成的dna序列进行存储。
46.步骤12：译码过程：将经过dna测序后的dna序列按照c
→
0，g
→
1，a
→
2，t
→
3的关系，转化为一条四进制序列y＝(y1，...，yn′
)∈{0，1，2，3}n′
，序列长度为n
′
，并比较n
′
与7680的大小关系。
47.步骤13：若n
′
＝7680，则判定发生一位替换错误。首先建立四进制序列集合{0，1，2，3}6到有限域的映射σ：若四进制序列x在映射π的像集中(这里π指的是编码阶段-步骤7中给出的映射π)，即存在一个中的元素z使得，π(z)＝x，则，σ将x映射为元素否则，σ将x映射为0，再将四进制序列y按照每6位一组，根据映射关系σ，转化为一条上长为1280的序列c，则c为至多在一个位置发生替换错误的汉明码码字，利用汉明码译码器对向量c进行译码，得到原始的127炔元数据序列m，并还原成二进制数据读取。
48.步骤14：若n
′
＝7681或767炔，则判定发生一位插入或删除错误。利用四元vt码的译码算法，将四进制序列y译码，得到长为7680的原始vt码码字c。对c每6位一组，按照步骤13所述的映射σ，转化为一条长度为1280的127炔元序列，此序列为一个汉明码码字，进而可得到127炔元数据序列m，并还原成二进制数据读取。
49.经过具体实际实验，在matlab2021平台上进行仿真，随机输入16k的二进制数据作为原始数据，选取汉明码余维数r＝3，有限域大小q＝127炔运行上述方法。能够得到的实验数据是：生成10条长度为7860的四元dna编码序列，每条dna序列满足gc含量稳定在50％以及游程约束条件，具有高鲁棒性，能够显著降低dna序列在合成和测序中的错误发生率。根据汉明码以及四元vt码的译码算法，该dna编码方法可以抵抗一位替换或插入或删除错误。同时，本次dna编码存储16k的数据，需要字节的数据量，冗余度比值为为根据理论计算，通过本方法最终得到的dna编码的冗余度为比特，冗余度比值为当q取值1279时，冗余度达到比特，冗余度比值理论上可达与实验基本一致。在其他场合下，允许汉明码的有限域大小q为任意不超过1280的素数幂，汉明码的余维数r是随机生成的正整数。
50.本发明通过对原始二进制数据做预处理，再对预处理的数据做三次编码，包括：先利用汉明码作外码编码，再利用自行构造的高鲁棒性四元内码作级联编码，接着，对级联的四元码利用四元vt码进一步编码，最后给出一个纠正单个插入、删除、替换错误的dna编码方案，从而保证dna序列的gc-含量稳定在50％，而且每个dna序列中连续出现同一碱基的个数小于等于6，满足游程约束，能够显著降低dna序列在合成和测序中的错误发生率。
51.相较于以往的编码方案，本发明得到的dna编码方法能够同时达到以下优势：i)gc-含量稳定在50％；ii)编码后的dna序列连续出现同一碱基的长度小于等于6；iii)能够纠正一位碱基替换、插入、删除错误；iv)冗余度较低，节约编码成本，从而显著降低dna序列在合成和测序中的错误出现率，从而具有高鲁棒性的同时弥补之前的dna编码方法无法同时达到纠错性能和高鲁棒性的局限。
52.上述具体实施可由本领域技术人员在不背离本发明原理和宗旨的前提下以不同的方式对其进行局部调整，本发明的保护范围以权利要求书为准且不由上述具体实施所限，在其范围内的各个实现方案均受本发明之约束。

技术特征：
1.一种基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征在于，包括：参数初始化阶段、预处理阶段、编码阶段和译码阶段；所述的预处理阶段是指：将待存储的二进制数据序列转化为q元数据序列m待编码；所述的编码阶段包括：步骤1：对经过预处理的q元数据序列m，利用汉明码进行编码，得到长为n的汉明码码字，构成q元汉明码ham(r；q)，该汉明码步骤2：生成高鲁棒性内码集合具体为：初始化内码集合依次考虑四元域上的6维向量按照映射0
→
c，1
→
g，β
→
a，β2→
t，转化为一条长为6的dna序列y，并判断当y中碱基c和g的个数为3时将x加入集合否则舍弃；当遍历四元域上全部的6维向量后得到高鲁棒性内码集合步骤3：对步骤2得到的内码集合中的码字进行排序，具体为：对四元域的元素排序：0＞1＞β＞β2；对任意两个不同的码字从左向右依次比较c和c
′
的每一位分量，找到c和c
′
中出现的第一个分量不同的位置i，并判断当c
i
大于c
i
′
时，构建c＞c
′
，否则构建c＜c
′
；步骤4：对步骤1中的q元汉明码hamcr；q)与步骤2生成的高鲁棒性内码集合作级联编码：步骤5：构造从有限域到高鲁棒性内码集合的单射π：将0映射为的第1个码字；对0≤i≤q-2，将α
i
映射为的第i+2个码字；步骤6：利用映射π对每个汉明码码字c＝(c1，c2，...，c
n
)∈ham(r；q)做级联编码，具体为：将c的每一位分量c
i
映射为中的向量π(c
i
)，得到长为6n的四元向量并按照0
→
0，1
→
1，β
→
2，β2→
3的映射关系，转化为长为6n的四进制序列，构成级联码该级联码步骤7：对级联码进行四元vt码编码，具体为：选取整数a和b为四元vt码的校验参数，利用(a，b)型四元vt码对编码，得到四元dna码编码，得到四元dna码步骤8：按照映射关系：0
→
c，1
→
g，2
→
a，3
→
t，将四元dna码中的四进制序列转化为由a、t、c、g构成的dna序列进行存储，序列长度为6n。2.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的参数初始化阶段是指：初始化高鲁棒性内码、汉明码和vt码的参数，具体为：选取内码的码长为6，构建四元域为包含四个元素的有限域，为内码的作用域；选取汉明码的汉明码作用的有限域的大小参数q和汉明码的余维数r，其中q为不超过1280的素数幂，r为正整数；选取α为有限域的生成元，生成有限域选取β满足β2+β+1＝0作为生成元，生成四元域3.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的校验参数满足：0≤a≤6n-1,0≤b≤3，该校验参数a和b通过以下方式得到：对
四进制序列x＝(x1，...，x
6n
)∈{0，1，2，3}
6n
，构建其二进制相伴序列为a(x)＝(a1，...，a
6n
)∈{0，1}
6n
，其中：a1取值为0，对2≤i≤6n，当x
i
≥x
i-1
时，a
i
取值为1；当x
i
＜x
i-1
时，a
i
取值为0；对于0；对于根据鸽笼原理，存在整数a和b使得：遍历所有0至6n-1之间的整数a以及0至3之间的整数b，选取满足的一组整数a和b。4.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的译码阶段包括：步骤a：将经过dna测序后的dna序列按照c
→
0，g
→
1，a
→
2，t
→
3的关系，转化为一条四进制序列y＝(y1，...，y
n
′
)∈{0，1，2，3}
n
′
，序列长度为n
′
，并比较n
′
与6n的大小关系：
①
当n
′
＝6n，则判定发生一位替换错误，并进行恢复：建立四进制序列集合{0，1，2，3}6到的映射σ：当四进制序列x在映射π的像集中存在一个中的元素z使得π(z)＝x，则σ将x映射为元素否则，σ将x映射为0；然后将四进制序列y按照每6位一组，根据映射关系σ，转化为一条上长为n的序列c，即c为至多在一个位置发生替换错误的汉明码码字，利用汉明码译码器对向量c进行译码，得到原始的q元数据序列m，并还原成二进制数据读取；
②
当n
′
＝6n+1或6n-1，则判定发生一位插入或删除错误，并进行恢复：利用四元vt码的译码算法，将四进制序列y译码，得到长为6n的原始vt码码字c，对c每6位一组，经映射σ转化为一条长度为n的q元序列，此序列为一个汉明码码字，进而可得到q元数据序列m，并还原成二进制数据读取。5.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的四元向量中碱基g和c的含量相当于其中符号1和0的含量，恰好为50％；每个四元向量长度为6，故其中连续出现同一符号的长度至多为3，即游程长度不超过3，即高鲁棒性内码集合是一个具有高鲁棒性的内码，并且码字个数为6.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的级联码的所有码字满足gc-平衡和游程约束，具体为：令(π(c1)，π(c2)，...，π(c
n
))为级联码的任意码字，则，(c1，c2,...,c
n
)是一个汉明码码字，对i＝1，...，n，有π(c
i
)是的码字，根据步骤4所述的，π(c
i
)的gc-含量为50％，游程长度不超过3，则(π(c1)，π(c2)，...，π(c
n
))的gc-含量为50％，游程长度不超过6，即的所有码字满足gc-平衡和游程约束。7.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的四元dna码满足gc-平衡和游程约束，具体为：的每个码字也是级联码的码字，故而满足gc-平衡和游程约束。8.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的dna码的码字个数并且当dna码的码长n＝6n，则dna码的冗余度为的冗余度为比
特。9.根据权利要求1所述的基于特殊内码和汉明、vt码的dna优化存储编解码方法，其特征是，所述的译码阶段中dna码纠正单个碱基替换错误，采用汉明码译码算法进行译码，译码复杂度为o(nlogn)，n为码长；所述的译码阶段中dna码纠正单个碱基插入或删除错误，采用四元vt码的译码算法进行译码，译码复杂度为o(n)，n为码长。

技术总结
一种基于特殊内码和汉明、VT码的DNA优化存储编解码方法，包括：参数初始化阶段、预处理阶段、编码阶段和译码阶段。本发明编码后的DNA序列，能够同时满足GC-平衡和游程约束，具有高鲁棒性，而且具备纠错性能，解决现有方法无法做到的：同时达到高鲁棒性、低冗余度，并且纠正碱基替换、插入、删除错误的问题。当码长为n时，本方法的译码复杂度最高为O(nlogn)。本方法的译码复杂度最高为O(nlogn)。本方法的译码复杂度最高为O(nlogn)。


技术研发人员：刘姝 张雅倩 邢朝平
受保护的技术使用者：上海交通大学
技术研发日：2023.04.14
技术公布日：2023/7/12