CN115423096A - DNA-based dynamic equalization system, data storage method and decoding method - Google Patents

Abstract

The invention relates to the field of data storage, and discloses a dynamic equalization system based on DNA, a data storage method and a decoding method, wherein in the process of coding first data to obtain a DNA molecular chain, a plurality of constraints are added to a first address and a second address, so that coded data can be efficiently and accurately read, and if the Hamming distance between the first address and the second address is greater than or equal to half of the length of the first address, the possibility of address selection error in reading is reduced; the prefix of the first address is different from the prefix of the second address and the suffix of the second address, so that the possibility of matching errors in the reading process is avoided; the content of guanine and cytosine in the prefix of each primer accounts for the preset ratio of the total content of guanine, cytosine, adenine and thymine contained in the primer, so that the accuracy is high when the coded data needs to be read and the sequencing is carried out in advance.

Description

DNA-based dynamic equalization system, data storage method and decoding method

technical field

The invention relates to the field of data storage, in particular to a DNA-based dynamic equalization system, a data storage method and a decoding method.

Background technique

As the world enters the information age, under the background of big data, the exponentially increasing amount of data has higher requirements for data storage devices. As a high-density storage medium, DNA has been a natural evolution choice for hundreds of millions of years. At the same time, due to its excellent The structure and properties of the structure, which mainly include the phosphodiester bond and the complementary pairing rules of bases based on hydrogen bonds. This combination structure is stable and can also complete the replication, retrieval, transcription, etc. of information through the catalysis of enzymes. Work, the size of a single DNA base is less than 1 nanometer, and DNA is flexible, and can be curled up and extended in three-dimensional space, and its information storage density is about 1019bit/cm3. Compared with the smallest unit triode of an electronic computer, 5 nanometers is almost At present, the limit of silicon crystal materials, the storage density of hard disk is about 1013Bit/cm3, and the storage density of flash memory is about 1016Bit/cm3. In terms of storage cost, DNA can be stored stably and for a long time at low temperature to room temperature without energy maintenance, and can be stored for at least 100,000 years. At present, the main problems that plague DNA storage come from the high cost of synthesis and sequencing on the one hand, and the lack of effective encoding methods that can maximize the use of the storage space of DNA storage. Therefore, we propose a DNA-based A dynamic equalization system, a data storage method and a decoding method.

Contents of the invention

(1) Solved technical problems

Aiming at the deficiencies of the prior art, the present invention provides a DNA-based dynamic equalization system, data storage method and decoding method to solve the above-mentioned problems.

(2) Technical solution

In order to achieve the above-mentioned purpose, the present invention provides the following technical solutions:

A dynamically balanced system based on DNA, including:

An acquisition module for acquiring the first data, an encoding module for encoding the first data, a Chinese character compression module for compressing storage space and encryption, and a decoding unit for decoding the encoded DNA molecular chain module.

A data storage method based on DNA that can dynamically balance the system, comprising the following steps:

Step 1: Obtain the first data through the acquisition module;

Step 2: Encode the first data through the encoding module to obtain the DNA molecular chain including the number of pseudo-random memory storage times, encoded data, equalization, re-equilibrium, verification, and forward and reverse primers. The forward primer is located in the The 3' end of the DNA molecular chain, and the reverse primer is located at the other end of the DNA molecular chain, that is, the 5' end.

Preferably, the source of the first data may be any existing computer-stored electronic file.

Preferably, the forward primer is subjected to DNA base complementary pairing rules, and after reverse displacement, it is a reverse primer, and the length of the forward primer and the reverse primer are the same;

The content of guanine and cytosine in each primer accounts for a preset ratio of the total content of guanine, cytosine, adenine and thymine contained in the primer.

Preferably, in the second step, when the first data is Chinese character text information, it needs to perform Chinese character compression, including the following steps:

S1: First analyze the target document to obtain the total number of characters K in the document. After eliminating repeated characters, count the number S of characters that appear in the document, and sort them according to the frequency of occurrence of characters from high to low to obtain a character table;

S2: Calculate the length of bases corresponding to Chinese characters, the calculation rule is: according to the number of characters S, calculate a character should use n bases to encode, n needs to ensure >=log4S;

