[go: up one dir, main page]

WO2021229184A1 - Procédé et dispositif de décodage de données stockées dans un système de stockage à base d'adn - Google Patents

Procédé et dispositif de décodage de données stockées dans un système de stockage à base d'adn Download PDF

Info

Publication number
WO2021229184A1
WO2021229184A1 PCT/FR2021/050826 FR2021050826W WO2021229184A1 WO 2021229184 A1 WO2021229184 A1 WO 2021229184A1 FR 2021050826 W FR2021050826 W FR 2021050826W WO 2021229184 A1 WO2021229184 A1 WO 2021229184A1
Authority
WO
WIPO (PCT)
Prior art keywords
nucleotide
nucleotides
decoding
dna
probability density
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/FR2021/050826
Other languages
English (en)
Inventor
Laura Conde-Canencia
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Universite de Bretagne Sud
Original Assignee
Universite de Bretagne Sud
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Universite de Bretagne Sud filed Critical Universite de Bretagne Sud
Priority to US17/925,562 priority Critical patent/US20230187024A1/en
Priority to EP21731261.0A priority patent/EP4150114A1/fr
Publication of WO2021229184A1 publication Critical patent/WO2021229184A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/65—Purpose and implementation aspects
    • H03M13/6597—Implementations using analogue techniques for coding or decoding, e.g. analogue Viterbi decoder
    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
    • G16B30/00—ICT specially adapted for sequence analysis involving nucleotides or amino acids
    • G16B30/20—Sequence assembly
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01N—INVESTIGATING OR ANALYSING MATERIALS BY DETERMINING THEIR CHEMICAL OR PHYSICAL PROPERTIES
    • G01N33/00—Investigating or analysing materials by specific methods not covered by groups G01N1/00 - G01N31/00
    • G01N33/48—Biological material, e.g. blood, urine; Haemocytometers
    • G01N33/483—Physical analysis of biological material
    • G01N33/487—Physical analysis of biological material of liquid biological material
    • G01N33/48707—Physical analysis of biological material of liquid biological material by electrical means
    • G01N33/48721—Investigating individual macromolecules, e.g. by translocation through nanopores
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F30/00—Computer-aided design [CAD]
    • G06F30/20—Design optimisation, verification or simulation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/12—Computing arrangements based on biological models using genetic models
    • G06N3/123—DNA computing
    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
    • G16B40/00—ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
    • G16B40/10—Signal processing, e.g. from mass spectrometry [MS] or from PCR
    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
    • G16B50/00—ICT programming tools or database systems specially adapted for bioinformatics
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1105—Decoding
    • H03M13/1111—Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/11—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits using multiple parity bits
    • H03M13/1102—Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
    • H03M13/1148—Structural properties of the code parity-check or generator matrix
    • H03M13/1171—Parity-check or generator matrices with non-binary elements, e.g. for non-binary LDPC codes
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/61—Aspects and characteristics of methods and arrangements for error correction or error detection, not provided for otherwise
    • H03M13/611—Specific encoding aspects, e.g. encoding by means of decoding
    • C—CHEMISTRY; METALLURGY
    • C12—BIOCHEMISTRY; BEER; SPIRITS; WINE; VINEGAR; MICROBIOLOGY; ENZYMOLOGY; MUTATION OR GENETIC ENGINEERING
    • C12Q—MEASURING OR TESTING PROCESSES INVOLVING ENZYMES, NUCLEIC ACIDS OR MICROORGANISMS; COMPOSITIONS OR TEST PAPERS THEREFOR; PROCESSES OF PREPARING SUCH COMPOSITIONS; CONDITION-RESPONSIVE CONTROL IN MICROBIOLOGICAL OR ENZYMOLOGICAL PROCESSES
    • C12Q1/00—Measuring or testing processes involving enzymes, nucleic acids or microorganisms; Compositions therefor; Processes of preparing such compositions
    • C12Q1/68—Measuring or testing processes involving enzymes, nucleic acids or microorganisms; Compositions therefor; Processes of preparing such compositions involving nucleic acids
    • C12Q1/6869—Methods for sequencing
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2111/00—Details relating to CAD techniques
    • G06F2111/08—Probabilistic or stochastic CAD

