满足GC局部平衡和游程约束的高码率DNA编码方法及系统

本发明属于数据存储领域，尤其涉及一种满足gc局部平衡和游程约束的高码率dna编码方法及系统。

背景技术：

1、近年来，dna存储技术由于其具有存储密度大、保存时间长、维护成本低、容易获取等优点引起了广泛关注。基于dna的数据存储是一种能长期保存数字数据的新方法。dna存储是指，使用预先设计好的编码方案将信息序列编码为腺嘌呤(a)、胸腺嘧啶(t)、鸟嘌呤(g)、胞嘧啶(c)四种碱基组成的dna序列，然后将这些序列合成寡核苷酸或长dna片段，以允许长期储存。为了检索数据，利用dna测序从合成的dna中获得原始atcg序列。

2、在dna的合成和测序过程中，碱基序列经常会出现错误，而dna存储过程中发生错误的概率与dna的序列结构密切相关。连续相同的碱基被称为一个碱基游程，有研究表明，一个长度超过六的碱基游程会显著增加替换和删除错误的发生率，因此在dna链中应该避免出现较长的游程。另外，gc含量是指一个dna链中碱基g和c占总碱基数的比例，同样有研究证明，当gc含量过高或过低时，合成和测序过程中会产生更多的错误，因此大部分研究都是控制dna链中gc含量在50％左右，这也被称为gc平衡。此外，gc平衡可以分为gc全局平衡和gc局部平衡，gc全局平衡是指整个dna链中的gc含量达到平衡，gc局部平衡是指给定整数在任意长度为的子序列中gc含量也达到平衡，显然gc局部平衡同时也是gc全局平衡，gc局部平衡经常会在pcr扩增时用到。

3、因此，在进行dna编码时，需要额外添加生物约束的限制，从而更贴合实际的存储需求。但现在大多数dna编码的方法都不具备生物约束性质，或者具备少量约束性质的同时牺牲了大量码率，对于能够具备多个生物约束性质的高码率dna编码方法仍然缺乏。

技术实现思路

1、针对现有技术存在的问题，本发明提供了一种满足gc局部平衡和游程约束的高码率dna编码方法及系统。

2、本发明是这样实现的，一种满足gc局部平衡和游程约束的高码率dna编码方法，该方法包括：

3、步骤1：定义一个满足gc∈-全局平衡并满足-游程限制的4元码并通过划分子集和数学归纳法的思想计算的具体码字个数；

4、步骤2：对中码字进行大小排序，建立与整数之间的映射，根据大小排序实现对的编码和解码；

5、步骤3：对的码字进行重新组合，构造一个满足gc(m，δ)-局部平衡并满足-游程限制的4元码并可以通过一个整数序列对进行编解码。

6、进一步，所述步骤1具体包括：

7、步骤1.1：构造到dna碱基集∑dna＝{a，t，c，g}的双射τ：τ(0)＝c，τ(1)＝g，τ(2)＝a，τ(3)＝t；用[n]表示{1，2，...，n}的整数集；

8、步骤1.2：设上长度为n的4元序列为：ci表示序列c的第i位坐标；定义c的gc重量为wtgc(c)＝|{i∈[n]：ci＝0}|+|{j∈[n]：cj＝1}|，如果wtgc(c)∈[(0.5-∈)n，(0.5+∈)n]，其中0＜∈＜1，则称码字c满足gc-∈全局平衡；如果对于c中的任何一个长度为m的子序列b都有，wtgc(b)∈[(0.5-∈)m，(0.5+∈)m]，则称码字c满足gc(m，∈)-局部平衡；如果码字c可以被分成t个长度为的连续子序列，即c＝(c1，c2，...，ct)，并且每个子序列ci满足则称码字c满足-分段平衡；

9、步骤1.3：连续相同的元素称作为一个游程，任何一个序列都可以由若干个游程组成，如果一个序列c的任何一个游程的长度都不超过那么称序列c满足-游程限制；这里用来代表同时满足gc∈-全局平衡和-游程限制的4元码字集合；