S3: Create a base sequence to mark text characters, the generation method of the base sequence is:

(a) inject the pseudo-random generator with the length of m as a seed, and randomly generate n-bit non-repetitive base sequences;

(b) Screen the generated base sequence. If there are more than 2 consecutive bases, fill and correspond from the character table from bottom to top, otherwise fill and correspond from top to bottom until the base code correspondence of all characters is completed Filling, get the dictionary table after filling, as the dictionary and key of DNA document statistics.

(4) According to the base sequences corresponding to the characters in the dictionary table, all the Chinese characters in the original document are converted into DNA base sequences, and the compressed and encrypted DNA base sequences are obtained.

Preferably, the steps for obtaining the DNA molecular chain are as follows:

Step 1: dividing the first data into several data sub-packets;

The second step: generate a 0/1 random matrix through the pseudo-random number generator of the electronic computer;

Step 3: According to the element value and element position in the random matrix, specify the corresponding data sub-packet for XOR encoding; dynamically balance the encoded data;

Step 4: Record the data in the process, map the running numbers into guanine, cytosine, adenine and thymine according to the preset alphabet, and encode them to obtain and form DNA molecular chain data.

Preferably, the generated DNA chain is checked for errors, and when an error occurs in the generated DNA chain, it can be identified;

Errors that may occur in the DNA chain include: substitution, insertion, and deletion errors;

For insertion and deletion errors, it can be judged by the length of the chain, for replacement errors;

The error correction method of XOR exclusive OR check is adopted, and the XOR result of all base data is finally obtained by performing exclusive OR bit by bit, and it can be judged whether there is a substitution error in the relevant DNA molecular chain.

Preferably, screening is performed on the DNA molecular chains to screen out disorderly folded structures and/or unbounded running numbers and codes in the DNA molecular chains, and dynamically balance the chains that fail the screening.

A decoding method based on a DNA-based dynamic equalization system includes the following content: according to the packaging result, a decoding module is used to perform decoding processing.

(3) Beneficial effects

Compared with the prior art, the DNA-based dynamic equalization system, data storage method and decoding method provided by the present invention have the following beneficial effects:

1. In the DNA-based dynamic balancing system, data storage method, and decoding method, in the process of encoding the first data to obtain DNA molecular chains, various types of data are added to the first address and the second address Constraints, so that the encoded data can be read efficiently and accurately, such as making the Hamming distance between the first address and the second address greater than or equal to half the length of the first address, reducing the reading time The possibility of wrong address selection; the prefix of the first address is different from the prefix of the second address and the suffix of the second address, which avoids the possibility of matching errors during the reading process; each The content of guanine and cytosine in the prefix of the primer accounts for the preset ratio of the total content of guanine, cytosine, adenine and thymine contained in the primer, so that when it is necessary to read the encoded data and perform sequencing in advance, High accuracy.

2. The DNA-based dynamic balance system, data storage method, and decoding method establish a DNA-based storage architecture, which can efficiently complete the conversion between the first data information and the DNA molecular chain, and the conversion efficiency is high.

3. The DNA-based dynamic balance system, data storage method and decoding method, when encoding the data on the DNA double strand, realize the absolute stability of the DNA double strand by setting a dynamic balance method, avoiding the homopolymer, GC Unbalanced content etc.

4. The DNA-based dynamic equalization system, data storage method and decoding method design a random matrix-based coding system, and use a multi-bit packaging method to reduce the complexity of coding and decoding, shorten coding time, and improve translation. Code rate; reduce the order of magnitude of storage redundancy, but also improve the efficiency of encoding and data center data recovery rate, realize highly sensitive random access and accurate rewrite addressing.

5. The DNA-based dynamic equalization system, data storage method and decoding method provide a new set of compression and encryption methods for Chinese character text information to realize efficient storage of Chinese character text.

Description of drawings

Fig. 1 is a schematic flow chart of the steps of a data storage method according to a specific embodiment of the present invention;

Fig. 2 is the schematic diagram of the DNA molecular chain of the specific embodiment of the present invention;