Definitions

  • TITLE method and device for decoding data stored in a DNA-based storage system
  • the present description relates to a device for decoding data stored in a storage system based on DNA (deoxyribonucleic acid) with a nanopore sequencer and a corresponding decoding method.
  • DNA sequencing One of the methods of reading data stored in DNA-based storage systems is known as DNA sequencing ("DNA sequencing"). Their goal is to determine the exact nucleotides and their order in a DNA sequence that encodes digital data.
  • nanopore sequencing is based on the detection of changes in an ionic current when a DNA sequence passes through a hole at the nanoscale.
  • Each nucleic base or nucleotide causes a different magnitude of current drop due to its different atomic structure. This makes it possible to identify the nucleotide passing through the nanopore at a given time.
  • the main advantage of nanopore sequencers is that they can read long sequences in a single step, up to several tens of thousands of nucleotides.
  • micro-array based synthesis makes it possible to synthesize DNA sequences of lengths up to 200 nucleotides, at a cost of approximately $ 0.001 per nucleotide.
  • its major drawback is its high error rate. From a general point of view, we can affirm that the current synthesis methods combine either a high cost and a high precision or on the contrary a low high cost and a low precision, and the current research tries to reduce the gap between these. two extremes.
  • the main error-generating events in DNA synthesis are simple substitutions [1] [2] [10] of one nucleotide for another and the substitution error rates depend mainly on performance and the cost of the technology [13]
  • a method for decoding a sequence of binary data encoded by a sequence of nucleotides to be decoded comprising B types of DNA nucleotides, B being an integer equal to 2, 3 or 4 , the decoding method comprising
  • the probability density function is a Gaussian probability density function and the flexible decoding algorithm is based on a modeling of the current drop measurement produced by the one-variable nanopore sequencer noise modulated by pulse-amplitude modulation at B discrete levels, each level corresponding to an average value of the probability density function obtained for a given type of nucleotide, the modulated noise variable being noisy by B channels of additive Gaussian white noise corresponding respectively to the statistical distributions obtained for the B types of nucleotides.
  • the nanopore sequencer is thus modeled as an asymmetric communication channel.
  • the error correcting code is a turbo code or an LDPC, Low-Density Parity-Check code decoding algorithm.
  • the flexible decoding algorithm is for example a turbo-code algorithm of the MAP, Message type
  • the flexible decoding algorithm is, for example, a Min-Sum algorithm for LDPC codes or a belief propagation (BP) algorithm for LDPC codes.
  • BP belief propagation
  • the number B of nucleotide type is equal to 4 and the flexible decoding algorithm with error correcting code is applied to symbols in a Galois body of order 4, each symbol in the Galois body of order 4 corresponding to one nucleotide.
  • the order in which the nucleotides are associated with the symbols in the Galois body of order 4 corresponds to the inverse order of the average values of the probability density functions of the current drop amplitudes obtained for the different types of nucleotides.
  • the reliability information for a measurement value y k and a type of nucleotide i is calculated as follows: [Math.201] where Ci is the mean value of the probability density function and ⁇ i the standard deviation of the probability density function obtained for the type of nucleotide i.
  • a decoding device comprising means for implementing the steps of a method according to the first aspect.
  • the means can be hardware and / or software means configured to implement the functions defined in this document for the decoding device.
  • the decoding device comprising at least one memory and at least one processor, the memory storing program instructions configured to cause said decoding device to execute the steps of a method according to the first aspect when the program instructions are executed by the processor.
  • a computer program comprising program instructions for the execution of the steps of a method according to the first aspect when said program is executed by a computer.
  • a recording medium readable by a computer on which is recorded a computer program comprising program instructions for the execution of the steps of a method according to the first aspect when said program is executed by a computer.
  • a DNA-based data storage system comprising a nanopore sequencer and a decoding device according to the second aspect.
  • FIG.1 illustrates aspects of the calculation of parity blocks in a coding method according to one or more embodiments
  • FIG.2 is a schematic representation of a DNA-based storage system according to one or more embodiments
  • FIG.3 represents examples of statistical distributions of current drop measurements obtained for different types of nucleotides in a nanopore sequencer
  • FIG.4 represents a table of parameters (mean and standard deviation) of the statistical distributions presented in Fig. 3;
  • fig.5] represents a flowchart of a flexible decoding method according to one or more embodiments.
  • DNA-based data storage systems with nanopore sequencers will be described in more detail. These storage systems are based on the use of quaternary codes based on graphs defined on Galois fields of order 4 and associated decoding algorithms based on "soft" samples ("soft samples”). -saxonne). These samples are the products of nanopore sequencers, the main characteristic of which is the passage of the DNA sequence at a controlled rate through one or more nanopores.
  • each DNA nucleotide is represented as an element of a Galois body of order 4.
  • Likelihood calculations are introduced to take into account an asymmetric DNA channel pattern and ion current drops.
  • An algorithm of the “Min-Sum” type suitable for a quasi-optimal decoding of low complexity is presented. The results of the simulations show that the error correction method proposed in this document is capable of guaranteeing an almost error-free reading of data with regard to the substitution errors and with ideal conditions for the synthesis.
  • the contributions described in this document relate specifically to the correction of substitution errors produced during nanopore sequencing.
  • the first contribution concerns the use of a quaternary encoding / decoding scheme using a representation of DNA nucleotides as elements of a Galois field of order 4 (this also includes the correspondence with the digital information to be stored in the system) and the use of non-binary correction codes defined in this Galois field. This is to avoid the quaternary to binary conversions that would be required when using a binary encoding / decoding scheme.
  • the second contribution concerns the use of the statistical distributions of the amplitudes of the ionic current signals as "flexible" intrinsic information, that is to say as reliability information.
  • Likelihood calculations at the decoder based on graphs which take into account these amplitudes and the specific model of asymmetric DNA channel without memory (ie the output at a given moment, depends only on the input at that moment but not on the entered at previous or later times).
  • the coding approaches known in the state of the art [8] [15] for this problem do not make it possible to exploit the "soft" information provided by the nanopore system.
  • the error correcting codes likely to use this intrinsic information can be LDPC (Low-Density Parity-Check) codes or turbo-codes.
  • a Galois field GF (q) is a finite set of q elements of which any element can be described as a function of a primitive element, noted here a.
  • the elements (or symbols) of the Galois field GF (q) are denoted ⁇ 0, ⁇ 0 , ⁇ 1 , ... a q-2 ⁇ .
  • LPDC codes are error correcting codes in the category of linear block codes, the parity matrix of which has the property of being sparse (in English, "low-density parity check matrix”), c ' that is, it contains only a small number of undamaged items compared to its total number of items.
  • LDPC codes can in fact be characterized, like linear block codes, by a so-called parity matrix, generally denoted H.
  • the dimensions M x N of the parity matrix correspond, for the number of rows M, to the number of parity constraints of the code, and for the number of columns N, to the length of the code words of the code considered (i.e. the number of symbols in a code word).
  • the elements of a parity matrix of a non-binary LDPC code will belong to a non-binary (q> 2) Galois field GF (q) and the matrix products of the above equations will be performed using the laws addition and multiplication of the field GF (q), denoted respectively in the following.
  • a non-binary LDPC code is a linear code associated with an input data block and defined by a very sparse parity check matrix H whose non-harmful elements belong to a finite field GF (q), where q > 2.
  • q finite field GF
  • d c the number of 1 in a row of the matrix H
  • d v the number of 1 in a column of matrix H.
  • a representation of the parity matrix of the code uses a two-part graph called a “Tanner graph”.
  • this representation maps, by means of branches, M nodes, called “parity nodes” (in English “Check Node” or “CN”) with N nodes, called “Variable nodes” (in English “Variable Node” or “VN”).
  • Each non-zero element of the parity matrix is represented in the corresponding Tanner graph by a branch joining the parity node corresponding to the row of the element in the matrix H to the variable node corresponding to the column of the element in the matrix H.
  • Each parity node of the graph thus represents a parity equation determined by the branches which connect it to the nodes of variables.
  • parity check matrix H 100 is shown in the left part of FIG. 1 and the corresponding Tanner graph 110 and represented in the right part of FIG. 1.
  • the parity matrix H is defined in the Galois field GF (4) whose elements are denoted ⁇ 0, ⁇ 0 , ⁇ 1 , ⁇ 2 ⁇ .
  • the three parity equations corresponding respectively to the three parity nodes of this graph are:
  • the Tanner graph 110 represents the iterative processing applied to each code word to be decoded.
  • the variable node VN k receives a vector ⁇ k calculated by a calculation block 10 k from the input y k to decode the symbol x k of a code word X.
  • This reliability information are for example based on the LLR (Log
  • the input vector ⁇ k is thus defined as follows: [Math.14]
  • the decoded code word is generated by the variable nodes after iteration (s) in the Tanner graph.
  • a decoded symbol of a decoded code word corresponds to the first value of the output vector (the symbols of the output vector being sorted in ascending order of LLR value, the first row of the output vector thus comprising the highest LLR value and the associated decoded symbol), that is to say the most probable value in GF (4) or the one with the lowest decoding error.
  • the variable node VN k thus receives a decoded vector containing the decoded value for the symbol X k of the code word X.
  • the decoded symbol identifies a type of nucleotide among the B types of DNA nucleotides and corresponds to the measurement value current drop.
  • Tanner's graphical representation can be exploited for the implementation of decoding algorithms whose efficiency has been shown on graph models, such as the so-called “belief propagation” algorithm (in English, “Belief propagation”, or “BP”) or message passing type algorithms (in English, “message passing”, or MP).
  • BP Belief propagation
  • MP message passing type algorithms
  • a message can be an intrinsic message (input data vector generated from channel information at the input of the decoder) or an extrinsic message (data vector generated during an iteration applied to an intrinsic message, these extrinsic messages are the messages exchanged between parity nodes and variable nodes).
  • Iterative LDPC code decoding algorithms based on a Tanner graph, in particular using the exchange of messages between the parity nodes and the variable nodes of the Tanner graph corresponding to the LPDC code considered have thus been developed.
  • These decoding algorithms can more generally be implemented or adapted for the decoding of all linear block codes likely to be represented by a bipartite graph comprising a set of parity nodes and a set of variable nodes.
  • Tanner graph of a non-binary LDPC code is generally much more sparse than a corresponding Tanner graph of a binary LDPC code having the same bit rate and the same code length in bits [19] [20] ,
  • the elements of GF (4) are thus denoted ⁇ 0, ⁇ 0 , ⁇ 1 , ⁇ 2 ⁇ , where a is the primitive element of this Galois field.
  • the elements of GF (4) are also called symbols.
  • the basic building blocks of DNA are the four nucleotides: Adenine (A), Cytosine (C), Guanine (G) and Thymine (T). Each nucleotide is represented by a symbol in GF (4).
  • the input binary data sequence is converted to a quaternary data or symbol sequence in GF (4).
  • LDPC coding a C code word with redundancy is obtained for each input code word, the C code word with redundancy comprising N symbols in GF (4) and consisting, on the one hand, of a block of
  • K symbols in GF (4) corresponding respectively to the K input symbols and, on the other hand, a parity check block of M symbols in GF (4) calculated on the basis of the coefficients of the parity matrix.
  • the LDPC coding is repeated for each input code block or word so as to obtain a succession of code words with redundancy.
  • a succession of code words with redundancy is then synthesized so as to obtain a DNA sequence encoding the input binary data blocks.
  • a nanopore device is then used to convert the DNA sequence encoding the input binary data blocks into a series of voltage drop amplitude measurement values.
  • a symbol X k decoded in GF (4) is obtained for each measurement y k of the current drop amplitude.
  • the decoded symbol corresponds to the most probable symbol, the one for which the decoding error is the smallest.
  • the flexible decoding algorithm can be an LDPC code decoding algorithm (for example, a Min-Sum algorithm for LDPC codes or a BP algorithm, Belief Propagation) or turbo-codes (for example, a MAP algorithm, Message Parsing Algorithm).
  • LDPC code decoding algorithm for example, a Min-Sum algorithm for LDPC codes or a BP algorithm, Belief Propagation
  • turbo-codes for example, a MAP algorithm, Message Parsing Algorithm.
  • the reliability values used are based on the statistical distributions of current drop measurements produced during the passage through a nanopore sequencer of a reference sequence composed of nucleotides of a type considered. (excluding other types of nucleotides).
  • the messages exchanged comprise the symbols of the code words processed and a reliability information item associated with each symbol.
  • reliability information is calculated from a measurement value y k supplied by the nanopore device.
  • This reliability information is based on the LLR (Log Likehood Ratio) function as explained in more detail in this document.
  • LLR Log Likehood Ratio
  • the messages exchanged include probability densities include two densities, one for the value "0" and the other for the value "1".
  • the messages or data vectors comprise, for example, pairs of binary values with which are respectively associated likelihood (or reliability) values.
  • the LDPC code considered is non-binary, and the symbols of the code words have values in the body of Galois GF (4).
  • a parity node of a decoder for non-binary LDPC codes of a code with values in the Galois body GF (q) thus receives d c input messages and generates d c output messages.
  • BP Belief Propagation
  • an output is constructed by selecting the q best combinations among q to the power of- 1. This leads to a computational complexity of l 'order of 0 (q 2 ).
  • the BP decoding algorithm can also be considered in the frequency domain. We then speak of a BP algorithm based on the Fourier transformation (in English, “Fourier Transform-based BP algorithm”). The passage in the frequency domain makes it possible to reduce the complexity of the BP algorithm, to reach a complexity of the order of 0 (d c ⁇ q ⁇ log (q)). B remains that the implementation of the BP algorithm presents a very high cost in terms of computational complexity, a cost which becomes prohibitive when considering values of q greater than 16.
  • EMS Extended Min-Sum
  • a parity node can be achieved by a combination of elementary parity nodes, where each elementary parity node receives as input two sorted messages and each containing n m pairs (symbol, reliability) from which it generates an output message containing the n m best possible combinations of the two input messages, the total number of combinations being equal to n m to the power 2.
  • n m pairs symbol, reliability
  • FIG. 2 shows a simplified model of a chain of components 110-190 of a DNA-based storage system 100. Note that this model does not include a component for compression.
  • This chain of components includes:
  • a component 160 for reading that is to say DNA sequencing
  • a component 190 for converting GF symbols (4) into binary data a component 190 for converting GF symbols (4) into binary data.
  • the component 110 is configured to convert binary data into GF symbols (4).
  • the component 110 implements a conversion function between binary data and the GF symbols (4) defined as follows:
  • component 190 is configured to convert GF symbols (4) into binary data and uses the inverse conversion function to that of component 110.
  • the component 120 is configured to introduce, during coding, insertion / deletion error correction codes.
  • the component 180 is configured to use, during decoding, the error correction codes to correct the insertions or deletions errors introduced at the time of encoding.
  • substitution errors i.e. that we aim to isolate the problem of substitutions occurring during nanopore sequencing.
  • the components 120 and 180 are complementary to the components 130 and 170 which aim to correct substitution errors.
  • the component 130 implements coding functions of the data blocks from the component 120 involving the generation of parity check blocks, by means of error correcting codes of the type LDPC (Low-Density Parity-Check) or turbo codes, defined on a Galois body of order 4, so that each encoded symbol corresponds to one of the four basic nucleotides of DNA (i.e. - say ' ⁇ ', T, 'C' and 'G').
  • LDPC Low-Density Parity-Check
  • turbo codes defined on a Galois body of order 4
  • LDPC coding generates parity check blocks.
  • This component 130 is applied to a succession of elements in the body of Galois GF (4).
  • the component 170 here called LDPC GF decoder (4), uses the parity check codes to correct the errors on the data blocks at the output of the component 160.
  • the component 130 is configured to encode a sequence of quaternary data (or symbols in GF (4)) by means of an LDPC or turbo code type coding.
  • a sequence of quaternary data or symbols in GF (4)
  • a word of C code with redundancy is obtained for each input code word, the C code word with redundancy comprising N symbols in GF (4) and consisting, on the one hand, of a block of K symbols in GF (4 ) corresponding respectively to the K input symbols and, on the other hand, to a parity check block of M symbols in GF (4) calculated on the basis of the coefficients of the parity matrix.
  • LDPC encoding is repeated for each input code block or word so that a succession of code words with redundancy which will be processed by the DNA synthesis component 140.
  • Component 140 is configured to perform DNA synthesis from the incoming symbol sequence in GF (4).
  • the synthesis is based on the following correspondence function:
  • nucleotide A has the highest average value, followed, in order by nucleotides T, C then G.
  • Simple insertion / deletion error corrections can also be used by integrating corrective codes during synthesis, that is to say at the level of component 140.
  • Tenengolts codes [cf: G. Tenengolts Nonbinary Codes "Correcting Single Deletion or Insertion" IEEE Transactions on Information Theory vol. ⁇ -30 pp. 766-769 1984] are well suited to this type of error and can be directly encoded in the DNA sequence.
  • the problem of reconstructing the DNA sequence from deletion / insertions followed by PCR techniques has been examined in [9] [10], as we focus in this paper specifically on sequencing techniques at nanopores, we assume that the reconstruction of the sequence is ideal or that we don't have to worry about it. Note however that the sequence reconstruction has motivated a large number of recent research [10] [11].
  • the components 120 and 180 will also not be described in more detail in this document.
  • component 160 is configured to perform DNA sequencing via a nanopore sequencer and thus the reading of a DNA sequence.
  • Component 150 is configured for DNA editing and corresponds to a process of removing and inserting DNA substrings at well-controlled locations. In addition, editing can be done by adding very specific point mutations [24] [25]. These possibilities will not be described in more detail in this document.
  • the current drop amplitude measurement operation during nanopore sequencing (component 160) is modeled as a data transmission channel so that the decoding can benefit from the reliability information to perform the associated soft decoding.
  • the measured values that is to say the amplitudes of the current drop measured for each nucleotide.
  • the current drop amplitude measurements obtained by component 160 are converted into symbols in GF (4) by means of a flexible decoding process using reliability information.
  • the parity check blocks generated by the encoding component 130 are used, are integrated into the flexible decoding (for N inputs, there are M symbols corresponding to the parity check blocks) and thus make it possible to correct substitution errors during sequencing.
  • Nanopore sequencing (component 160) generates as output measurement values of the current drops produced by the passage of the DNA sequence through the nanopore are transmitted to component 170. Details of the flexible decoding method (component 1701
  • each measurement value of a current drop corresponds to a sample.
  • a sample corresponds to the realization of a Gaussian random variable.
  • FIG. 3 represents the statistical distributions obtained for 4 types of nucleotides' ⁇ ', T,' C or 'G' respectively.
  • Each curve represents a statistical distribution of the current drop values obtained for a type of nucleotide.
  • the DNA chain cannot be formed with a single type of nucleotide, several known DNA chains passing through a nanopore sequencer are used and the current drop values are measured many times (1000, 2000 ...) to obtain the statistical distribution for a given type of nucleotide.
  • each statistical distribution corresponds to a Gaussian probability density function represented by a Gaussian curve corresponding to a Gaussian random variable.
  • nucleotide "A" is associated with a Gaussian curve, the average of which corresponds to a current drop of 1.25 nA;
  • nucleotide "T" is associated with a Gaussian curve, the average of which corresponds to a current drop of 0.68 nA;
  • nucleotide ‘C is associated with a Gaussian curve, the average of which corresponds to a current drop of 0.65 nA;
  • the nucleotide "G" is associated with a Gaussian curve, the average of which corresponds to a current drop of 0.3 nA. Assuming that the four nucleotides are equiprobable, a hard decoding which would use thresholds to identify each nucleotide would lead to high error rates because the curves are strongly superimposed. For example, as illustrated by FIG. 3, it is not possible when the value of the current drop is between 0.3 and 1 to know with certainty or with sufficient probability whether it is the nucleotide G, C or T. On the other hand, if the value of the current drop is greater than 1, the probability that it is nucleotide A is almost 100 3 ⁇ 4.
  • the current drop measured at a given instant is modeled as a variable modulated by pulse amplitude modulation at 4 levels (here noted 4-PAM, "Pulse Amplitude Modulation”), each level corresponding to the mean value of the probability density function of the current drop amplitudes obtained for a given nucleotide .
  • 4-PAM Pulse Amplitude Modulation
  • the modeling takes into account these statistical distributions by adding to this modulated variable 4 channels of additive Gaussian white noise corresponding respectively to the statistical distributions obtained for the 4 nucleotides.
  • the value of the standard deviation ⁇ i depends on the type of nucleotide A, G, C, T at the origin of the current drop in current and is determined from the normalized probability density function current drops for each DNA nucleotide, for example according to the values given in the table shown in FIG. 4.
  • the mean values Ci to C4 and the standard deviations ⁇ 1 to ⁇ 4 are given for the 4 distributions corresponding to the 4 nucleotides.
  • This table is an example of possible values for a given sequencing sequencer. In practice, for each sequencer and for given experimental conditions, a statistical analysis is implemented for this sequencer, so as to obtain the mean values and standard deviations specific to the sequencer used and / or to the experimental conditions.
  • the first step of the Min-Sum algorithm is the calculation of the value L k (x) for each symbol x of the code word. With the assumption that the four nucleotides are equiprobable, the value L k (x) of the symbol x in the code word can be defined by:
  • Ci is the mean value of the probability density function and ai the standard deviation of the probability density function obtained for the type of nucleotide i.
  • the message intrinsic to the input of the decoding algorithm is formed of 4 pairs consisting of: an LLR value ⁇ k (i) L and a symbol in GF (4), and they are ordered according to the LLR value obtained by the Math.8 equation.
  • LLR ⁇ k (i) L values are normalized, starting with 0, according to Equation Math.8. given above.
  • the flexible decoding algorithm is thus based on a modeling of the current drop measurement produced by the nanopore sequencer as a noisy variable modulated by amplitude pulse modulation at B discrete levels, each level corresponding to an average value of the Gaussian probability density function of the measurements of the current drops measured for a given nucleotide among the B types of nucleotides, the modulated noisy variable being noisy by B channels of additive Gaussian white noise corresponding respectively to the Gaussian statistical distributions obtained for the B types of nucleotides.
  • C2V (jk (l), k) and C2V (jk (2), k) (respectively V2C (jk (l), k) and V2C (jk (2), k)) the two messages C2V (respectively V2C ) associated with the VN k wherein j k (l) and j k (2) indicate the position of the two non-zero values of column k of the matrix H.
  • V2C and C2V messages are identical to the structure of the intrinsic message ⁇ k .
  • the C2N output message of the CN contains the 4 LLR C2N (1) L values (sorted in ascending order) and the GF C2N (1) GF symbols associated with them.
  • L (x), V2C (x) and C2V (x) are respectively the intrinsic LLR values, the extrinsic V2C and C2V messages associated with the symbol x.
  • the VN decoding equations can be divided into three steps.
  • Step 1 the calculation of V2C (x) for each x in GF (4) [Math.11]
  • Step 2 determining the minimum of the value of V2C)
  • Step 3 normalization [Math.13]
  • a parity node of degree d c can be broken down into control nodes elementary, for example in 3 (dc- 2) elementary control nodes.
  • Bubble-check algorithm at the level of the elementary parity node described for example in E. Boutillon, L. Conde-Canencia, “Simplified check node processing in nonbinary LDPC decoders ”, 6th International Symposium on Turbo Codes & Iterative Information Processing, Brest, France, September 2010.
  • a parity check matrix H is obtained.
  • the non-zero values of H can be chosen randomly from the elements of GF (4).
  • the corresponding matrices are designed to maximize the circumference of the associated bipartite graph, and minimize the multiplicity of cycles with a minimum length [23],
  • the Min-Sum algorithm is applied on the basis of the bipartite Tanner graph associated with the parity check matrix H obtained on this basis.
  • the decoding process iterates n it times and for each iteration the following operations are carried out: M updates of control nodes CN (M being the number of control nodes) and M * of updates of control nodes. VN variables. During the last iteration, a decision is taken for each symbol, the decoded GF (4) symbols are then generated and constitute the decoded DNA code word.
  • steps A) to C) are repeated in the next iteration.
  • a final decision is taken to estimate the code word using the new message C2V and the intrinsic message L k .
  • FIG. 5 schematically represents a flowchart of a flexible decoding process.
  • B 4 nucleotides Adenine (A), Cytosine (C), Guanine (G) and Thymine (T) .
  • a Gaussian probability density function of current drop measurements is obtained for each type of nucleotide among the B types of nucleotides.
  • These probability density functions are obtained from one or more sequences of reference nucleotides whose composition is known, and measurements of current drops produced during one or more passage of these reference nucleotide sequences through a nanopore sequencer. .
  • step 520 current drop amplitude measurements produced as the nucleotide sequence to be decoded passes through the nanopore device are obtained.
  • a calculation is carried out for each measurement value and for each type of nucleotide among the N types of nucleotides, of reliability information on the basis of the Gaussian probability density function obtained. for the type of nucleotide considered.
  • the reliability information for a measurement value y k and a type of nucleotide i is calculated according to the Math.8 equation from Ci, the mean value of the probability density function, and ⁇ i, l 'standard deviation of the probability density function obtained for the type of nucleotide i.
  • a decoded value is obtained for the measurement value by application to each current drop measurement considered and to the N reliability information obtained for the measurement value considered from a flexible decoding with a code.
  • error corrector, the error correction code is a turbo code or an LDPC code, Low-Density Parity-Check.
  • the decoding is based on a modeling of the current drop measurement produced by the nanopore device as a noisy variable modulated by pulse amplitude modulation at N discrete levels. Each level corresponds to an average value of the Gaussian probability density function of the measurements of the current drops obtained for a given nucleotide among the N types of nucleotides.
  • the modulated noisy variable is noisy by N channels of additive Gaussian white noise corresponding respectively to the Gaussian statistical distributions obtained for the N types of nucleotides.
  • the number N of nucleotide type is equal for example to 4 and the error correcting code is applied to quaternary data (or symbols) encoded in a Galois body of order 4.
  • Steps 520 to 540 are repeated for each measurement of a fall amplitude. of current produced when a nucleotide of the nucleotide sequence to be decoded passes through the nanopore device.
  • Monte-Carlo simulations were carried out to obtain performance curves of the DNA-based data storage chain with nanopore sequencing. To do this, we generated random binary sequences and converted them into DNA sequences, each nucleotide being represented by a GF symbol (4). We considered N different values and different coding rates for the LDPC code, and compared them to the results obtained with the hard detection.
  • SNER sequenced nucleotide error rate
  • Non-binary LDPC in DNA storage applications with flexible, appropriately modeled intrinsic information used in combination with an optimized Min-Sum decoder.
  • the present description thus relates to a software or computer program, capable of being executed by a computing device (for example, a computer) serving as a decoding device, by means of one or more data processors, this software / program comprising instructions for the execution by this computer device of all or part of the steps of one or more methods described in this document.
  • a computing device for example, a computer
  • this software / program comprising instructions for the execution by this computer device of all or part of the steps of one or more methods described in this document.
  • These instructions are intended to be stored in a memory of a computing device, loaded and then executed by one or more processors of this computing device so as to cause this computing device to execute the process concerned.
  • This software / program can be coded by means of any language of programming, and be in the form of source code, object code, or code intermediate between source code and object code, such as in a partially compiled form, or in any other desirable form.
  • the computing device can be implemented by one or more physically distinct machines.
  • the computing device can have the overall architecture of a computer, including components of such an architecture: data memory (s), processor (s), communication bus, hardware interface (s) for the connection. from this computing device to a network or other equipment, user interface (s), etc.
  • all or part of the steps of the decoding method described in this document are implemented by a decoding device provided with means for implementing these steps of this method.
  • These means can comprise software means (software) (eg instructions of one or more components of a program) and / or hardware means (eg data memory (s), processor (s), communication bus, hardware interface (s), etc.).
  • software eg instructions of one or more components of a program
  • hardware means eg data memory (s), processor (s), communication bus, hardware interface (s), etc.
  • Means implementing a function or a set of functions can also correspond in this document to a software component, to a hardware component or to a set of hardware and / or software components, capable of implementing the function. or the set of functions, as described below for the means concerned.
  • the present description also relates to an information medium readable by a data processor, and comprising instructions of a program as mentioned above.
  • the information medium can be any material means, entity or device, capable of storing the instructions of a program as mentioned above.
  • Usable program storage media include ROM or RAM, magnetic storage media such as magnetic disks and magnetic tapes, hard disks or optical readable digital data storage media, etc., or any combination thereof. supports.
  • the computer readable storage medium is not transient.
  • the information medium can be a transient medium (for example, a carrier wave) for the transmission of a signal (electromagnetic, electrical, radio or optical signal) carrying the program instructions.
  • This signal can be routed via an appropriate transmission means, wired or wireless: electrical or optical cable, radio or infrared link, or by other means.
  • An embodiment also relates to a computer program product comprising a computer readable storage medium on which program instructions are stored, the program instructions being configured to cause the computer device to implement everything. or part of the steps of one or more methods described herein when the program instructions are executed by one or more processors and / or one or more programmable hardware components.
  • all or part of the steps of the decoding method described in this document are implemented by electronic circuit, programmable or not, specific or not.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Theoretical Computer Science (AREA)
  • Biophysics (AREA)
  • Spectroscopy & Molecular Physics (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Evolutionary Biology (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Chemical & Material Sciences (AREA)
  • Biomedical Technology (AREA)
  • Biotechnology (AREA)
  • Evolutionary Computation (AREA)
  • Molecular Biology (AREA)
  • General Physics & Mathematics (AREA)
  • Bioethics (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Analytical Chemistry (AREA)
  • Artificial Intelligence (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Public Health (AREA)
  • Computer Hardware Design (AREA)
  • Geometry (AREA)
  • Epidemiology (AREA)
  • Computer Vision & Pattern Recognition (AREA)
  • Proteomics, Peptides & Aminoacids (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Computational Linguistics (AREA)
  • Genetics & Genomics (AREA)
  • Nanotechnology (AREA)
  • Hematology (AREA)
  • Urology & Nephrology (AREA)

Abstract

Procédé de décodage d'une séquence de données binaires encodées par une séquence de nucléotides à décoder comprenant B types de nucléotides d'ADN, comprenant: une obtention (510) pour chaque type de nucléotide d'une fonction de densité de probabilité, les fonctions de densité de probabilité étant obtenues à partir de mesures de chutes de courant produites lors d'au moins un passage d'au moins une séquence de nucléotides de référence à travers un séquenceur à nanopore; une obtention (520) de mesures de chute de courant produites au passage de la séquence de nucléotides à décoder à travers le séquenceur à nanopore; un calcul (530), pour chaque valeur de mesure considérée et pour chaque type de nucléotide parmi les B types de nucléotides, d'une information de fiabilité sur la base de la fonction de densité de probabilité obtenue pour le type de nucléotide considéré; une obtention (540) d'une valeur décodée identifiant un type de nucléotide parmi les B types de nucléotides d'ADN par application à la mesure de chute de courant et aux B informations de fiabilité obtenues pour la valeur de mesure considérée d'un algorithme de décodage souple avec un code correcteur d'erreur.

Description

DESCRIPTION
TITRE: procédé et dispositif de décodage de données stockées dans un système de stockage à base d'ADN
DOMAINE TECHNIQUE [0001] La présente description concerne un dispositif de décodage de données stockées dans un système de stockage à base d'ADN (acide désoxyribonucléique) avec séquenceur à nanopores et un procédé de décodage correspondant.
ETAT DE LA TECHNIQUE
[0002] Une des méthodes de lecture de données stockées dans des systèmes de stockage à base d’ADN est connu sous le nom de séquençage d’ADN (« DNA sequencing », selon la terminologie anglosaxonne). Leur but est de déterminer les nucléotides exacts et leur ordre dans une séquence d'ADN qui encode des données numériques.
[0003] Il y a déjà eu plusieurs générations de technologies de séquençage et chacune d'entre elles a soulevé des défis spécifiques. Après le séquençage Sanger de première génération qui date des années 1970, les technologies de la deuxième génération [25] ont permis une diminution impressionnante des coûts du séquençage au cours de la dernière décennie (par exemple [26] et [27]). Cependant, ces technologies ne peuvent pas lire de longs brins de nucléotides : les appareils doivent ainsi lire de courts fragments, puis combiner les données pour récupérer la séquence originale. Ce processus a motivé des recherches récentes sur les algorithmes de reconstruction ([28], [29] et [17]).
[0004] Dans ce document, seuls les séquenceurs dits de troisième génération qui sont basés sur des nanopores sont considérés. Dans ces séquenceurs (appelés ici aussi dispositif de séquençage), le principe du séquençage par nanopore est basé sur la détection des changements dans un courant ionique lorsqu'une séquence d'ADN passe à travers un trou à l'échelle nanométrique. Chaque base nucléique ou nucléotide provoque une amplitude différente de chute de courant en raison de sa structure atomique différente. Cela rend possible l'identification du nucléotide passant à travers le nanopore à un instant donné. Le principal avantage des séquenceurs à nanopores est qu’ils permettent de lire de longues séquences en une seule étape, jusqu'à plusieurs dizaines de milliers de nucléotides.
[0005] Cependant, ces séquenceurs à nanopores présentent encore des contraintes importantes et un taux d'erreur élevé. Ainsi, le défi est de fournir des outils efficaces pour corriger les erreurs inhérentes à la technologie de séquençage et correspondant à des suppressions, insertions et substitutions simples ou en rafale pouvant se produire lors du séquençage. [0006] Le processus de synthèse de séquences d’ADN encodant des données numériques est également connu comme une source d'erreurs simples de substitution et de suppression/insertion.
[0007] Ces méthodes de synthèse chimique d’ADN les plus prometteuses sont connues sous le nom de synthèse à base de micro-réseau (« micro-array based synthesis », selon la terminologie anglosaxonne). Ces méthodes permettent de synthétiser des séquences d’ADN de longueurs jusqu'à 200 nucléotides, avec un coût d'environ 0.001$ par nucléotide. Cependant, son inconvénient majeur est son taux d’erreur élevé. D'un point de vue général, nous pouvons affirmer que les méthodes de synthèse actuelles combinent soit un coût élevé et une grande précision ou au contraire un faible coût élevé et une faible précision, et les recherches en cours tentent réduire l'écart entre ces deux extrêmes.
[0008] Les principaux événements générateurs d’erreur dans la synthèse de l'ADN sont des substitutions simples [1] [2] [10] d’un nucléotide par un autre et les taux d'erreur de substitution dépendent principalement des performances et du coût de la technologie [13]
[14] [15] [0009] Les méthodes de séquençage utilisant la réaction en chaîne de la polymérase (PCR,
« Polymerase Chain Reaction », selon la terminologie anglo-saxonne) amplifie ces erreurs de substitution en créant de nombreuses copies de la séquence synthétisée. De plus, avec le séquençage à haut débit, les erreurs de synthèse se propagent à travers un certain nombre de lectures produites par le séquençage. Ces questions ont été abordées dans [17] [18] [19] avec l'introduction de codes de profil ADN.
[0010] Il apparaît ainsi un besoin d’améliorer la situation en réduisant la complexité des systèmes à base d’ADN utilisant des séquenceurs basés sur des nanopores tout en augmentant leur fiabilité, notamment en réduisant les erreurs de substitution produites lors du séquençage. [0011] Dans cette perspective, des travaux antérieurs incluent [8] [14] [15]. Dans ces approches les auteurs proposent des codes asymétriques pour traiter les erreurs de substitution caractérisées par les distributions statistiques (fonctions de densité de probabilité des niveaux de signaux de sortie) des réponses impulsionnelles des signaux de sortie du séquenceur à nanopore, ces signaux de sortie correspondant aux amplitudes des chutes de courant mesurées. Ces erreurs sont en fait considérées comme asymétriques parce que certaines substitutions sont beaucoup plus probables que d'autres (par exemple la base nucléique A est plus susceptible d'être substituée par la base nucléique T que par la base nucléique G)
[0012] Dans [15], des codes dans la distance de Damerau sont introduits pour corriger les erreurs de transposition individuelles ou par bloc combinées avec des suppressions. D'autres travaux importants [16] abordent le problème des vitesses de translocation rapide des molécules d'ADN à travers le nanopore, qui conduit à des suppressions en rafales [17], Pour corriger ce type d'erreurs, les auteurs ont proposé un code non binaire de correction des rafales de suppression dans [18], Tous ces types de codes offrent une capacité de correction d'erreurs efficace et les algorithmes de décodage associés utilisent un décodage à distance limitée (bounding distance decoding, selon la terminologie anglosaxonne), basé sur la prise d'une décision dure (« hard decoding », selon la terminologie anglosaxonne) à l'entrée du décodeur.
RESUME
[0013] Selon un premier aspect, est divulgué un procédé de décodage d’une séquence de données binaires encodées par une séquence de nucléotides à décoder comprenant B types de nucléotides d’ADN, B étant un nombre entier égal à 2, 3 ou 4, le procédé de décodage comprenant
- une obtention, pour chaque type de nucléotide parmi les B types de nucléotides, d’une fonction de densité de probabilité, les fonctions de densité de probabilité étant obtenues à partir de mesures de chutes de courant produites lors d’au moins un passage d’au moins une séquence de nucléotides de référence à travers un séquenceur à nanopore ;
- une obtention de mesures de chute de courant (y1, y2, ...yk) produites au passage de la séquence de nucléotides à décoder à travers le séquenceur à nanopore;
- un calcul, pour au moins une valeur de mesure et pour chaque type de nucléotide parmi les B types de nucléotides, d’une information de fiabilité (λk( (i)L) sur la base de la fonction de densité de probabilité obtenue pour le type de nucléotide considéré;
- une obtention pour chaque valeur de mesure considérée d’une valeur décodée identifiant un type de nucléotide parmi les B types de nucléotides d’ADN par application à la mesure de chute de courant et aux B informations de fiabilité obtenues pour la valeur de mesure considérée d’un algorithme de décodage souple avec un code correcteur d’erreur.
[0014] Dans des exemples de réalisation, la fonction de densité de probabilité est une fonction de densité de probabilité gaussienne et l’algorithme de décodage souple est basé sur une modélisation de la mesure de chute de courant produite par le séquenceur à nanopore une variable bruitée modulée par modulation d'impulsions en amplitude à B niveaux discrets, chaque niveau correspondant à une valeur moyenne de la fonction de densité de probabilité obtenue pour un type de nucléotide donné, la variable bruitée modulée étant bruitée par B canaux de bruit blanc gaussien additif correspondant respectivement aux distributions statistiques obtenues pour les B types de nucléotides. Le séquenceur à nanopore est ainsi modélisé comme un canal de communication asymétrique.
[0015] Dans des exemples de réalisation, le code correcteur d’erreur est un turbo code ou un algorithme de décodage de code LDPC, Low-Density Parity-Check. L’algorithme de décodage souple est par exemple un algorithme turbo-codes de type MAP, Message
Parsing Algorithm. L’algorithme de décodage souple est par exemple un algorithme Min- Sum pour codes LDPC ou un algorithme par propagation de croyance (BP, « belief propagation ») pour codes LDPC.
[0016] Dans des exemples de réalisation, le nombre B de type de nucléotides est égal à 4 et l’algorithme de décodage souple avec code correcteur d’erreur est appliqué à des symboles dans un Corps de Galois d’ordre 4, chaque symbole dans le Corps de Galois d’ordre 4 correspondant à un nucléotide. Le procédé est également applicable à des séquences d’ ARN (acide ribonucléique) comprenant seulement 3 types de nucléotides tout en utilisant un corps de Galois d’ordre q=4. L’ordre dans lequel les nucléotides sont associés aux symboles dans le Corps de Galois d’ordre 4 correspond à l’ordre inverse des valeurs moyennes des fonctions de densité de probabilité des amplitudes de chutes de courant obtenues pour les différents types de nucléotide.
[0017] Dans des exemples de réalisation, l’information de fiabilité pour une valeur de mesure yk et un type de nucléotide i est calculée comme suit : [Math.201]
Figure imgf000007_0001
où Ci est la valeur moyenne de la fonction de densité de probabilité et σi l’écart type de la fonction de densité de probabilité obtenue pour le type de nucléotide i.
[0018] Selon un deuxième aspect est divulgué un dispositif de décodage comprenant des moyens de mise en œuvre des étapes d’un procédé selon le premier aspect. Les moyens peuvent être des moyens matériels et/ou logiciels configurés pour mettre en œuvre les fonctions définies dans ce document pour le dispositif de décodage. Selon un exemple de réalisation, le dispositif de décodage comprenant au moins une mémoire et au moins un processeur, la mémoire stockant des instructions de programme configurées pour causer l’exécution par ledit dispositif de décodage des étapes d’un procédé selon le premier aspect lorsque les instructions de programme sont exécutées par le processeur.
[0019] Selon encore un autre aspect est divulgué un programme d'ordinateur comportant des instructions de programme pour l'exécution des étapes d’un procédé selon le premier aspect lorsque ledit programme est exécuté par un ordinateur. [0020] Selon encore un autre aspect est divulgué un support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur comprenant des instructions de programme pour l'exécution des étapes d’un procédé selon le premier aspect lorsque ledit programme est exécuté par un ordinateur.
[0021] Selon encore un autre aspect est divulgué un système de stockage de données à base d’ADN, comprenant un séquenceur à nanopore et un dispositif de décodage selon le deuxième aspect.
BREVE DESCRIPTION DES FIGURES
[0022] D’autres avantages et particularités résulteront de la description qui va suivre, donnée à titre d'exemple non limitatif et faite en référence aux figures annexées dans lesquelles :
[fig.1] illustre des aspects du calcul de blocs de parité dans un procédé de codage selon un ou plusieurs modes de réalisation;
[fig.2] est une représentation schématique d’un système de stockage à base d'ADN selon un ou plusieurs modes de réalisation; [fig.3] représente des exemples distributions statistiques de mesures de chute de courant obtenues pour différents types de nucléotides dans un séquenceur à nanopore;
[fig.4] représente un tableau de paramètres (moyenne et écart type) des distributions statistiques présentées à la Fig. 3; [fig.5] représente un organigramme d’un procédé de décodage souple selon un ou plusieurs modes de réalisation.
DESCRIPTION DETAILLEE
[0023] Des systèmes de stockage de données à base d’ADN avec séquenceurs à nanopores vont être décrits plus en détails. Ces systèmes de stockage sont basés sur l'utilisation de codes quaternaires basés sur des graphes définis sur des Champs de Galois d’ordre 4 et des algorithmes de décodage associés basés sur des échantillons « souples » (« soft samples », selon la terminologie anglo-saxonne). Ces échantillons sont les produits de séquenceurs à nanopores dont la principale caractéristique est le passage de la séquence ADN à vitesse contrôlée à travers un ou des nanopores. Dans ces systèmes, chaque nucléotide d'ADN est représenté comme un élément d'un Corps de Galois d'ordre 4. Des calculs de vraisemblance sont introduits pour prendre en compte un modèle de canal asymétrique d'ADN et les chutes de courant ionique. Un algorithme de type « Min-Sum » adapté pour un décodage quasi-optimal de faible complexité est présenté. Les résultats des simulations montrent que le procédé de correction d'erreur proposé dans ce document est capable de garantir une lecture de données quasi sans erreur en ce qui concerne les erreurs de substitutions et avec des conditions idéales pour la synthèse .
[0024] On parle ici de décodage « souple » (« soft decoding » selon la terminologie anglo- saxonne) ou d’échantillons souples pour désigner une technique de décodage dans laquelle des informations de fiabilité sont disponibles pour les échantillons. Ces informations de fiabilité permettent notamment d’effectuer une correction de la valeur de l’échantillon mesurée à un instant donné. Un échantillon souple ou valeur souple correspondent à une valeur analogique mesurée en sortie, sans quantification ni codage.
[0025] Les contributions décrites dans ce document portent spécifiquement sur la correction des erreurs de substitution produites lors du séquençage à nanopores. [0026] La première contribution concerne l’utilisation d'un schéma de codage/décodage quaternaire utilisant une représentation des nucléotides de l'ADN comme éléments d'un Corps de Galois d'ordre 4 (cela inclut également la correspondance avec l'information numérique à stocker dans le système) et l'utilisation de codes correcteurs non binaires définis dans ce Corps de Galois. Cela permet d'éviter les conversions quaternaires en binaires qui seraient nécessaires lors de l'utilisation d'un schéma de codage/décodage binaire.
[0027] La deuxième contribution concerne l'utilisation des distributions statistiques des amplitudes des signaux de courant ionique comme information intrinsèque « souple », c’est-à-dire comme information de fiabilité. Des calculs de vraisemblance au décodeur à base de graphes qui tiennent compte de ces amplitudes et du modèle spécifique de canal d'ADN asymétrique sans mémoire (i.e. la sortie à un instant donné, ne dépend que de l’entrée à cet instant mais pas des entrées aux instants précédents ou postérieurs). Notez que les approches de codage connues dans l’état de la technique [8] [15] pour ce problème ne permettent pas d'exploiter les informations « souples » fournies par le système à nanopore. Les codes correcteurs d’erreurs susceptibles d’utiliser cette information intrinsèque peuvent être des codes LDPC (Low-Density Parity-Check) ou bien des turbo- codes.
[0028] Enfin, comme l'un des inconvénients majeurs des algorithmes de décodage de symboles non binaires est leur complexité, une troisième contribution consiste à adapter l'algorithme Min-Sum pour pouvoir effectuer un décodage quasi-optimal avec un nombre réduit de calculs.
[0029] Définitions et principes
[0030] Pour rappel, un corps de Galois GF(q) est un ensemble fini de q éléments dont tout élément peut être décrit en fonction d’un élément primitif, noté ici a. Les éléments (ou symboles) du corps de Galois GF(q) sont notés {0, α0, α1, ... aq-2}.
[0031] Un mot de code (« codeword », selon la terminologie anglo-saxonne) est noté X = {x1, x2, .... xN}, OÙ {xk}, k= 1 à N, est un élément (ou symbole) appartenant à un corps de Galois GF(q) et est représenté par m = log2(q) bits avec xk= { xk,i, xk,2, ....xk,m}.
[0032] Les codes LPDC sont des codes correcteurs d’erreurs de la catégorie des codes en bloc linéaires, dont la matrice de parité a la propriété d’être creuse (en anglais, « low- density parity check matrix »), c’est-à-dire qu’elle ne contient qu’un faible nombre d’éléments non nuis en comparaison de son nombre total d’éléments. Les codes LDPC peuvent en effet être caractérisés, à l’instar des codes en bloc linéaires, par une matrice dite de parité, généralement notéeH. La matrice de paritéH est liée à une matrice dite de génération du code, généralement notéeG, par la relation : G.HT = 0 oùHT désigne la matrice transposée deH. Les dimensionsM x N delà matrice de parité correspondent, pour le nombre de lignesM, au nombre de contraintes de parité du code, et pour le nombre de colonnesN, à la longueur des mots de code du code considéré (i.e. le nombre de symboles dans un mot de code). Les lignes de la matrice de paritéH d’un code en bloc linéaire correspondant respectivement à des contraintes de parité qui sont par construction respectées par les mots de code, l’égalitév.HT = 0 sera vérifiée pour tout mot de codev. [0033] Les codes LDPC dont les symboles composant les mots de code appartiennent au corps de Galois binaire (d’ordre 2), noté GF(2), sont dits binaires, tandis que les codes LDPC dont les symboles composant les mots de code appartiennent à un corps de Galois d’ordre q strictement supérieur à 2, noté GF(q), sont dits non-binaires. Ainsi, les éléments d’une matrice de parité d’un code LDPC non-binaire appartiendront à un corps de Galois GF(q) non binaire (q > 2) et les produits matriciels des équations ci-dessus seront effectués en utilisant les lois d’addition et de multiplication du corps GF(q), notées respectivement
Figure imgf000010_0002
dans la suite.
[0034] Un code LDPC non binaire est un code linéaire associé à un bloc de données d’entrée et défini par une matrice de contrôle de parité H très clairsemée dont les éléments non nuis appartiennent à un champ fini GF(q), où q >2. On considère dans ce document le cas d’un corps de Gai ois d’ordre q = 4.
[0035] La construction de ces codes LDPC est exprimée par un ensemble d'équations de contrôle de parité sur GF(q), où une équation de parité impliquant de symboles de mots de code s’écrit : [Math.l]
Figure imgf000010_0001
où hj,k sont les valeurs non nulles de laj-ème ligne de la matrice H et un mot de code est désigné par X = {x1, x2, xN}, OÙ Xk est un symbole représenté par m=log2(q)= 2 bits dans le cas où q = 4. . On note dc le nombre de 1 dans une ligne de la matrice H et dv le nombre de 1 dans une colonne de la matrice H.
[0036] De nombreux algorithmes de décodage itératif de codes LDPC utilisent une représentation de la matrice de parité du code par un graphe bi-partite dit « graphe de Tanner ». Pour une matrice de parité H de dimensions M×N, cette représentation met en correspondance, par le biais de branches, M nœuds, dits « nœuds de parité » (en anglais « Check Node » ou « CN ») avec N nœuds, dits « nœuds de variable » (en anglais « Variable Node » ou « VN »). Chaque élément non nul de la matrice de parité est représenté dans le graphe de Tanner correspondant par une branche joignant le nœud de parité correspondant à la ligne de l’élément dans la matrice H au nœud de variable correspondant à la colonne de l’élément dans la matrice H. Chaque nœud de parité du graphe représente ainsi une équation de parité déterminée par les branches qui le relient aux nœuds de variables.
[0037] Un exemple de matrice de contrôle de parité H 100 est représenté dans la partie gauche de la Fig. 1 et le graphe de Tanner 110 correspondant et représenté dans la partie droite de la Fig. 1. Dans cet exemple, la matrice de parité H est définie dans le corps de Galois GF(4) dont les éléments sont notés {0, α0, α1, α2}. La matrice de parité H est de dimensions M = 3 et N = 6. Le graphe de Tanner 110 correspondant comprend M = 3 nœuds de parité notés sur la fig. 1 CN1, CN2 et CN3, et N = 6 nœuds de variable notés VN1, VN2 , VN3, VN4, VN5 et VN6. [0038] Les trois équations de parité correspondant respectivement aux trois nœuds de parité de ce graphe sont :
[Math.11]
Figure imgf000011_0001
pour le nœud de parité CN1, [Math.12]
Figure imgf000011_0002
pour le nœud de parité CN2,
[Math.13]
Figure imgf000011_0003
pour le nœud de parité CN3, où les opérateurs Θ et ® désignent respectivement l’addition et la multiplication dans le corps de Galois GF(4).
[0039] Le graphe de Tanner 110 représente le traitement itératif appliqué à chaque mot de code à décoder. Les nœuds de variable VNk reçoivent chacun un vecteur λk composé de B=4 couples de valeurs pour chaque valeur de mesure d’entrée yk correspondant à un symbole d’un mot de code d’entrée à décoder ou d’un mot de code en cours de décodage. Par exemple, sur la fig. 1, le nœud de variable VNk reçoit un vecteur λk calculé par un bloc de calcul 10k à partir de l’entrée yk pour décoder le symbole xk d’un mot de code X. [0040] Ces informations de fiabilités sont par exemple basées sur la fonction LLR (Log
Likehood Ratio) comme expliqué plus en détail dans ce document. Dans cet exemple, chaque couple du vecteur λk est composé d’un symbole Xk possible dans GF(4) = {0, α0, α1, α2} et d’une information de fiabilité associée, notéeλk(i)L avec i = 1 à 4. Le vecteur d’entrée λk est ainsi défini comme suit : [Math.14]
Figure imgf000012_0001
[0041] . Le mot de code décodé est généré par les nœuds de variable après itération(s) dans le graphe de Tanner. Un symbole décodé d’un mot de code décodé correspond à la première valeur du vecteur de sortie (les symboles du vecteur de sortie étant triées par ordre croissant de valeur LLR, la première ligne du vecteur de sortie comprenant ainsi la valeur LLR la plus élevée et le symbole décodé associé), c’est-à-dire la valeur dans GF(4) la plus probable ou celle dont l’erreur de décodage est la plus faible. Le nœud de variable VNk reçoit ainsi un vecteur décodé contenant la valeur décodée pour le symbole Xk du mot de code X. Le symbole décodé identifie un type de nucléotide parmi les B types de nucléotides d’ADN et correspond à la valeur de mesure de chute de courant.
[0042] La représentation graphique de Tanner peut être exploitée pour la mise en œuvre d’algorithmes de décodage dont l’efficacité a été montrée sur des modèles de graphe, tels que l’algorithme dit de « propagation de croyances » (en anglais, « belief propagation », ou « BP ») ou les algorithmes de type à passage de messages (en anglais, « message passing », ou MP). Lorsqu’il est appliqué à un graphe bipartite ayant deux types de nœuds, l’algorithme BP repose sur un processus itératif d’envoi de messages entre des nœuds de chaque type connectés par des branches (nœuds dits « voisins »). [0043] Dans le cadre d’un algorithme de décodage de codes LDPC, un message correspond à un vecteur de données. Un message peut être un message intrinsèque (vecteur de données d’entrées généré à partir des informations du canal à l’entrée du décodeur) ou un message extrinsèque (vecteur de données généré au cours d’une itération appliquée à un message intrinsèque, ces messages extrinsèques sont les messages échangés entre les nœuds de parité et les nœuds de variable).
[0044] Des algorithmes de décodage de codes LDPC itératifs à base de graphe de Tanner, utilisant notamment l’échange de messages entre les nœuds de parité et les nœuds de variable du graphe de Tanner correspondant au code LPDC considéré ont ainsi été développés. Ces algorithmes de décodage peuvent plus généralement être mis en œuvre ou adaptés pour le décodage de tous les codes en bloc linéaires susceptibles d’être représentés par un graphe bipartite comprenant un ensemble de nœuds de parité et un ensemble de nœuds de variable.
[0045] Le graphe de Tanner d'un code LDPC non binaire est généralement beaucoup plus épars qu'un graphe de Tanner correspondant d'un code LDPC binaire ayant le même débit et la même longueur de code en bits [19] [20], De plus, une meilleure performance de correction d'erreur peut être obtenue en utilisant un degré de nœud de variable le plus bas possible, soit dv=2.
[0046] Pour le stockage des données sur l'ADN, nous considérons dans ce document les codes LDPC non binaire définis sur un Corps de Galois d'ordre 4 noté GF(4) (c.-à-d. q=4). Les éléments de GF(4) sont ainsi notés {0, α0, α1, α2}, où a est l'élément primitif de ce Corps de Galois. Un élément de GF(q) est ainsi représenté par m = log2(q) = 2 bits. Les éléments de GF(4) sont également appelés des symboles.
[0047] Les imités de base de construction de l'ADN sont les quatre nucléotides : Adénine (A), Cytosine (C), Guanine (G) et Thymine (T). Chaque nucléotide est représenté par un symbole dans GF(4). Avant la synthèse, la séquence de données binaires d’entrée est convertie en séquence de données quaternaires ou symboles dans GF(4). [0048] La séquence de données quaternaires est ensuite divisée en blocs de K = N - M symboles d’entrée, correspondant respectivement aux nucléotides A, C, G et T, pour aboutir à des mots de code d’entrée de taille N. Après codage LDPC, un mot de code C avec redondance est obtenu pour chaque mot de code d’entrée, le mot de code C avec redondance comprenant N symboles dans GF(4) et étant constitué, d’une part, d’un bloc de
K symboles dans GF(4) correspondants respectivement aux K symboles d’entrée et, d’autre part, d’un bloc de contrôle de parité de M symboles dans GF(4) calculé sur la base des coefficients de la matrice de parité. Le codage LDPC est répété pour chaque bloc ou mot de code d’entrée de sorte à obtenir une succession de mots de code avec redondance. [0049] Une succession de mots de code avec redondance fait ensuite l’objet de la synthèse de sorte à obtenir une séquence d’ADN encodant les blocs de données binaires d’entrée.
[0050] On utilise ensuite un dispositif à nanopore pour convertir la séquence d’ADN encodant les blocs de données binaires d’entrée en une suite de valeurs de mesure d’amplitudes de chutes de tension. Cette suite de mesures d’amplitude de chute de courant est convertie en une suite de symboles dans GF(4) par application d’un algorithme de décodage souple (algorithme de décodage à entrées souples), en associant à chaque mesure d’amplitude de chute de courant q=4 valeurs de fiabilité correspondant respectivement aux 4 symboles de GF(4). En sortie de l’algorithme de décodage, un symbole Xk décodé dans GF(4) est obtenu pour chaque mesure yk d’amplitude de chute de courant. Le symbole décodé correspond au symbole le plus probable, celui pour lequel l’erreur de décodage est la plus faible.
[0051] L’algorithme de décodage souple peut être un algorithme de décodage de codes LDPC (par exemple, un algorithme Min-Sum pour codes LDPC ou un algorithme BP, Belief Propagation) ou turbo-codes (par exemple, un algorithme MAP, Message Parsing Algorithm). Dans le cadre du présent document, on décrit plus en détail l’utilisation d’un algorithme LDPC. Quel que soit l’algorithme de décodage, les valeurs de fiabilité utilisées sont basées sur les distributions statistiques de mesures de chutes de courant produites lors du passage à travers un séquenceur à nanopore d’une séquence de référence composée de nucléotides d’un type considéré (à l’exclusion des autres types de nucléotides). Par exemple, si on applique un décodage LDPC à entrées souples, les messages échangés comprennent les symboles des mots de code traités et une information de fiabilité associée à chaque symbole. [0052] Dans des exemples de réalisation, des informations de fiabilité sont calculées à partir d’une valeur de mesure yk fournies par le dispositif à nanopore. Ces informations de fiabilités sont basées sur la fonction LLR (Log Likehood Ratio) comme expliqué plus en détail dans ce document. [0053] On notera que lorsque le code LDPC est binaire, et que les symboles des mots de code sont à valeurs dans le corps de Galois GF(2), c’est-à-dire à valeurs binaires, les messages échangés comprennent des densités de probabilité comprennent deux densités, l’une pour la valeur « 0 » et l’autre pour la valeur « 1 ». Les messages ou vecteurs de données comprennent par exemple des couples de valeurs binaires auxquelles sont respectivement associées des valeurs de vraisemblance (ou de fiabilité).
[0054] Dans le cadre de ce document, le code LDPC considéré est non-binaire, et les symboles des mots de code sont à valeurs dans le corps de Galois GF (4). les messages échangés contiennent q = 4 valeurs de fiabilité, correspondant chacune à un élément de GF(q), qui peuvent être représentées sous la forme d’un vecteur de taille q de couples (symbole, valeur de fiabilité).
[0055] Un nœud de parité d’un décodeur pour codes LDPC non binaire d’un code à valeurs dans le corps de Galois GF(q) reçoit ainsi dc messages en entrée et génère dc messages en sortie. Chaque message d’entrée et de sortie contient q = 4 couples de valeurs, l’une représentant un symbole, et l’autre représentant une fiabilité ou une vraisemblance associée à ce symbole.
[0056] Lorsqu’on utilise une implémentation directe de l’algorithme de décodage Belief Propagation (BP), une sortie est construite en sélectionnant les q meilleures combinaisons parmi q à la puissance de- 1. Cela conduit à une complexité de calcul de l’ordre de 0(q2). L’algorithme de décodage BP peut en outre être considéré dans le domaine fréquentiel. On parle alors d’algorithme BP basé sur la transformation de Fourier (en anglais, « Fourier Transform-based BP algorithm »). Le passage dans le domaine fréquentiel permet de réduire la complexité de l’algorithme BP, pour atteindre une complexité de l’ordre de 0(dc× q ×log(q)). B reste que l’implémentation de l’algorithme BP présente un coût très élevé en termes de complexité de calcul, coût qui devient prohibitif dès lors que l’on envisage des valeurs de q supérieures à 16.
[0057] Différents algorithmes ont été proposés pour palier à ce problème de complexité élevée, parmi lesquels l’algorithme dit Extended Min-Sum (EMS), qui propose d’utiliser des messages tronqués en sélectionnant les nm symboles les plus fiables, nm étant choisi très inférieur à q (nm «q). Cependant, vu l’ordre relativement faible du corps de Gai ois, nous considérons ici que nm =q= 4.
[0058] Les messages sont ensuite triés avant d’être introduits au nœud de parité. Un nœud de parité peut être réalisé par une combinaison de nœuds de parité élémentaires, où chaque nœud de parité élémentaire reçoit en entrée deux messages triés et contenant chacun nm couples (symbole, fiabilité) à partir desquels il génère un message de sortie contenant les nm meilleures combinaisons possibles des deux messages en entrée, le nombre total de combinaisons étant égal à nm à la puissance 2. [0059] On pourra se reporter à l’article suivant pour une description détaillée de l’algorithme EMS : « Decoding algorithms for nonbinary LDPC codes over GF(q) », D. Declercq et M. Fossorier, IEEE Trans. Commun., vol. 55, n° 4, pp. 633-643, Apr. 2007.
[0060] La Fig. 2 présente un modèle simplifié d’une chaîne de composants 110 à 190 d’un système 100 de stockage à base d'ADN. Notez que ce modèle n'inclut pas de composant pour la compression.
[0061] Cette chaîne de composants comprend :
- un composant 110 de conversion de données binaires en symboles GF(4) ;
- un composant 120 de correction d’erreur d’insertions / suppressions ;
- un composant 130 d’encodage LDPC appliqué à des symboles GF(4) ;
- un composant 140 d’écriture, c’est-à-dire de synthèse d’ADN ;
- un composant 150 d’édition d’ADN ;
- un composant 160 de lecture, c’est-à-dire de séquençage d’ADN ;
- un composant 170 de décodage LDPC appliqué à des symboles GF(4) ;
- un composant 180 de correction d’erreur d’insertions / suppressions ;
- un composant 190 de conversion de symboles GF(4) en données binaires.
[0062] Le composant 110 est configuré pour convertir des données binaires en symboles GF(4). Le composant 110 met en œuvre une fonction de conversion entre données binaires et les symboles GF(4) définie comme suit :
‘00’ -> 0 ‘01 -> α0
‘10’ -▻ α1 ‘11' -> α2. [0063] De manière symétrique, le composant 190 est configuré pour convertir des symboles GF(4) en données binaires et utilise la fonction de conversion inverse à celle du composant 110.
[0064] Le composant 120 est configuré pour introduire, lors du codage, des codes de corrections d’erreurs d’insertions / suppressions. De manière symétrique, le composant 180 est configuré pour exploiter, lors du décodage, les codes de corrections d’erreurs pour corriger les erreurs d’insertions ou suppressions introduits au moment du codage.
[0065] Dans le présent document, nous nous concentrons spécifiquement sur les erreurs de substitution, c.-à-d. que nous visons à isoler le problème des substitutions se produisant lors du séquençage par nanopores. Ainsi les composants 120 et 180 sont complémentaires des composants 130 et 170 qui visent la correction des erreurs de substitution.
[0066] Le composant 130, appelé ici encodeur GF(4), met en œuvre des fonctions de codage des blocs de données issus du composant 120 impliquant la génération de blocs de contrôle de parité, au moyen de codes correcteurs d’erreur de type LDPC (Low-Density Parity-Check) ou turbo codes, définis sur un Corps de Galois d'ordre 4, de sorte que chaque symbole codé correspond à l'un des quatre nucléotides de base de l'ADN (c'est-à-dire 'Α', T, 'C' et 'G').
[0067] Le codage LDPC génère des blocs de contrôle de parité. Ce composant 130 est appliqué à une succession d’éléments dans le Corps de Galois GF(4). De manière symétrique, le composant 170, appelé ici décodeur LDPC GF(4), exploite les codes de contrôle de parité pour corriger les erreurs sur les blocs de données en sortie du composant 160. Ces composants seront décrits plus en détail ci-dessous.
[0068] Plus précisément, le composant 130 est configuré pour encoder une séquence de données quaternaires (ou symboles dans GF(4)) au moyen d’un codage type LDPC ou turbo code. Par exemple, dans le cas du codage LDPC, la séquence de symboles est divisée en blocs de K = N - M symboles d’entrée, pour aboutir à des mots de code d’entrée de taille N. Après codage LDPC, un mot de code C avec redondance est obtenu pour chaque mot de code d’entrée, le mot de code C avec redondance comprenant N symboles dans GF(4) et étant constitué, d’une part, d’un bloc de K symboles dans GF(4) correspondants respectivement aux K symboles d’entrée et, d’autre part, d’un bloc de contrôle de parité de M symboles dans GF(4) calculé sur la base des coefficients de la matrice de parité. Le codage LDPC est répété pour chaque bloc ou mot de code d’entrée de sorte à obtenir une succession de mots de code avec redondance qui sera traité par le composant 140 de synthèse d’ADN.
[0069] Le composant 140 est configuré pour réaliser la synthèse d’ADN à partie de la suite de symboles entrante dans GF(4). La synthèse est basée sur la fonction de correspondance suivante :
0-> A α0 -> T α1 -> C α2 -> G.
[0070] Comme cela sera expliqué plus en détail ci-dessous, l’ordre dans lequel les nucléotides sont considérés et associés aux symboles 0, α, α1, α2 dans GF(4) correspond à l’ordre inverse des valeurs moyennes (de la plus élevée à la plus basse) des fonctions de densité de probabilité des amplitudes de chutes de courant obtenues pour un nucléotide donné. Dans l’exemple de la Fig. 3 et comme précisé dans le tableau de la Fig. 4, c’est le nucléotide A qui a la valeur moyenne la plus élevée, suivi, dans l’ordre par les nucléotides T, C puis G.
[0071] Des corrections d’erreurs d'insertion/suppression simples peuvent également être utilisées en intégrant des codes correcteurs pendant la synthèse, c’est-à-dire au niveau du composant 140. Les codes Tenengolts [cf : G. Tenengolts Nonbinary Codes "Correcting Single Délétion or Insertion" IEEE Transactions on Information Theory vol. ΓΓ-30 pp. 766-769 1984] sont bien adaptés à ce type d'erreurs et peuvent être directement encodés dans la séquence d'ADN. En outre, le problème de la reconstruction de la séquence d'ADN à partir de suppression / insertions suivies par des techniques de PCR a été examiné dans [9] [10], Comme nous nous concentrons dans ce document spécifiquement sur les techniques de séquençage à nanopores, nous supposons que la reconstruction de la séquence est idéale ou que nous n’avons pas à nous en préoccuper. Notons cependant que la reconstruction de séquence a motivé un grand nombre de recherches récentes [10] [11], Les composants 120 et 180 ne seront en outre pas décrits plus en détail dans ce document.
[0072] De manière symétrique au composant 140, le composant 160, est configuré pour réaliser le séquençage de l’ADN via un séquenceur à nanopore et ainsi la lecture d’une séquence d’ADN. [0073] Le composant 150 est configuré pour une édition d'ADN et correspond à un processus de suppression et d'insertion de sous-chaînes d'ADN à des endroits bien contrôlés. De plus, l'édition peut être effectuée en ajoutant des mutations ponctuelles très spécifiques [24] [25], Ces possibilités ne seront pas décrites plus en détail dans ce document.
[0074] Afin de rendre le système de stockage à base d'ADN plus robuste, des principes de codage de canaux de transmission de données sont exploités au niveau du composant 170 de décodage et adaptés à l’opération de séquençage. En particulier, l’opération de mesure d’amplitude de chute de courant pendant le séquençage (composant 160) à nanopore est modélisée comme un canal de transmission de données de sorte que le décodage puisse bénéficier des informations de fiabilité pour effectuer le décodage souple associées aux valeurs de mesure, c’est-à-dire des amplitudes de chute de courant mesurées pour chaque nucléotide.
[0075] Ainsi les mesures d’amplitude de chute de courant obtenues par le composant 160 sont converties en symboles dans GF(4) au moyen d’un procédé de décodage souple utilisant des informations de fiabilité. Lors du décodage souple réalisée par le composant 170, les blocs de contrôle de parité générés par le composant d’encodage 130 sont exploités, sont intégrés dans le décodage souple (pour N entrées, on a M symboles correspondant aux blocs de contrôle de parité) et permettent ainsi de corriger les erreurs de substitution lors du séquençage.
[0076] Les travaux présentés dans [26] montrent qu'il est possible d'optimiser les vitesses de translocation pour des nucléotides simples passant à travers un nanopore. Ceci est possible grâce à la haute viscosité de certains liquides ioniques à température ambiante.
Les gouttes actuelles ont été caractérisées statistiquement et montrent que les erreurs de substitution deviennent dominantes. Ainsi, le procédé de décodage souple présenté dans ce document est particulièrement adapté à la correction des erreurs produites par le séquençage. Le séquençage à nanopores (composant 160) génère en sortie des valeurs de mesures des chutes de courant produites par le passage de la séquence d’ADN au travers du nanopore sont transmises au composant 170. [0077] Détails du procédé de décodage souple (composant 1701
[0078] Pour les besoins de la modélisation, chaque valeur de mesure d’une chute de courant correspond à un échantillon. Un échantillon correspond à la réalisation d'une variable aléatoire gaussienne.
[0079] La Fig. 3 représente les distributions statistiques obtenues pour 4 types de nucléotides 'Α', T, 'C ou 'G' respectivement. Chaque courbe représente une distribution statistique des valeurs de chutes de courant obtenues pour un type de nucléotide. En pratique, la chaîne d’ADN ne pouvant pas être formée avec un seul type de nucléotide, on utilise plusieurs chaînes d’ADN connues passant à travers un séquenceur à nanopore et les valeurs de chute de courant sont mesurées de nombreuses fois (1000, 2000...) pour obtenir la distribution statistique pour un type de nucléotide donné. En l’occurrence, chaque distribution statistique correspond à une fonction de densité de probabilité gaussienne représentée par une courbe gaussienne correspondant à une variable aléatoire gaussienne.
[0080] Par exemple, sur la Fig. 3 :
- le nucléotide ‘A’ est associé à courbe gaussienne dont la moyenne correspond à une chute de courant de 1.25 nA ;
- le nucléotide ‘T’ est associé à courbe gaussienne dont la moyenne correspond à une chute de courant de 0.68 nA ;
- le nucléotide ‘C est associé à courbe gaussienne dont la moyenne correspond à une chute de courant de 0.65 nA ;
- le nucléotide ‘G’ est associé à courbe gaussienne dont la moyenne correspond à une chute de courant de 0.3 nA. [0081] En supposant que les quatre nucléotides sont équiprobables, un décodage dur qui utiliserait des seuils pour identifier chaque nucléotide conduirait à des taux d'erreur élevés car les courbes sont fortement superposées. Par exemple, comme illustré par la Fig. 3, il n’est pas possible lorsque la valeur de la chute de courant est comprise entre 0.3 et 1 de savoir de manière certaine ou avec une probabilité suffisante s’il s’agit du nucléotide G, C ou T. Par contre, si la valeur de la chute de courant est supérieure à 1, la probabilité qu’il s’agit du nucléotide A est quasiment de 100 ¾.
[0082] Pour réduire significativement ces taux d'erreur, un algorithme de décodage souple est exploité. Plus précisément, nous utilisons un algorithme Min-Sum étendu [27] appliqué à des éléments dans un Corps de Gai ois d’ordre q=4. Cet algorithme est basé sur une généralisation de l'algorithme Min-Sum utilisé pour les codes LDPC binaires présenté dans
[28] [29],
[0083] La chute de courant mesurée à un instant donné est modélisée comme une variable modulée par modulation d'impulsions en amplitude à 4 niveaux (notée ici 4-PAM, « Pulse Amplitude Modulation »), chaque niveau correspondant à la valeur moyenne de la fonction de densité de probabilité des amplitudes de chutes de courant obtenues pour un nucléotide donné. En outre, la modélisation prend en compte ces distributions statistiques en ajoutant à cette variable modulée 4 canaux de bruit blanc gaussien additif correspondant respectivement aux distributions statistiques obtenues pour les 4 nucléotides.
[0084] Calcul du message intrinsèque
[0085] En considérant la modulation 4-PAM et les B=4 canaux de bruit blanc gaussien additif (« Additive White Gaussian Noise », AWGN), les échantillons de courant bruités reçus à la sortie du séquenceur nanopore constituent une séquence bruitée Y de N symboles dans GF(4) affectés indépendamment par un bruit, où chaque échantillon est noté yk = PAM(xk) + nk, k= 1 à B. Le coefficient de modulation est représenté par PAM(xk) et nk est une variable aléatoire qui suit une fonction de densité de probabilité gaussienne avec une moyenne nulle et une variance notée [Math.2]
Figure imgf000021_0001
avec i= 1 à 4. La valeur de l’écart type σi dépend du type de nucléotide A, G, C, T à l'origine de la chute de courant courante et est déterminée à partir de la fonction de densité de probabilité normalisée des chutes de courant pour chaque nucléotide d'ADN, selon par exemple les valeurs données dans le tableau représenté à la Fig. 4. Dans ce tableau, on donne les valeurs moyennes Ci à C4 et les écarts types σ1 à σ4 pour les 4 distributions correspondant aux 4 nucléotides. Ce tableau est un exemple de valeurs possibles pour un séquenceur de séquençage donné. En pratique, pour chaque séquenceur et pour des conditions expérimentales données, une analyse statistique est mise en œuvre pour ce séquenceur, de sorte à obtenir les valeurs moyennes et écarts types propres au séquenceur utilisé et/ou aux conditions expérimentales.
[0086] Soit Lk(X), k= 1 à N, la valeur du logarithme du rapport de vraisemblance (Log Likehood Ratio, LLR) du k-ème symbole xk représentant l’échantillon k, k= 1 à N, dans un mot de code X à N symboles et [Math.3]
Figure imgf000022_0002
étant le symbole GF(4) qui maximise la probabilité de yk sachant x, notée P(yk|x) (probabilité conditionnelle). La première étape de l'algorithme Min-Sum est le calcul de la valeur Lk(x) pour chaque symbole x du mot de code. Avec l'hypothèse que les quatre nucléotides sont équiprobables, la valeur Lk(x) du symbole x dans le mot de code peut être définie par :
[Math.4]
Figure imgf000022_0001
avec
[Math.5]
Figure imgf000022_0003
Il est à noter que
[Math.6]
Figure imgf000022_0004
et que pour tout symbole x de GF(4) [Math.7]
Figure imgf000022_0005
( )
Ainsi, lorsque la valeur de Lk(x) d'un symbole x augmente, sa fiabilité diminue. Cette définition de la Lk(x) évite d'avoir à re-normaliser les messages après chaque mise à jour du nœud. [0087] Soit λk le message Min-Sum intrinsèque associé au k-ème symbole Xk sachant yk.
Le message intrinsèque λk est un vecteur composé de 4 couples (λk(i)L, λk(i)GF) pour i= 1 à 4, où λk(i)GF est un symbole GF(4) ( λk(l)GF=0,λk (1)GF= a,λk (1)GF=a\λk (1)GF=α2) et λk(i)L est la valeur LLR associée, calculée sur la base de la formule Math8 ci-dessous et telle que :λk(i)L = Lk(λk(i)GF). Les valeurs de LLRλk(i)L pour i= 1 à 4 vérifient la relation :
Figure imgf000022_0006
[0088] Avec le modèle de canal asymétrique considéré, la variable yk est considérée comme une variable bruitée modulée par modulation d'impulsions en amplitude à B=4 niveaux discrets, chaque niveau correspondant à une valeur moyenne de la fonction de densité de probabilité des mesures des chutes de courant mesurées pour un nucléotide donné parmi les B types de nucléotides. On peut calculer λk(i)L de la manière suivante :
[Math.8]
Figure imgf000023_0001
où Ci est la valeur moyenne de la fonction de densité de probabilité et ai l’écart type de la fonction de densité de probabilité obtenue pour le type de nucléotide i. Ci et σi résultent d’une analyse statistique propre au séquenceur utilisé, comme par exemple les valeurs présentées dans le tableau de la Fig. 4. Il faut noter que pour i= 1, λk (i)L = 0 .
[0089] Le message intrinsèque à l’entrée de l’algorithme de décodage est formé de 4 couples constitué par : une valeur LLR λk(i)L et un symbole dans GF(4), et ils sont ordonnés en fonction de la valeur LLR obtenue par l’équation Math.8. Les valeurs LLR λk(i)L sont normalisées, commençant par 0, conformément à l’équation Math.8. donnée plus haut. L’algorithme de décodage souple est ainsi basé sur une modélisation de la mesure de chute de courant produite par le séquenceur à nanopore comme une variable bruitée modulée par modulation d'impulsions en amplitude à B niveaux discrets, chaque niveau correspondant à une valeur moyenne de la fonction de densité de probabilité gaussienne des mesures des chutes de courant mesurées pour un nucléotide donné parmi les B types de nucléotides, la variable bruitée modulée étant bruitée par B canaux de bruit blanc gaussien additif correspondant respectivement aux distributions statistiques gaussiennes obtenues pour les B types de nucléotides.
[0090] Définition des messages correspondant à des arêtes du graphe de Tanner
[0091] On définit ici deux types de messages extrinsèques ou vecteurs de données correspondant aux arêtes du graphe de Tanner: pour une arête de ce graphe, on définit un message C2V ( « Check to Variable ») allant du nœud de parité CN au nœud de variable VN et un message V2C ( « Variable to Check») allant du nœud de variable VN au nœud de parité CN. Pour l’arête correspondant à l’élément hj,k, on note C2V(j,k) et V2C(j,k) les messages associés. [0092] Puisque dv= 2, seules 2 arêtes sont reliées à un nœud de variable VN k donné. On désigne C2V(jk(l),k) et C2V(jk(2),k) (respectivement V2C(jk(l),k) et V2C(jk(2),k)) les deux messages C2V (respectivement V2C) associés au VN k où jk(l) etjk(2) indiquent la position des deux valeurs non nulles de la colonne k de la matrice H. [0093] De même, on désigne C2V(j, kj(v)) (respectivement V2C(j, kj(v))) pour v= 1 à dc, les dc messages C2V (respectivement V2C) associés au CH j où kj(v) indiquent la position de la v-ème valeur non nulle de la ligne j de la matrice H.
[0094] La structure des messages V2C et C2V est identique à la structure du message intrinsèque λk. Le message de sortie V2C d’un VN ne doit contenir que les 4 valeurs triées LLR V2C(1)L et les symboles GF associés V2C(1)GF, avec /= 1 à 4. De même, le message C2N de sortie du CN contient les 4 valeurs LLR C2N(1)L (triées par ordre croissant) et les symboles GF C2N(1)GF qui leur sont associés.
[0095] Traitement pour chaque VN
[0096] Pour un symbole x, L(x), V2C(x) et C2V(x) sont respectivement les valeurs LLR intrinsèques, les messages extrinsèques V2C et C2V associées au symbole x. Les équations de décodage VN peuvent être divisées en trois étapes.
[0097] Etape 1 : le calcul de V2C(x) pour chaque x dans GF(4) [Math.11]
Figure imgf000024_0001
[0098] Etape 2 : la détermination du minimum de la valeur de V2C)
[Math.12]
Figure imgf000024_0003
[0099] Etape 3 : normalisation [Math.13]
Figure imgf000024_0002
[0100] Traitement pour chaque CN
[0101] Un nœud de parité de degré dc peut être décomposé nœuds de contrôle élémentaires, par exemple en 3(dc- 2) nœuds de contrôle élémentaires.
[0102] Pour minimiser la complexité des calculs, il est possible d’utiliser l'algorithme de Bubble-check au niveau du nœud de parité élémentaire décrit par exemple dans E. Boutillon, L. Conde-Canencia, « Simplified check node processing in nonbinary LDPC decoders », 6th International Symposium on Turbo Codes & Itérative Information Processing, Brest, France, Septembre 2010.
[0103] Décodage par un algorithme Min-Sum
[0104] Une matrice de contrôle de parité H est obtenue. Les valeurs non nulles de H peuvent être choisies aléatoirement parmi les éléments de GF(4). [0105] Dans un exemple de réalisation, des codes GF(4)-LDPC ultra-épars (à très faible densité) qui sont basés sur le protographe [21] [22] avec dv=2 sont utilisés. Les matrices correspondantes sont conçues pour maximiser la circonférence du graphe bipartite associé, et minimiser la multiplicité des cycles avec une longueur minimale [23], Chaque bloc de contrôle de parité utilise exactement dv=2 symboles distincts dans GF(4). Cette limitation dans le choix des valeurs réduit les besoins de stockage.
[0106] L'algorithme Min-Sum est appliqué sur la base du graphe bipartite de Tanner associé à la matrice de contrôle de parité H obtenu sur cette base.
[0107] L’algorithme Min-Sum étendu est appliqué ici en utilisant de nouvelles équations à la première étape du décodeur (c.-à-d. les calculs intrinsèques du rapport log- vraisemblance-rapport). De plus, comme nous visons à utiliser un traitement de nœuds de contrôle de complexité réduite, nous adaptons le travail préalable au cas des implémentations GF(4)-LDPC conviviales pour le matériel.
[0108] Le processus de décodage itère nit fois et pour chaque itération on effectue les opérations suivantes : M mises à jour des nœuds de contrôle CN (M étant le nombre de nœuds de contrôle) et M * de mises à jour de nœuds de variables VN. Lors de la dernière itération, une décision est prise pour chaque symbole, les symboles GF(4) décodés sont alors générés et constituent le mot de code ADN décodé.
[0109] La décision pour le mot de code est prise dans les processeurs VN et conclut le processus de décodage. Le décodeur est appliqué ensuite au mode de code suivant. [0110] Etapes du décodage par un algorithme Min-Sum [0111] Les étapes de l’algorithme Min-Sum peuvent être résumées comme suit.
[0112] Dans une phase d’initialisation, le message intrinsèque est généré pour k= 1 à N:<
Figure imgf000026_0001
ce message intrinsèque correspondant aux 4 valeurs Lk(x) calculées sur la base de la formule Math.1.
[0113] Le message V2C est calculé pour k= 1 à N et v=l à 2 : [Math.21]
Figure imgf000026_0004
[0114] Le décodage souple est ensuite réalisé de manière itérative. A chaque itération, les étapes suivantes sont mises en œuvre. Le nombre d’itération est fixé. Pour j= 1 à M : on effectue les étapes A) B) et C).
[0115] A) calcul du message extrinsèque V2C associé au nœud de parité CNj pour v= 1 à de :
Figure imgf000026_0002
[0116] B) mise en œuvre du traitement associé au nœud de parité CNj pour v= 1 à dc de sorte à générer des nouveaux messages C2V
Figure imgf000026_0003
[0117] C) pour chaque nœud de variable kj(v) connecté au nœud de parité CNj, on met à jour le deuxième message V2C en utilisant le nouveau message C2V et le message intrinsèque Lk [Math.23]
Figure imgf000026_0005
[0118] Puis les étapes A) à C) sont répétées à l’itération suivante. [0119] A l’issue des itérations, une décision finale est prise pour estimer le mot de code en utilisant le nouveau message C2V et le message intrinsèque Lk.
[0120] La décision êk pour k=1 à N s’exprime comme le symbole x sur GF(4) qui minimise la somme ci-dessous : [Math.24]
Figure imgf000027_0001
[0121] Pour plus de detail sur cet algorithme Min-Sum, on pourra se reporter au document de Boutillon, E., Conde-Canencia, L., Al Ghouwayel, A.“ Design of a GF(64)-LDPC Décoder Based on the EMS Algorithm“ IEEE Transactions on Circuits and Systems I, vol.60, no.10, pp.2644-2656, Oct. 2013, doi: 10.1109/TC SI.2013.22791862013.
[0122] D’autres exemples détaillés d’algorithmes Min-Sum sont décrits dans les références [29] et [28].
[0123] Procédé de décodage [0124] La fig. 5 représente de manière schématique un organigramme d’un procédé de décodage souple. Le procédé est appliqué à une séquence de données binaires encodée par une séquence de nucléotides à décoder comprenant B types de nucléotides, par exemple les B=4 nucléotides Adénine (A), Cytosine (C), Guanine (G) et Thymine (T). Le procédé est également applicable à des séquences d’ARN (acide ribonucléique) comprenant seulement 3 types de nucléotides tout en utilisant un corps de Galois d’ordre q=4.
[0125] Bien que les étapes soient décrites de manière séquentielle, les étapes peuvent être exécutées dans un ordre différent et/ou en parallèle. Certaines étapes peuvent être répétées ou être omises. Les caractéristiques et aspects du traitement de données décrits dans ce document notamment par référence aux figures 1 à 4 sont applicables à la mise en œuvre de ce procédé.
[0126] Lors d’une étape 510, pour chaque type de nucléotide parmi les N types de nucléotides, est obtenue une fonction de densité de probabilité gaussienne de mesures de chutes de courant, pour chaque type de nucléotide parmi les B types de nucléotides. Ces fonctions de densité de probabilité sont obtenues à partir d’une ou plusieurs séquences de nucléotides de référence dont la composition est connue, et des mesures de chutes de courant produites lors d’un ou plusieurs passage de ces séquences de nucléotides de référence à travers un séquenceur à nanopore. .
[0127] Lors d’une étape 520, des mesures d’amplitude de chute de courant produites au passage de la séquence de nucléotides à décoder à travers le dispositif à nanopore sont obtenues.
[0128] Lors d’une étape 530, on effectue un calcul pour chaque valeur de mesure et pour chaque type de nucléotide parmi les N types de nucléotides, d’une information de fiabilité sur la base de la fonction de densité de probabilité gaussienne obtenue pour le type de nucléotide considéré.
[0129] L’information de fiabilité pour une valeur de mesure yk et un type de nucléotide i est calculée selon l’équation Math.8 à partir de Ci, la valeur moyenne de la fonction de densité de probabilité, et σi, l’écart type de la fonction de densité de probabilité obtenue pour le type de nucléotide i. [0130] Lors d’une étape 540 on obtient une valeur décodée pour la valeur de mesure par application à chaque mesure de chute de courant considérée et aux N informations de fiabilité obtenues pour la valeur de mesure considérée d’un décodage souple avec un code correcteur d’erreur, le code correcteur d’erreur est un turbo code ou un code LDPC, Low- Density Parity-Check. [0131] Le décodage est basé sur une modélisation de la mesure de chute de courant produite par le dispositif à nanopore comme une variable bruitée modulée par modulation d'impulsions en amplitude à N niveaux discrets. Chaque niveau correspond à une valeur moyenne de la fonction de densité de probabilité gaussienne des mesures des chutes de courant obtenues pour un nucléotide donné parmi les N types de nucléotides. La variable bruitée modulée est bruitée par N canaux de bruit blanc gaussien additif correspondant respectivement aux distributions statistiques gaussiennes obtenues pour les N types de nucléotides.
[0132] Le nombre N de type de nucléotides est égal par exemple à 4 et le code correcteur d’erreur est appliqué à des données quaternaires (ou symboles) codées dans un Corps de Galois d’ordre 4.
[0133] Les étapes 520 à 540 sont répétées pour chaque mesure d’une amplitude de chute de courant produite au passage d’un nucléotide de la séquence de nucléotides à décoder à travers le dispositif à nanopore.
[0134] Les données quaternaires issues du décodage sont ensuite converties en sortie du bloc 190 en données binaires, selon ce qui a été décrit par référence à la fig. 2. [0135] Résultats
[0136] Des simulations de Monte-Carlo ont été effectuées pour obtenir des courbes de performance de la chaîne de stockage de données à base d'ADN avec un séquençage de nanopores. Pour cela, nous avons généré des séquences binaires aléatoires et les avons converties en séquences d'ADN, chaque nucléotide étant représenté par un symbole GF(4). Nous avons considéré N différentes valeurs et différents taux de codage pour le code LDPC, et nous les avons comparés aux résultats obtenus avec la détection dure.
[0137] Pour évaluer le gain de codage obtenu avec le code LDPC, nous avons considéré le taux d'erreur des nucléotides séquencés (SNER, « sequenced nucléotide error rate ») après l'étape d'appel de base avec HD (c.-à-d., schéma non codé) et le SNER codé (c.-à-d., où les échantillons souples du dispositif à nanopore sont les entrées du décodeur non binaire).
[0138] Pour les valeurs expérimentales présentées dans la table de la Fig. 3, nous avons obtenu un SNERHD simulé de 0,23, qui est du même ordre que les autres taux d'erreur signalés dans les dispositifs à nanopores [17], Les simulations ont été effectuées sur 106 séquences de nucléotides codés, c'est-à-dire un ensemble de données comprenant à la fois des informations originales et des symboles redondants formant des blocs de contrôle de parité. Nous avons utilisé des codes LDPC non binaires ultra-épars avec des séquences de N = 48 et 192 et 480 symboles GF(4), et des taux de codage R=1/2, 2/3 et 5/6. Pour tous les codes considérés, toutes les erreurs séquentielles ont été corrigées, ce qui a permis un séquençage quasi sans erreur. Pour être précis, compte tenu du nombre de lectures de nucléotides simulées, nous avons pu garantir des taux d'erreur de l'ordre de 10'9. Le fait de considérer des blocs plus grands (c.-à-d. des valeurs de N plus grandes) améliore le rendement. Ces simulations modélisent spécifiquement les erreurs de substitution et elles supposent une correction parfaite des erreurs d'insertion et de suppression. De plus, nos simulations supposent également une synthèse d'ADN sans erreur libre et des étapes d'alignement et de reconstruction optimales. Les résultats obtenus ici tiennent compte des valeurs présentées en Fig. 4 (conditions expérimentales décrites dans [26]) pour les calculs de LLR dans le décodeur souple. [0139] Les différentes contributions présentées dans ce document rendent possible l'utilisation de codes LDPC non binaires et de leurs algorithmes associés de décodage souple de faible complexité pour améliorer grandement la performance en matière d'erreurs. Les résultats de simulation obtenus avec des matrices LDPC ultra-éparses montrent que cette technique de codage est capable de corriger toutes les erreurs de séquençage de l'approche de décodage dure. Le nombre de séquences d'ADN considérées dans notre simulation peut garantir une performance quasi sans erreur (SNER de l'ordre de 10-9) si on suppose que l’on dispose d’une synthèse d'ADN sans erreur et une correction parfaite des insertions et des suppressions. [0140] Les résultats obtenus démontrent la faisabilité pratique des codes et décodeurs
LDPC non binaires dans les applications de stockage de l'ADN, avec des informations intrinsèques souples, modélisées de manière appropriée, utilisées en combinaison avec un décodeur Min-Sum optimisé.
[0141] Selon un mode de réalisation, tout ou partie des étapes du procédé de décodage décrits dans ce document sont mises en œuvre par un logiciel ou programme d'ordinateur.
[0142] Les fonctions et procédés décrits dans ce document peuvent ainsi être mises en oeuvre par logiciel (par exemple, via un logiciel sur un ou plusieurs processeurs, pour exécution sur un ordinateur à usage général (par exemple, via l'exécution par un ou plusieurs processeurs) afin d'implémenter un ordinateur à usage spécifique ou similaire) et/ou puissent être mises en œuvre dans du matériel (par exemple, en utilisant un ordinateur à usage général, un ou plusieurs circuits intégrés spécifiques (ASIC) et/ou tout autre équivalent matériel).
[0143] La présente description concerne ainsi un logiciel ou programme d'ordinateur, susceptible d’être exécuté par un dispositif informatique (par exemple, un ordinateur) servant de dispositif de décodage, au moyen d’un ou plusieurs processeurs de données, ce logiciel / programme comportant des instructions pour cause l'exécution par ce dispositif informatique de tout ou partie des étapes de l’un ou des procédés décrits dans ce document. Ces instructions sont destinées à être stockées dans une mémoire d’un dispositif informatique, chargées puis exécutées par un ou plusieurs processeurs de ce dispositif informatique de sorte à causer l’exécution par ce dispositif informatique du procédé concerné.
[0144] Ce logiciel / programme peut être codé au moyen de n’importe quel langage de programmation, et être sous la forme de rode source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n’importe quelle autre forme souhaitable.
[0145] Le dispositif informatique peut être mis en œuvre par une ou plusieurs machines physiquement distinctes. Le dispositif informatique peut présenter globalement l’architecture d’un ordinateur, incluant des constituants d’une telle architecture : mémoire(s) de données, processeur(s), bus de communication, interface(s) matérielle(s) pour la connexion de ce dispositif informatique à un réseau ou un autre équipement, interface(s) utilisateur, etc. [0146] Dans un mode de réalisation, tout ou partie des étapes du procédé de décodage décrits dans ce document sont mises en œuvre par un dispositif de décodage doté de moyens de mise en œuvre de ces étapes de ce procédé.
[0147] Ces moyens peuvent comprendre des moyens logiciels (software) (par ex. des instructions d'un ou plusieurs composants d’un programme) et/ou moyens matériels (hardware) (par ex. mémoire(s) de données, processeur(s), bus de communication, interface(s) matérielle(s), etc).
[0148] Des moyens mettant en œuvre une fonction ou un ensemble de fonctions peuvent également correspondre dans ce document à un composant logiciel, à un composant matériel ou bien à un ensemble de composants matériels et/ou logiciels, apte à mettre en œuvre la fonction ou l’ensemble de fonctions, selon ce qui est décrit ci-dessous pour les moyens concernés.
[0149] La présente description concerne aussi un support d'informations lisible par un processeur de données, et comportant des instructions d'un programme tel que mentionné ci-dessus. [0150] Le support d'informations peut être riimporte quel moyen matériel, entité ou dispositif, capable de stocker les instructions d'un programme tel que mentionné ci-dessus. Les supports de stockage de programme utilisables incluent les mémoires ROM ou RAM, les supports de stockage magnétiques tels que des disques magnétiques et des bandes magnétiques, les disques durs ou des supports de stockage de données numériques à lecture optique, etc ou toute combinaison de ces supports.
[0151] Dans certains cas, le support de stockage lisible par ordinateur n'est pas transitoire. Dans d’autres cas, le support d'informations peut être un support transitoire (par exemple, une onde porteuse) pour la transmission d’un signal (signal électromagnétique, électrique, radio ou optique) porteur des instructions de programme. Ce signal peut être acheminé via un moyen de transmission approprié, filaire ou non filaire : câble électrique ou optique, liaison radio ou infrarouge, ou par d'autres moyens.
[0152] Un mode de réalisation concerne également un produit programme d'ordinateur comprenant un support de stockage lisible par ordinateur sur lequel sont stockées des instructions de programme, les instructions de programme étant configurées pour causer la mise en œuvre par le dispositif informatique de tout ou partie des étapes d’un ou des procédés décrits ici lorsque les instructions de programme sont exécutées par un ou plusieurs processeurs et/ou un ou plusieurs composants matériels programmables.
[0153] Selon un mode de réalisation, tout ou partie des étapes du procédé de décodage décrits dans ce document sont mises en œuvre par circuit électronique, programmable ou non, spécifique ou non.
LISTE DES REFERENCES CITEES
[1] G. M. Church, Y. Gao, and S. Kosuri, “Next-generation digital information storage in DNA,” Science, vol. 337, no. 6102, pp. 1628-1628, 2012.
[2] N. Goldman, P. Bertone, S. Chen, C. Dessimoz, E. M. LeProust, B. Sipos, and E. Bimey, “Towards practical, high-capacity, lowmaintenance information storage in synthesized DNA,” Nature, vol. 494, no. 7435, pp. 77-80, February 2013.
[3] https://www.microsoft.com/en-us/research/project/DNA-storage/.
[4] https://bigthink. com/philip-perry/microsoft-plans-to-have-a-DNAbased- computer-by- 2020. [5] L. Conde-Canencia and L. Dolecek, “Nanopore DNA sequencing channel modeling,” in 2018 IEEE International Workshop on Signal Processing Systems (SiPS), Oct 2018, pp. 258-262.
[6] R. N. Grass, R. Heckel, M. Puddu, D. Paunescu, and W. J. Stark, “Robust Chemical préservation of digital information on DNA in silica with error-correcting codes,” Angewandte Chemie International Edition, vol. 54, no. 8, pp. 2552-2555.
[7] W. Wan et al., “Errer removal in microchip-synthesized DNA using immobilized muts.” Nucleic Acids Res., vol. 42(12), Jul 2014.
[8] H. M. Kiah, G. J. Puleo, and O. Milenkovic, “Codes for DNA sequence profiles,” IEEE Transactions on Information Theory, vol. 62, no. 6, pp. 3125-3146, June 2016. [9] F. Sala, R. Gabrys, C. Schoeny, and L. Dolecek, “Three novel combinatorial theorems for the insertion/deletion channel,” in 2015 IEEE International Symposium on Information Theory (ISIT), June 2015, pp. 2702-2706.
[10] F. Sala, R. Gabrys, C. Schoeny, K. Mazooji, and L. Dolecek, “Exact sequence reconstruction for insertion-correcting codes,” in 2016 IEEE Int. Symp. on Inf. Theory (ISIT), July 2016, pp. 615-619.
[11] R. Heckel, I. Shomorony, K. Ramchandran, and D. N. C. Tse, “Fundamental limits of DNA storage Systems,” CoRR, vol. ab s/1705.04732, 2017. [Online], Available: http://arxiv.org/abs/1705.04732
[12] M. G. Ross, C. Russ, M. Costello, A. Hollinger, N. J. Lennon, R. Hegarty, C. Nusbaum, and D. B. Jaffe, “Characterizing and measuring bias in sequence data,” Genome Biology, vol. 14, no. 5, p. R51, May 2013.
[13] F. Sala, R. Gabrys, C. Schoeny, and L. Dolecek, “Exact reconstruction from insertions in synchronization codes,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2428-2445, April 2017.
[14] R. Gabrys, H. M. Kiah, and O. Milenkovic, “Asymmetric Lee distance codes for DNA-based storage,” IEEE Transactions on Information Theory, vol. 63, no. 8, pp. 4982- 4995, Aug 2017. [15] R. Gabrys, E. Yaakobi, and O. Milenkovic, “Codes in the Damerau distance for DNA storage,” CoRR, vol. abs/1601.06885, 2016. [Online], Available: http://arxiv.org/abs/1601.06885
[16] C. Schoeny, F. Sala, and L. Dolecek, “Novel combinatorial coding results for DNA sequencing and data storage,” IEEE Asilomar Conférence on Signais, Systems, and Computers, vol. abs/1801.04882, Oct. 2017.
[17] C. R. O’Donnel, H. Wang, and W. B. Dunbar, “Errer analysis of idealized nanopore sequencing,” Electrophoresis, vol. 34(15), pp. 2137 - 2144, Aug. 2013.
[18] C. Schoeny, A. Wachter-Zeh, R. Gabrys, and E. Yaakobi, “Codes correcting a burst of délétions or insertions,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1971-1985, April 2017.
[19] C. Poulliat, M. Fossorier, and D. Declercq, “Design of regular (2, de)- LDPC codes over GF(q) using their binary images,” IEEE Trans. Commun., vol. 56, no. 10, pp. 1626- 1635, Oct. 2008.
[20] X.-Y. Hu and E. Eleftheriou, “Binary représentation of cycle Tanner graph GF(2b) codes,” in IEEE Int. Conf. Commun. ICC’ 2004. Paris, France, June 2004.
[21] L. Zeng, L. Lan, Y. Tai, S. Song, S. Lin, and K. Abdel-Ghaffar, “Transactions papers - constructions of nonbinary quasi-cyclic LDPC codes: A finite field approach,” Communications, IEEE Transactions on, vol. 56, no. 4, pp. 545 -554, april 2008.
[22] R. Peng and R. Chen, “Design of nonbinary quasi-cyclic LDPC cycle codes,” in Information Theory Workshop. Tahoe City, USA, Sept. 2007, pp. 13-18.
[23] A. Venkiah, D. Declercq, and C. Poulliat, “Design of cages with a randomized progressive edge growth algorithm” IEEE Commun. Letters, vol. 12(4), pp. 301-303,
April 2008.
[24] I. Wataru, I. Hiroshi, and K. Yoshikazu, “A general method for introducing a sériés of mutations into cloned DNA using the polymerase chain reaction,” Gene, vol. 102, no. 1, pp. 67 -70, 1991.
[25] R. Higuchi, B. Krummel, and R. Saiki, “A general method of in vitro préparation and spécifie mutagenesis of DNA fragments: study of protein and DNA interactions,” Nucleic Acids Res., no. 16, pp. 7351-67, August 1988.
[26] J. Feng, K. Liu, R. D. Bulushev, S. Khlybov, D. Dumcenco, A. Kis, and A. Radenovic, “Identification of single nucléotides in MoS2 nanopores,” Nature Nanotechnology, vol. 10, pp. 1070-1078, Dec 2015. [27] A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, “Low complexity, low memory EMS algorithm for non-binary LDPC codes,” in IEEE Intem. Conf. on Commun., ICC’2007. Glasgow, England, June 2007.
[28] J. Zhao, F. Zarkeshvari, and A. H. Banihashemi, “On implémentation of min-sum algorithm and its modifications for decoding LDPC codes,” IEEE Trans. Commun., vol. 53, no. 4, pp. 549-554, April 2005.
[29] D. Declercq and M. Fossorier, “Decoding algorithme for nonbinary LDPC codes over GF(q),” IEEE Trans. Comm., vol. 55, no. 4, pp. 633- 643, April 2007.
[30] V. Savin, “Min-max decoding for non binary LDPC codes,” in Proc. IEEE Int. Symp. Information Theory, ISIT’2008. Toronto, Canada, July 2008. [31] H. Wymeersch, H. Steendam, and M. Moeneclaey, “Log-domain decoding of LDPC codes over GF(q),” in IEEE Intem. Conf. on Commun., ICC’2004. Paris, France, June 2004, pp. 772-776.
[32] E. Boutillon and L. Conde-Canencia, “Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders,” Electronics Letters, vol. 46, no. 9, pp. 633-634, April 2010.

Claims

Revendications
1. Procédé de décodage d’une séquence de données binaires encodées par une séquence de nucléotides à décoder comprenant B types de nucléotides d’ADN, B étant un nombre entier égal à 2, 3 ou 4, le procédé de décodage comprenant: - une obtention (510), pour chaque type de nucléotide parmi les B types de nucléotides, d’une fonction de densité de probabilité, les fonctions de densité de probabilité étant obtenues à partir de mesures de chutes de courant produites lors d’au moins un passage d’au moins une séquence de nucléotides de référence à travers un séquenceur à nanopore ;
- une obtention (520) de mesures de chute de courant (y1, y2, ...yk) produites au passage de la séquence de nucléotides à décoder à travers le séquenceur à nanopore;
- un calcul (530), pour au moins une valeur de mesure et pour chaque type de nucléotide parmi les B types de nucléotides, d’une information de fiabilité (λk (i)L) sur la base de la fonction de densité de probabilité obtenue pour le type de nucléotide considéré;
- une obtention (540) pour chaque valeur de mesure considérée, d’une valeur décodée identifiant un type de nucléotide parmi les B types de nucléotides d’ADN par application à la mesure de chute de courant et aux B informations de fiabilité obtenues pour la valeur de mesure considérée d’un algorithme de décodage souple avec un code correcteur d’erreur.
2. Procédé selon la revendication 1, dans lequel la fonction de densité de probabilité est une fonction de densité de probabilité gaussienne et l’algorithme de décodage souple est basé sur une modélisation de la mesure de chute de courant produite par le séquenceur à nanopore comme une variable bruitée modulée par modulation d'impulsions en amplitude à B niveaux discrets, chaque niveau correspondant à une valeur moyenne de la fonction de densité de probabilité obtenue pour un type de nucléotide donné, la variable bruitée modulée étant bruitée par B canaux de bruit blanc gaussien additif correspondant respectivement aux distributions statistiques obtenues pour les B types de nucléotides.
3. Procédé selon la revendication 1 ou 2 dans lequel le code correcteur d’erreur est un turbo code ou un algorithme de décodage de code LDPC, Low-Density Parity-Check.
4. Procédé revendication selon l’une quelconque des revendications précédentes, dans lequel l’algorithme de décodage souple est un algorithme Min-Sum pour codes LDPC, Low-Density Parity-Check ou un algorithme par propagation de croyance pour codes LDPC.
5. Procédé selon la revendication selon l’une quelconque des revendications précédentes dans lequel le nombre B de type de nucléotides est égal à 4 et l’algorithme de décodage souple avec code correcteur d’erreur est appliqué à des symboles codés dans un Corps de Galois d’ordre 4, chaque symbole dans le Corps de Galois d’ordre 4 correspondant à un nucléotide.
6. Procédé selon la revendication 5 dans lequel l’ordre dans lequel les types de nucléotides sont associés aux symboles dans le Corps de Galois d’ordre 4 correspond à l’ordre inverse des valeurs moyennes des fonctions de densité de probabilité des amplitudes de chutes de courant obtenues pour les différents types de nucléotide.
7. Procédé selon l’une quelconque des revendications précédentes dans lequel l’information de fiabilité pour une valeur de mesure yk et un type de nucléotide i est calculée comme suit :
[Math.8]
Figure imgf000037_0001
où Ci est la valeur moyenne de la fonction de densité de probabilité et ai l’écart type de la fonction de densité de probabilité obtenue pour le type de nucléotide i.
8. Dispositif de décodage comprenant au moins une mémoire et au moins un processeur, ladite au moins une mémoire stockant des instructions de programme configurées pour causer l’exécution par ledit dispositif de décodage des étapes d’un procédé selon l'une quelconque des revendications 1 à 7 lorsque les instructions de programme sont exécutées par ledit au moins processeur.
9. Programme d'ordinateur comportant des instructions de programme pour l'exécution des étapes d’un procédé selon l'une quelconque des revendications 1 à 7 lorsque ledit programme est exécuté par un ordinateur.
10. Support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur comprenant des instructions de programme pour l'exécution des étapes d’un procédé selon l'une quelconque des revendications 1 à 7 lorsque ledit programme est exécuté par un ordinateur.
11. Système de stockage de données à base d’ADN, comprenant un séquenceur à nanopore et un dispositif de décodage selon la revendication 8.
PCT/FR2021/050826 2020-05-15 2021-05-11 Procédé et dispositif de décodage de données stockées dans un système de stockage à base d'adn Ceased WO2021229184A1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US17/925,562 US20230187024A1 (en) 2020-05-15 2021-05-11 Method and device for decoding data stored in a DNA-based storage system
EP21731261.0A EP4150114A1 (fr) 2020-05-15 2021-05-11 Procédé et dispositif de décodage de données stockées dans un système de stockage à base d'adn

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR2004819A FR3110177A1 (fr) 2020-05-15 2020-05-15 procédé et dispositif de décodage de données stockées dans un système de stockage à base d'ADN
FRFR2004819 2020-05-15

Publications (1)

Publication Number Publication Date
WO2021229184A1 true WO2021229184A1 (fr) 2021-11-18

Family

ID=72885610

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/FR2021/050826 Ceased WO2021229184A1 (fr) 2020-05-15 2021-05-11 Procédé et dispositif de décodage de données stockées dans un système de stockage à base d'adn

Country Status (4)

Country Link
US (1) US20230187024A1 (fr)
EP (1) EP4150114A1 (fr)
FR (1) FR3110177A1 (fr)
WO (1) WO2021229184A1 (fr)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12380338B2 (en) * 2021-03-08 2025-08-05 Microsoft Technology Licensing, Llc Codes to detect insertion and deletion errors in a dense storage medium
US20230215516A1 (en) * 2022-01-05 2023-07-06 Quantum Corporation Joint multi-nanopore sequencing for reliable data retrieval in nucleic acid storage
CN114328000B (zh) * 2022-01-10 2022-08-23 天津大学 1型2型分段纠错内码的dna存储级联编码与解码方法
US20250191696A1 (en) * 2023-12-06 2025-06-12 Western Digital Technologies, Inc. Dna data storage device with variable reliability tiers

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2012088339A2 (fr) * 2010-12-22 2012-06-28 Genia Technologies, Inc. Caractérisation de molécules individuelles d'adn, sur nanopores, à l'aide de ralentisseurs
WO2017083828A1 (fr) * 2015-11-12 2017-05-18 Samuel Williams Séquençage rapide de fragments d'adn court à l'aide de la technologie des nanopores
WO2017184677A1 (fr) * 2016-04-21 2017-10-26 President And Fellows Of Harvard College Méthode et système de codage d'informations à base de nanopores
WO2018132457A1 (fr) * 2017-01-10 2018-07-19 Roswell Biotechnologies, Inc. Procédés et systèmes de stockage de données d'adn
EP3419180A1 (fr) * 2017-06-19 2018-12-26 Universite De Bretagne Sud Décodage de type min-sum (ems) etendu basé sur syndrome prétrié simplifié de codes ldpc non binaire
WO2019075100A1 (fr) * 2017-10-10 2019-04-18 Roswell Biotechnologies, Inc. Procédés, appareil et systèmes pour le stockage de données d'adn sans amplification

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2012088339A2 (fr) * 2010-12-22 2012-06-28 Genia Technologies, Inc. Caractérisation de molécules individuelles d'adn, sur nanopores, à l'aide de ralentisseurs
WO2017083828A1 (fr) * 2015-11-12 2017-05-18 Samuel Williams Séquençage rapide de fragments d'adn court à l'aide de la technologie des nanopores
WO2017184677A1 (fr) * 2016-04-21 2017-10-26 President And Fellows Of Harvard College Méthode et système de codage d'informations à base de nanopores
WO2018132457A1 (fr) * 2017-01-10 2018-07-19 Roswell Biotechnologies, Inc. Procédés et systèmes de stockage de données d'adn
EP3419180A1 (fr) * 2017-06-19 2018-12-26 Universite De Bretagne Sud Décodage de type min-sum (ems) etendu basé sur syndrome prétrié simplifié de codes ldpc non binaire
WO2019075100A1 (fr) * 2017-10-10 2019-04-18 Roswell Biotechnologies, Inc. Procédés, appareil et systèmes pour le stockage de données d'adn sans amplification

Non-Patent Citations (37)

* Cited by examiner, † Cited by third party
Title
A. VENKIAHD. DECLERCQC. POULLIAT: "Design of cages with a randomized progressive edge growth algorithm", IEEE COMMUN. LETTERS, vol. 12, no. 4, April 2008 (2008-04-01), pages 301 - 303
A. VOICILAD. DECLERCQF. VERDIERM. FOSSORIERP. URARD: "Low complexity, low memory EMS algorithm for non-binary LDPC codes", IEEE INTERN. CONF. ON COMMUN., ICC'2007. GLASGOW, ENGLAND, June 2007 (2007-06-01)
ALDRIN KAY-YUEN YIM ET AL: "The Essential Component in DNA-Based Information Storage System: Robust Error-Tolerating Module", FRONTIERS IN BIOENGINEERING AND BIOTECHNOLOGY, vol. 2, 6 November 2014 (2014-11-06), XP055374159, DOI: 10.3389/fbioe.2014.00049 *
BOUTILLON, E.CONDE-CANENCIA, L.AL GHOUWAYEL, A.: "Design of a GF(64)-LDPC Decoder Based on the EMS Algorithm", IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I,, vol. 60, no. 10, October 2013 (2013-10-01), pages 2644 - 2656, XP011528051, DOI: 10.1109/TCSI.2013.2279186
C. POULLIATM. FOSSORIERD. DECLERCQ: "Design of regular (2,dc)- LDPC codes over GF(q) using their binary images", IEEE TRANS. COMMUN., vol. 56, no. 10, October 2008 (2008-10-01), pages 1626 - 1635, XP011236194, DOI: 10.1109/TCOMM.2008.060527
C. R. O'DONNELH. WANGW. B. DUNBAR: "Error analysis of idealized nanopore sequencing", ELECTROPHORESIS, vol. 34, no. 15, August 2013 (2013-08-01), pages 2137 - 2144
C. SCHOENYA. WACHTER-ZEHR. GABRYSE. YAAKOBI: "Codes correcting a burst of deletions or insertions", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 63, no. 4, April 2017 (2017-04-01)
C. SCHOENYF. SALAL. DOLECEK: "Novel combinatorial coding results for DNA sequencing and data storage", IEEE ASILOMAR CONFÉRENCE ON SIGNAIS, SYSTEMS, AND COMPUTERS, October 2017 (2017-10-01)
CHANDAK SHUBHAM ET AL: "Overcoming High Nanopore Basecaller Error Rates for DNA Storage via Basecaller-Decoder Integration and Convolutional Codes", ICASSP 2020 - 2020 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING (ICASSP), IEEE, 4 May 2020 (2020-05-04), pages 8822 - 8826, XP033793113, DOI: 10.1101/2019.12.20.871939 *
CONDE-CANENCIA LAURA ET AL: "Nanopore DNA Sequencing Channel Modeling", 2018 IEEE INTERNATIONAL WORKSHOP ON SIGNAL PROCESSING SYSTEMS (SIPS), IEEE, 21 October 2018 (2018-10-21), pages 258 - 262, XP033490361, DOI: 10.1109/SIPS.2018.8598361 *
D. DECLERCQ ET M. FOSSORIER, IEEE TRANS. COMMUN., vol. 4, April 2007 (2007-04-01), pages 633 - 643
D. DECLERCQM. FOSSORIER: "Decoding algorithms for nonbinary LDPC codes over GF(q", IEEE TRANS. COMM., vol. 55, no. 4, April 2007 (2007-04-01), pages 633 - 643, XP011177031, DOI: 10.1109/TCOMM.2007.894088
E. BOUTILLONL. CONDE-CANENCIA: "Bubble check: a simplifïed algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders", ELECTRONICS LETTERS, vol. 46, no. 9, April 2010 (2010-04-01), pages 633 - 634, XP006035504, DOI: 10.1049/EL:20100566
F. SALAR. GABRYSC. SCHOENYK. MAZOOJIL. DOLECEK: "Exact sequence reconstruction for insertion-correcting codes", 2016 IEEE INT. SYMP. ON INF. THEORY (ISIT, July 2016 (2016-07-01), pages 615 - 619, XP032940314, DOI: 10.1109/ISIT.2016.7541372
F. SALAR. GABRYSC. SCHOENYL. DOLECEK: "Exact reconstruction from insertions in synchronization codes", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 63, no. 4
F. SALAR. GABRYSC. SCHOENYL. DOLECEK: "Three novel combinatorial theorems for the insertion/deletion channel", 2015 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT, June 2015 (2015-06-01), pages 2702 - 2706, XP033220265, DOI: 10.1109/ISIT.2015.7282947
FEI PENG ET AL: "LDPC Codes for Portable DNA Storage", 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), IEEE, 7 July 2019 (2019-07-07), pages 76 - 80, XP033620453, DOI: 10.1109/ISIT.2019.8849814 *
G. M. CHURCHY. GAOS. KOSURI: "Next-generation digital information storage in DNA", SCIENCE, vol. 337, no. 6102, 2012, pages 1628 - 1628
H. M. KIAHG. J. PULEOO. MILENKOVIC: "Codes for DNA sequence profiles", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 62, no. 6, June 2016 (2016-06-01), pages 3125 - 3146
H. WYMEERSCHH. STEENDAMM. MOENECLAEY: "Log-domain decoding of LDPC codes over GF(q", IEEE INTERN. CONF. ON COMMUN., ICC'2004. PARIS, FRANCE, June 2004 (2004-06-01), pages 772 - 776
I. WATARUI. HIROSHIK. YOSHIKAZU: "A général method for introducing a series of mutations into cloned DNA using the polymerase chain reaction", GEN, vol. 102, no. 1, 1991, pages 67 - 70
J. FENGK. LIUR. D. BULUSHEVS. KHLYBOVD. DUMCENCOA. KISA. RADENOVIC: "Identification of single nucleotides in MoS2 nanopores", NATURE NANOTECHNOLOGY, vol. 10, December 2015 (2015-12-01), pages 1070 - 1078
J. ZHAOF. ZARKESHVARIA. H. BANIHASHEMI: "On implementation of min-sum algorithm and its modifications for decoding LDPC codes", IEEE TRANS. COMMUN., vol. 53, no. 4, April 2005 (2005-04-01), pages 549 - 554, XP011131324, DOI: 10.1109/TCOMM.2004.836563
L. CONDE-CANENCIAL. DOLECEK: "Nanopore DNA sequencing channel modeling", 2018 IEEE INTERNATIONAL WORKSHOP ON SIGNAL PROCESSING SYSTEMS (SIPS, October 2018 (2018-10-01), pages 258 - 262, XP033490361, DOI: 10.1109/SiPS.2018.8598361
L. ZENGL. LANY. TAIS. SONGS. LINAND K. ABDEL-GHAFFAR: "Transactions papers - constructions of nonbinary quasi-cyclic LDPC codes: A finite field approach", COMMUNICATIONS, IEEE TRANSACTIONS, vol. 56, no. 4, April 2008 (2008-04-01), pages 545 - 554
M. G. ROSSC. RUSSM. COSTELLOA. HOLLINGERN. J. LENNONR. HEGARTYC. NUSBAUMD. B. JAFFE: "Characterizing and measuring bias in sequence data", GENOME BIOLOGY, vol. 14, no. 5, May 2013 (2013-05-01), pages R51
N. GOLDMANP. BERTONES. CHENC. DESSIMOZE. M. LEPROUSTB. SIPOSE. BIRNEY: "Towards practical, high-capacity, lowmaintenance information storage in synthesized DNA", NATURE, vol. 494, no. 7435, February 2013 (2013-02-01), pages 77 - 80
R. GABRYSE. YAAKOBIO. MILENKOVIC: "Codes in the Damerau distance for DNA storage", CORR, 2016
R. GABRYSH. M. KIAHO. MILENKOVIC: "Asymmetric Lee distance codes for DNA-based storage", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 63, no. 8, August 2017 (2017-08-01), pages 4982 - 4995
R. HECKELI. SHOMORONYK. RAMCHANDRAND. N. C. TSE: "Fundamental limits of DNA storage systems", CORR, 2017, Retrieved from the Internet <URL:http://arxiv.org/abs/1705.04732>
R. HIGUCHIB. KRUMMELR. SAIKI: "A général method of in vitro préparation and spécifié mutagenesis of DNA fragments: study of protein and DNA interactions", NUCLEIC ACIDS RES., vol. 16, August 1988 (1988-08-01), pages 7351 - 67
R. N. GRASSR. HECKELM. PUDDUD. PAUNESCUW. J. STARK: "Robust chemical préservation of digital information on DNA in silica with error-correcting codes", ANGEWANDTE CHEMIE INTERNATIONAL EDITION, vol. 54, no. 8, pages 2552 - 2555
R. PENGR. CHEN: "Design of nonbinary quasi-cyclic LDPC cycle code", INFORMATION THEORY WORKSHOP. TAHOE CITY, USA, September 2007 (2007-09-01), pages 13 - 18, XP031136563
V. SAVIN: "Min-max decoding for non binary LDPC codes", PROC. IEEE INT. SYMP. INFORMATION THEORY, ISIT'2008. TORONTO, CANADA, July 2008 (2008-07-01)
W. WAN ET AL.: "Error removal in microchip-synthesized DNA using immobilized muts", NUCLEIC ACIDS RES., vol. 42, no. 12, July 2014 (2014-07-01)
X.-Y. HUE. ELEFTHERIOU: "Binary représentation of cycle Tanner graph GF(2b) codes", IEEE INT. CONF. COMMUN. ICC'2004. PARIS, FRANCE, June 2004 (2004-06-01)
YIXIN WANG ET AL: "High capacity DNA data storage with variable-length Oligonucleotides using repeat accumulate code and hybrid mapping", JOURNAL OF BIOLOGICAL ENGINEERING, vol. 13, no. 1, 21 November 2019 (2019-11-21), XP055764162, DOI: 10.1186/s13036-019-0211-2 *

Also Published As

Publication number Publication date
FR3110177A1 (fr) 2021-11-19
US20230187024A1 (en) 2023-06-15
EP4150114A1 (fr) 2023-03-22

Similar Documents

Publication Publication Date Title
WO2021229184A1 (fr) Procédé et dispositif de décodage de données stockées dans un système de stockage à base d&#39;adn
Welzel et al. DNA-Aeon provides flexible arithmetic coding for constraint adherence and error correction in DNA storage
EP2095512B1 (fr) Procédé et dispositif de décodage pour codes ldpc, et appareil de communication comprenant un tel dispositif
EP2047605B1 (fr) Procédé de décodage à passage de messages avec un classement des noeuds selon la fiabilité de voisinage
JP3893383B2 (ja) Ｌｄｐｃ符号用検査行列生成方法および検査行列生成装置
FR3016259A1 (fr) Procede de gestion d&#39;une unite de calcul de noeud de parite, equipement et logiciel pour la mise en oeuvre du procede
WO2003056705A1 (fr) Procede de generation de matrice d&#39;examen de code ldpc
EP3879708B1 (fr) Décodage des codes ldpc avec basculement de bits sélectif
JP2002353946A (ja) 有限サイズのデータブロックに対して誤り訂正符号を評価する方法
EP1959572B1 (fr) Procédé de décodage à passage de messages et à convergence forcée
FR2849514A1 (fr) Code de geometrie algebrique adapte aux erreurs en rafale
CN113890543B (zh) 基于多层感知神经网络的多进制ldpc码的译码方法
WO2008059160A2 (fr) Codage et decodage d&#39;un signal de donnees en fonction d&#39;un code correcteur
Conde-Canencia et al. Nanopore DNA sequencing channel modeling
FR3009462B1 (fr) Procede ameliore de decodage d&#39;un code correcteur avec passage de message, en particulier pour le decodage de codes ldpc ou codes turbo
Sakogawa et al. Symbolwise MAP estimation for multiple-trace insertion/deletion/substitution channels
Zhao et al. Progressive algebraic Chase decoding algorithms for Reed–Solomon codes
Pal et al. Error-Control Coding Algorithms and Architecture for Modern Applications Powered by LDPC Codes and Belief Propagation
EP4233177B1 (fr) Décodage efficace de codes gldpc
FR2913836A1 (fr) Codage et decodage de signaux de donnees de rendements variables
Lavauzelle Codes with locality: constructions and applications to cryptographic protocols
FR3061393A1 (fr) Procedes de codage et de decodage de paquets de donnees dans un corps de galois
Taghavi Decoding linear codes via optimization and graph-based techniques
Shen Analysis and error performances of convolutional doubly orthogonal codes with non-binary alphabets
Jardel Distributed coding and computing for networks

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 21731261

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2021731261

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2021731261

Country of ref document: EP

Effective date: 20221215

NENP Non-entry into the national phase

Ref country code: DE

WWW Wipo information: withdrawn in national office

Ref document number: 2021731261

Country of ref document: EP