10、步骤1.4：用s代表上所有长度不超过的游程集合，如果s∈s，用γ(s)来代表组成s这个游程的元素，则用a(n，s，g)代表长度为n，最后一个游程为s，且gc重量为g的所有码字集合，然后用φ(n，s，g)代表其的码字个数，即φ(n，s，g)＝|a(n，s，g)|；

11、步骤1.5：给出定理一：可以被分解为

12、

13、其中，φ(n，s，g)的计算方法为：

14、

15、其中ω(·)当括号里的条件为真时为1，反之为0。

16、进一步，所述定理一的证明如下：

17、首先，显然可以分成若干个无交集的a(n，s，g)，对于任意的s∈s，g∈[(0.5-∈)n，(0.5+∈)n]；当n≤|s|时，φ(n，s，g)的值可以很容易通过定义得到；而当n＞|s|时，采用了递推关系进行计算，设码字c＝c′||s，||表示两个序列的级联，即c的最后一个游程为s，除去游程后的序列为c′，用s′代表c′的最后一个游程，满足γ(s′)≠γ(s)，那么c∈a(n，s，g)当且仅当c′∈a(n-|s|，s’，g-wtgc(s))，因此最后一个等式也可以得到；利用定理一可以计算得到具体的码字个数

18、进一步，所述步骤2具体包括：

19、步骤2.1：对于s∈s，定义θ(s)＝γ(s)+4(|s|-1)；对于二元组定义(s′，g′)＜(s，g)，如果g′＜g或者g′＝g同时θ(s′)＜θ(s)；对于任意两个不同的四元序列最后一个游程分别为s1和s2，定义c1＜c2，如果满足以下两个条件之一：

20、(1)(s1，wtgc(c1))＜(s2，wtgc(c2))

21、(2)

22、其中，λt(c)代表码字c的前t位；

23、步骤2.2：根据步骤2.1的定义，任意任意两个不同的四元序列只有c1＜c2或c1＞c2两种情况，因此我们可以对中所有码字进行大小排序；那么一定存在一个双射λ：

24、

25、λ表示整数k与中第k个最小的码字c的映射；下面介绍如何计算映射结果；

26、步骤2.3：令那么对于任意的整数存在一个函数可以返回中第k个最小的码字；给出引理二：对于任意的整数一定存在一个唯一的满足且那么有

27、

28、其中g′＝g-wtgc(s)；证明如下：

29、令φ0＝0，令

30、

31、其中i∈[1，m]；很容易发现φi随着i单调递增，所以对于任意的整数一定存在一个i∈[1，m]使得那么可以得到a(n，si，gi)中第个最小的序列；又因为a(n，si，gi)中的序列具有相同的最后一个游程si,进一步可以得到

32、

33、证明完毕；

34、步骤2.4：同理，存在一个函数可以返回c在中的顺序；类似于步骤2.3，给出引理三：对于任意一个码字令s代表c的最后一个游程，g＝wtgc(c)，那么有

35、

36、其中g′＝g-wtgc(s)；这里证明与步骤2.3类似，不再赘述；

37、步骤2.5：根据引理二和引理三，可以实现与中第k个最小的码字之间的编解码；例如：设码长为4，满足∈＝0.1的全局平衡和的游程限制，如果要得到中第60个最小的码字；将计算的游程合并，最终得到中第60个最小的码字为c＝3112；同理，如要计算c＝3112在中的顺序，将计算得到的累加，得到c在中的顺序为k＝1+1+18+40＝60。

38、进一步，所述步骤3具体包括：

39、步骤3.1：给出引理四：如果码字满足-分段平衡，那么码字c同样满足gc(m，δ)-局部平衡，其中并且

40、步骤3.2：定义根据步骤1.2中的定义，满足gc(n，∈)-分段平衡；根据引理四，同时满足gc(m，δ)-局部平衡，其中2n＜m≤nt，另外，满足-游程限制；