Fig. 3 is a schematic diagram of generating a matrix according to a specific embodiment of the present invention.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Example

Referring to Figures 1-3, the data storage method of the DNA-based dynamically balanced system provided in this embodiment includes the following steps:

Get the first data;

Encode the first data to obtain DNA molecular chains. When the first data is Chinese character text information, it needs to be compressed. Chinese characters are currently the most used text in the world. According to statistics, by 2020, the global The number of people who use Chinese characters exceeds 1.6 billion, accounting for more than 20% of the world's total population. China is currently the country with the largest number of Internet users in the world. (As of September 2019, China has a total of 830 million users connected to the Internet). The amount of Chinese character document resources is huge. The current general electronic storage solution for Chinese characters is UTF-8. A single Chinese character needs to occupy 3-4 bytes. Referring to the ideal storage density of 2bit/nt DNA, each Chinese character needs 12- 16 bases of information space. However, in fact, there are about 5,000 commonly used characters in Chinese characters, and these 5,000 characters can be stored in 4-7 bases. There is undoubtedly a huge room for improvement in storage space. We propose a method for dynamic planning and storage of Chinese characters, which can perform dynamic optimal planning according to the document information to be stored. At the same time, it has very good compression ability and encryption function. The implementation method is:

(1) First analyze the target document to obtain the total number of characters K in the document. After removing repeated characters, count the number of characters S that appear in the document, and sort them according to the frequency of occurrence of characters from high to low to obtain a character table;

(2) Calculate the base length corresponding to the Chinese character. The calculation rule is: according to the number S of characters, a character should be encoded with n bases, and n needs to be guaranteed to be >=log4S.

(3) Establish the base sequence to mark the text characters. The base sequence generation method is: (a) injecting the pseudo-random generator with the length of m as a seed, and randomly generating n-bit non-repetitive base sequences; (b) screening the generated base sequences, if there are 2 If there are more than 1 consecutive bases, then fill and correspond from the character table from bottom to top, otherwise fill and correspond from top to bottom until the base code corresponding to all characters is filled, and the dictionary table after filling is obtained as a dictionary for DNA document statistics and key;

(4) According to the base sequences corresponding to the characters in the dictionary table, all the Chinese characters in the original document are converted into DNA base sequences, and the compressed and encrypted DNA base sequences are obtained.

For the encoding method after obtaining the first data, see the following steps for details:

1) Determine the coding space, which is mainly determined according to the synthesis technology and budget of the DNA synthesizer.

2) Data segmentation, divide L into n chunks (n=S//P+1) to form L1, L2, L3...Ln, and the length of each chunk is p nt;

3) Generate random vectors, use the random function in Python to generate integers in the range of (0, 2n), record the number of times the random generator is generated, and convert the generated integers into n-bit binary data vectors, which start from the low bit (0 ) to high (n-1) elements are 1, indicating whether the chunks of L1, L2...Ln that divide the original file L in step 2) participate in encoding.

4) XOR the chunks corresponding to the position where the element in the generated random vector is 1, and obtain the corresponding Droplet;

5) Every time a random vector is generated, record the number of times the pseudo-random number generator generates and store it in the Times location. The Droplet obtained through step 4 is stored in the Data payload location to form a Packs. Repeat step 4 until Times is exhausted. Storage space, generating a total of 4t Packs;

6) Balance the obtained Packs, first perform condition screening, require homopolymer (no more than 3 consecutive bases), GC content (45%-55%), whether the primer is repeated in the information coding space, if the DNA chain If the screening is passed, the XE bit is marked as 0 (10 A), and the packs are stored as an available chain; if the packs do not pass the screening, the Packs are balanced, and the Adapter sequence is used as the seed of the random generator to generate k A random base with a secondary length of (t+p)nt is XORed with the bases of the packs that have not passed the screening to obtain a new base sequence, and the balance is repeated until the base sequence passes the screening or when When k>410, it means that the XE equalization bit storage space is exhausted. For the chain that passed the screening after k times of equalization, store k in the XE position, and record the base sequence of the packs that passed the balance; for the chain that still cannot be balanced and pass the screening when the XE balance bit space is exhausted, choose to discard.

7) Rebalance. Since the 10nt Xe balance bit is added, the Xe position itself will cause problems such as homopolymers, too high or too low GC content, etc. We have introduced a 2nt rebalance bit to rebalance the XE position , the equalization method is the same as the equalization method for Packs in Section 6). After rebalancing, the number of equalization times is stored in the XEE bit, and the Packs and XE bits are stored as the balanced base sequence, and the chains that do not pass the rebalancing are directly discarded. It is worth noting that rebalancing will no longer change the base sequence of Packs, and at the same time, the judging conditions for rebalancing take into account the homopolymer conditions of the link between XE and Packs and the link between XE and XEE;

8) Assume that there are G DNA strands after step 7, and the storage redundancy is m. In order to ensure the robustness of the final storage content, first randomly select (n+m) strands in G, and then select (n+m) strands randomly in (n +m), randomly select n 1000 times, generate the corresponding degree distribution sequence according to Times (the length of this sequence vector is n), construct it into a (n*n) dimensional matrix, and use the XOR Gaussian elimination method to solve the obtained triangular matrix , it is necessary to ensure that all the elements on the main diagonal of the triangular matrix obtained at least 550 times are 1.

9) Synthesis, the (n+m) chains finally selected in step 8), start from the packs obtained after equalization, go through XE and XEE, perform XOR in units of 3nt, and finally get 3nt bases by XOR Sequence, stored as XC bits appended to XEE.

10) Add forward and reverse primers to the obtained strand to carry out biosynthesis and complete the final DNA storage.

As shown in Figure 2, in this embodiment, the aim is to achieve highly sensitive random access and accurate rewrite addressing. The principle of the proposed method is that each block in random access must be systematically equipped with address sequence primers that allow unique selection and amplification by DNA. Due to information encoding, the length of data information is uncertain. The data chain may be a complete data information, or it may be a segment or extremely scattered chain information. Therefore, primers are added to the front and back ends of the DNA molecular chain for identification. Different chain information. In this embodiment, the length of the DNA molecular chain is 700bps as an example for illustration. In other embodiments, it can be other lengths. The forward primer and the reverse primer are synthesized at both ends of the block sequence, and the forward primer and the reverse primer are They are respectively stored in short blocks with a length of 20bps, and the block sequence is used to store data. The encoding process is to encode the first data of the block sequence to obtain the encoded data, so as to obtain the encoded DNA molecular chain.

In this embodiment, the first data is divided into several second data, and each second data includes a primer, a pseudo-random memory storage number bit, an encoded data bit, an equalization bit, a re-equilibrium bit, a check bit, and a primer is a code describing the synchronization of DNA prefixes, the number of co-coded words selected is controlled by the goal, to make rewriting as simple as possible and to avoid error propagation due to variable code length; "word encoding" operates as follows: first, different textual data information The words in are counted and tabulated in a dictionary, and each word in the dictionary is transformed into a binary sequence long enough to allow encoding of the dictionary. Secondly, use the quaternary model (for example, 00, 01, 10, 11 can be one-to-one correspondence with the bases A (adenine), T (thymine), C (cytosine), and G (guanine) in DNA to encode.

The content of G (guanine) and C (cytosine) in the prefix of each primer accounts for the total content of G (guanine), C (cytosine), A (adenine) and T (thymine) contained in the primer The preset ratio includes but not limited to 45%-55%.

The reason is that because DNA stores information through G (guanine), A (adenine), C (cytosine), T (thymine) and the pairing of A and T, C and G can form a stable Whether it is single-stranded DNA or double-stranded DNA, information can be stored in the form of binary codes. Among them, double-stranded DNA needs to have a prefix with a certain GC content (so that the GC content accounts for about 45% to 55% of the total. %). Because DNA duplexes with 50% GC content are more stable than DNA duplexes with lower or higher GC content, and can have better coverage during sequencing. Since the user information in the encoding is implemented by prefix synchronization, it is important to impose GC content constraints on addresses and their prefixes, because the latter requirement also needs to ensure that all fragments of the encoded data block can have GC content removed;

The decoding steps are as follows:

1) Extract the DNA strand obtained by sequencing according to the forward and reverse Adapter, and judge and analyze the length of the proposed DNA strand. If the length is lower than the target length or higher than the target length, it means that a deletion/insertion error has occurred and discarded this chain;