41、步骤3.3：类似步骤2，可以用一个整数序列进行编解码；对于任意一个码字c＝(c1，c2，...，ct)，其中令λ为步骤2中定义的映射，λ-1为对应的逆映射，则λ-1(c)＝λ(c1，c2，...，ct)＝(k1，k2，..，kt)，其中因此利用步骤2中的编解码算法，同样可以实现(k1，k2，...，kt)与(c1，c2，...，ct)之间的编码；

42、步骤3.4：具有极高的码率，可以接近码率上限2，当∈＝0.1，时，不同码长下的码率如下：(码率计算方法为log2|cl|/nt)。

43、本发明另一目的在于提供一种实施所述满足gc局部平衡和游程约束的高码率dna编码方法的满足gc局部平衡和游程约束的高码率dna编码系统，该系统包括：

44、定义计算模块，用于定义一个满足gc∈-全局平衡并满足-游程限制的4元码并通过划分子集和数学归纳法的思想计算的具体码字个数；

45、排序编码和解码模块，与定义计算模块连接，用于对中码字进行大小排序，建立与整数之间的映射，根据大小排序实现对的编码和解码；

46、组合解码模块，与排序编码和解码模块连接，用于对的码字进行重新组合，构造一个满足gc(m，δ)-局部平衡并满足-游程限制的4元码并可以通过一个整数序列对进行编解码。

47、本发明另一目的在于提供一种计算机设备，所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行所述满足gc局部平衡和游程约束的高码率dna编码方法的步骤。

48、本发明另一目的在于提供一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行所述满足gc局部平衡和游程约束的高码率dna编码方法的步骤。

49、本发明另一目的在于提供一种信息数据处理终端，所述信息数据处理终端用于实现所述满足gc局部平衡和游程约束的高码率dna编码系统。

50、结合上述的技术方案和解决的技术问题，本发明所要保护的技术方案所具备的优点及积极效果为：

51、第一、本发明提出了一种同时满足gc局部平衡和游程约束的高码率dna编码方法，该方法利用了数学归纳法的思想，对满足约束的码字进行了明确计算，并通过排序实现了对码字的编解码，这种编码方法具有极高的码率，可以接近码率上限。

52、第二，现在大多数dna编码的方法都不具备生物约束性质，或者具备少量约束性质的同时牺牲了码率，对于能够具备多个生物约束性质的高码率dna编码方法仍然缺乏，本发明有效解决了目前的问题，采用数学归纳法的思想，对满足约束的码字进行了明确计算，并通过排序实现了对码字的编解码，这种编码方法具有极高的码率，可以接近码率上限。

53、第三，作为本发明的权利要求的创造性辅助证据，还体现在以下几个重要方面：

54、(1)本发明的技术方案转化后的预期收益和商业价值为：

55、本发明构造了满足两种严苛的生物约束条件的dna编码方法，具有极高的码率，同时提供了有效的编译码算法，贴合实际应用需求，可以应用于某些对生物约束和码率要求高的dna存储系统中，能够有效降低dna序列在合成测序过程中的错误率，并具有较高的可用性。

56、(2)本发明的技术方案填补了国内外业内技术空白：

57、目前大多数的dna编码方法都不具备生物约束性质，或者具备少量约束性质的同时牺牲了大量码率，本发明构造了一种新的编码方法，不仅满足gc局部平衡和游程约束，而且具有极高码率，同时还提供了一种有效的编译码方法，填补了dna编码领域的技术空白。

58、(3)本发明的技术方案解决了人们一直渴望解决、但始终未能获得成功的技术难题：

59、在dna编码中，为了降低错误概率，dna序列需要满足一些特定的生物约束条件。然而，生物约束与码率之间存在着一定的妥协，满足的生物约束越多、约束条件越严苛，序列码率就会越低，这也是dna编码的痛点。本方案构造的编码方法同时满足了两种严苛的约束条件：gc局部平衡和游程约束，并且具有接近上界的码率，同时保证了存储系统的可用性和可靠性，很好地克服了这一痛点。