2) Perform XOR restoration on the data according to the length specified by the XC bit. If the restored data is inconsistent with the data stored in XC, otherwise it means that a replacement error has occurred, and the chain is discarded;

3) If the number of chains K>=n completed by sequencing, the formal decoding process can be started. First, the information is recovered, and the primer information is used as the seed of the random generator, and injected into the pseudo-random generator. Random generator generation times, XEE information recovery, and then according to the XEE pseudo-random generator generation number information obtained after recovery, data recovery of Times and data payload bits, to obtain the original data data information.

4) Generate a corresponding random integer of 0-2**(n) according to the generation times of the pseudo-random number generator corresponding to Times, and convert it into an n-bit binary vector to form a K*n-dimensional binary distribution sequence.

5) The data in the Data payload is converted from base to decimal data, and the sequence matrix of the same degree distribution forms an augmented matrix, and the matrix is solved by using the XOR Gaussian elimination method. (The solution rules are as follows: first combine the K-order matrix D with the Data matrix of K rows and 1 column to construct an augmented matrix, and then judge along the diagonal of the matrix (i from 0-k), if D[i] [i]=1, then judge all the sequences below it along the column, if D[j][i]=1, then XOR all the data in row i and all data in row j. If D[i][ i]=0, then search down along the column, when D[j][i]=1 is found, exchange the two rows, and then search down, if there is still D[j][i]=1, then XOR the i-th row with the j-th row to ensure that an upper triangular matrix is constructed, and the area below the diagonal of the matrix is all 0. Then follow the previous step and reverse the operation to eliminate all the 1 above the diagonal as 0, you can get the only S1...Sk, and Data1...Datak. Complete the decoding process.) Get the data solutions of S1, S2...Sn, convert this part into a binary sequence, and then convert it into a base sequence , you can get ChunksL1, L2...Ln.

6) According to Table 2, complete the decoding of the stored text data.

DNA-based dynamic balancing system, including:

an acquisition module, configured to acquire the first data;

An encoding module, configured to encode the first data to obtain a DNA molecular chain, the DNA molecular chain includes the encoded data, a forward primer and a reverse primer, the forward primer is located at one end of the encoded data, and the The reverse primer is located at the other end of the coded data, and the coded data includes pseudo-random memory storage number bits, coded data bits, equalization bits, re-balanced bits, and check bits;

Chinese character compression module: used to perform special encoding on Chinese characters when the first data is Chinese character text information, and play the role of compressing storage space and encrypting.

The decoding module is used to decode the encoded DNA molecular chain, and restore the decoding to the complete first data.

The embodiment of the present invention also provides a storage medium, the storage medium stores a program, and the program is executed by a processor to complete the DNA-based data storage method.

This embodiment also provides a decoding method based on a DNA-based dynamic equalization system, which includes the following steps: performing decoding processing according to the packing result.

When the DNA is obtained by the above packaging method, when the DNA needs to be read and decoded, only the packaging result needs to be used, which is equivalent to only sending the row position and column position of 1 in the generated matrix G, instead of sending The entire generator matrix G, then only needs to be decoded according to the received row and column positions, and the generated matrix is restored to translate the original data. At this stage, the encoding and decoding process and application of LT codes are packaged and transmitted per unit of raw data, while the transmission of unit data packets will occupy more memory and bandwidth problems when large and appear effective and reliable in the case of large amounts of data. Sexuality has declined. After the above-mentioned processing method, that is, some bits after encoding and transmission are encapsulated, and the original unit number transmission is replaced, the data volume is greatly reduced, the storage space is reduced, the storage redundancy is reduced, and the decoding success rate is improved.

Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications and substitutions can be made to these embodiments without departing from the principle and spirit of the present invention. and modifications, the scope of the invention is defined by the appended claims and their equivalents.

Claims (9)

1. A DNA-based dynamically balanced system, comprising:

the device comprises an acquisition module for acquiring first data, an encoding module for encoding the first data, a Chinese character compression module for compressing storage space and encrypting and a decoding module for decoding a DNA molecular chain obtained by encoding.

2. A data storage method of a dynamic equalization system based on DNA is characterized by comprising the following steps:

the first step is as follows: acquiring first data through an acquisition module;

the second step is that: and coding the first data through a coding module to obtain a DNA molecular chain comprising the storage times of the pseudo random access memory, coded data, balance, rebalancing, checking and forward and reverse primers, wherein the forward primer is positioned at the 3 'end of the DNA molecular chain, and the reverse primer is positioned at the other end of the DNA molecular chain, namely the 5' end.

3. The data storage method of the DNA-based dynamically balanced system according to claim 2, characterized in that: the source of the first data may be any existing computer-stored electronic file.

4. The method for storing data of a DNA-based dynamically balanced system according to claim 2, characterized in that: the forward primer is subjected to a DNA base complementary pairing rule, and is a reverse primer after reverse displacement, and the lengths of the forward primer and the reverse primer are consistent in the length aspect;

the content of guanine and cytosine in each primer accounts for the preset ratio of the total content of guanine, cytosine, adenine and thymine in the primers.

5. The data storage method of the DNA-based dynamically balanced system according to claim 2, characterized in that: in the second step, when the first data is Chinese character text information, chinese character compression is required to be carried out on the first data, and the method comprises the following steps:

s1: analyzing a target document to obtain the total number K of characters in the document, counting the number S of characters appearing in the document after removing repeated characters, and sequencing from high to low according to the occurrence frequency of the characters to obtain a character table;

s2: calculating the length of the base corresponding to the Chinese character according to the following calculation rule: calculating that one character should be coded by n bases according to the number S of the characters, wherein n is required to ensure > = log4S;

s3: establishing a base sequence to label the text characters, wherein the generation mode of the base sequence is as follows:

(a) Injecting the length of m as a seed into a pseudorandom generator to randomly generate n-bit nonrepeating base sequences;

(b) Screening the generated base sequence, if more than 2 continuous bases exist, filling from bottom to top from the character table for correspondence, otherwise, filling from top to bottom for correspondence until the base codes of all the characters are correspondingly filled, and obtaining a filled dictionary table which is used as a dictionary and a key for DNA document statistics;

(4) And according to the base sequence corresponding to the characters in the dictionary table, all Chinese character characters in the original document are converted into DNA base sequences, and the compressed and encrypted DNA base sequences are obtained.

6. The data storage method of the DNA-based dynamically balanced system according to claim 2, characterized in that: the steps for obtaining the DNA molecular chain are as follows:

the first step is as follows: dividing the first data into a plurality of data sub-packets;

the second step is that: generating a 0/1 random matrix by a pseudo random number generator of an electronic computer;

the third step: according to the element values and the element positions in the random matrix, appointing corresponding data sub-packets to carry out XOR coding; dynamically balancing the coded data;

the fourth step: and recording data in the process, mapping the running numbers and the running numbers into guanine, cytosine, adenine and thymine according to a preset alphabet, and coding to obtain and form DNA molecular chain data.

7. The method for storing data of a DNA-based dynamically balanced system according to claim 2, characterized in that: the generated DNA chain is subjected to error checking, and when the generated DNA chain has an error, the generated DNA chain can be identified;

possible errors in the DNA strand include: replacement, insertion, deletion errors;

for insertion and deletion errors, judgment can be performed through the length of the chain, and for replacement errors;

and (3) performing XOR according to bits by adopting an error correction mode of XOR verification to finally obtain the result of XOR of all base data, and judging whether the related DNA molecular chain has a substitution error.

8. The data storage method of the DNA-based dynamically balanced system according to claim 6, characterized by: and screening the DNA molecular chain to screen out a disordered folding structure and/or unbounded running numbers and codes in the DNA molecular chain, and dynamically balancing the chains which do not pass the screening.

9. A method for decoding a DNA-based dynamically-equalized system, comprising: and decoding by using a decoding module according to the packaging result.

Images