60、第四，在生物信息学和基因工程领域，对dna序列进行高效且准确的编码和解码一直是技术挑战。传统的dna编码方法往往难以同时满足gc局部平衡(即序列中鸟嘌呤g和胞嘧啶c的比例在局部区域内保持平衡)和游程约束(即序列中连续相同碱基的最大长度受到限制)的要求。这种局限性导致了编码效率低下、解码错误率高以及潜在的生物功能干扰，严重制约了dna数据存储和基因编辑等应用的发展。

61、本发明提出了一种满足gc局部平衡和游程约束的高码率dna编码方法，通过精妙的算法设计和数学归纳法的应用，有效地解决了上述问题。该方法首先定义了一种满足全局平衡的4元码，并通过划分子集和数学归纳法计算出具体的码字个数。接着，通过对码字进行大小排序并建立与整数的映射关系，实现了高效且准确的编码和解码过程。最后，通过对码字的重新组合，构造出一个满足局部平衡和游程限制的4元码，进一步提高了编码的效率和准确性。

62、本发明的显著技术进步主要体现在以下几个方面：首先，通过引入gc局部平衡和游程约束的概念，本发明提高了dna编码的准确性和可靠性，降低了生物功能干扰的风险。其次，通过采用数学归纳法和整数映射的方法，本发明实现了高效且准确的编码和解码过程，显著提高了编码效率。最后，本发明的编码方法具有极高的码率，接近理论上限，为dna数据存储和基因编辑等应用提供了强有力的技术支持。

63、本发明的应用前景广阔，不仅可以在生物信息学和基因工程领域发挥重要作用，还可以拓展到数据存储、信息安全等领域。通过采用本发明的dna编码方法，我们可以更加高效、准确地存储和传输生物信息数据，为生命科学研究和应用提供有力的支持。同时，本发明的提出也为dna数据存储和基因编辑等领域带来了新的技术思路和解决方案，具有重要的理论意义和实践价值。

技术特征：

1.一种满足gc局部平衡和游程约束的高码率dna编码方法，其特征在于，该方法包括：

2.如权利要求1所述的方法，其特征在于，步骤1具体包括：

3.如权利要求1所述的方法，其特征在于，步骤3具体包括：

4.如权利要求1至4中任一项所述的方法，其特征在于，还包括：

5.一种实施如权利要求1-4任意一项所述编码方法的满足gc局部平衡和游程约束的高码率dna编码系统，其特征在于，该系统包括：

6.一种计算机设备，其特征在于，所述计算机设备包括存储器和处理器，所述存储器存储有计算机程序，所述计算机程序被所述处理器执行时，使得所述处理器执行如权利要求1-4任意一项所述满足gc局部平衡和游程约束的高码率dna编码方法的步骤。

7.一种计算机可读存储介质，存储有计算机程序，所述计算机程序被处理器执行时，使得所述处理器执行如权利要求1-4任意一项所述满足gc局部平衡和游程约束的高码率dna编码方法的步骤。

8.一种信息数据处理终端，其特征在于，所述信息数据处理终端用于实现如权利要求5所述满足gc局部平衡和游程约束的高码率dna编码系统。

技术总结
本发明属于数据存储领域，公开了一种满足GC局部平衡和游程约束的高码率DNA编码方法及系统，该方法包括：步骤1：定义一个满足GC<subgt;∈</subgt;‑全局平衡并满足‑游程限制的4元码并通过划分子集和数学归纳法的思想计算的具体码字个数；步骤2：对中码字进行大小排序，建立与整数之间的映射，根据大小排序实现对的编码和解码；步骤3：对的码字进行重新组合，构造一个满足GC(m，δ)‑局部平衡并满足‑游程限制的4元码并可以通过一个整数序列对进行编解码。本发明利用了数学归纳法的思想，对满足约束的码字进行了明确计算，并通过排序实现了对码字的编解码，这种编码方法具有极高的码率，可以接近码率上限。

技术研发人员：吴克楠,刘姝
受保护的技术使用者：电子科技大学
技术研发日：
技术公布日：2024/9/23