FR 3110177 A1 20211119 FR 2004819 A 20200515 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, le procédé de décodage 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 pour la valeur de mesure par application à la mesure de chute de courant et aux B informations de fiabilité d’un algorithme de décodage souple avec un code correcteur d’erreur. Figure pour l’abrégé : fig. 5 procédé et dispositif de décodage de données stockées dans un système de stockage à base d'ADN 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 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. 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]) . 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. 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. 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. 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. 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] . 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. 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. 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) 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 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, 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 (y 1 , y 2 , …y k ) 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 d’une valeur décodée pour chaque valeur de mesure considérée 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. 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. Dans des exemples de réalisation, l’algorithme de décodage souple avec 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. 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 données quaternaires codées dans un Corps de Galois d’ordre 4, chaque symbole 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. Dans des exemples de réalisation, l’information de fiabilité pour une valeur de mesure y k et un type de nucléotide i est calculée comme suit : [Math.201] 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. 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. 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. 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. 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 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 : illustre des aspects du calcul de blocs de parité dans un procédé de codage selon un ou plusieurs modes de réalisation; est une représentation schématique d’un système de stockage à base d'ADN selon un ou plusieurs modes de réalisation; 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; représente un tableau de paramètres (moyenne et écart type) des distributions statistiques présentées à la Fig. 3; représente un organigramme d’un procédé de décodage souple selon un ou plusieurs modes de réalisation. DESCRIPTION DETAILLEE 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 . 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. Les contributions décrites dans ce document portent spécifiquement sur la correction des erreurs de substitution produites lors du séquençage à nanopores. 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. 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. 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. Définitions et principes 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 α. Les éléments (ou symboles) du corps de Galois GF(q) sont notés {0, α 0 , α 1 , … α q-2 }. Un mot de code (« codeword », selon la terminologie anglo-saxonne) est noté X = {x 1 , x 2 , …. x N }, où {x k }, k= 1 à N, est un élément (ou symbole) appartenant à un corps de Galois GF(q) et est représenté par m = log 2 (q) bits avec x k = { x k ,1 , x k,2 , ….x k,m }. 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 nuls 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ée . La matrice de parité est liée à une matrice dite de génération du code, généralement notée , par la relation : où désigne la matrice transposée de . Les dimensions de la matrice de parité correspondent, pour le nombre de lignes , au nombre de contraintes de parité du code, et pour le nombre de colonnes , à 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é 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é sera vérifiée pour tout mot de code . 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 ( ) 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 et dans la suite. 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 nuls appartiennent à un champ fini GF(q), où q >2. On considère dans ce document le cas d’un corps de Galois d’ordre q = 4. 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 d c symboles de mots de code s’écrit : où h j,k sont les valeurs non nulles de la j-ème ligne de la matrice H et un mot de code est désigné par X = {x 1 , x 2 , …. x N }, où x k est un symbole représenté par m=log 2 (q)= 2 bits dans le cas où q = 4. . On note d c le nombre de 1 dans une ligne de la matrice H et d v le nombre de 1 dans une colonne de la matrice H. 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. 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 , et , et N = 6 nœuds de variable notés , , , , et . Les trois équations de parité correspondant respectivement aux trois nœuds de parité de ce graphe sont : pour le nœud de parité , pour le nœud de parité , pour le nœud de parité , où les opérateurs et désignent respectivement l’addition et la multiplication dans le corps de Galois GF(4). Le graphe de Tanner 110 représente le traitement itératif appliqué à chaque mot de code à décoder. Les nœuds de variable VN k reçoivent chacun un vecteur λ k composé de B=4 couples de valeurs pour chaque valeur de mesure d’entrée y k 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 VN k reçoit un vecteur λ k calculé par un bloc de calcul 10 k à partir de l’entrée y k pour décoder le symbole x k d’un mot de code X. 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 x k possible dans GF(4) = {0, α 0 , α 1 , α 2 } et d’une information de fiabilité associée, notée avec i = 1 à 4. Le vecteur d’entrée λ k est ainsi défini comme suit : . 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) , c’est-à-dire la valeur la plus probable ou celle dont l’erreur de décodage est la plus faible. Le nœud de variable VN k reçoit ainsi un vecteur décodé contenant la valeur décodée pour le symbole x k du mot de code X. 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 »). 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). 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. 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 d v =2. 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ù α est l'élément primitif de ce Corps de Galois. Un élément de GF(q) est ainsi représenté par m = log 2 (q) = 2 bits. Les éléments de GF(4) sont également appelés des symboles. Les unité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). 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. 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. 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 x k décodé dans GF(4) est obtenu pour chaque mesure y k 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. 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. Dans des exemples de réalisation, des informations de fiabilité sont calculées à partir d’une valeur de mesure y k 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. 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é). 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é). 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 messages en entrée et génère 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. 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 d c - 1. Cela conduit à une complexité de calcul de l’ordre de O( q 2 ) . 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 O(d c × q ×log( q ) ) . Il 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. 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 n m symboles les plus fiables, n m étant choisi très inférieur à q ( n m q ). Cependant, vu l’ordre relativement faible du corps de Galois, nous considérons ici que n m = q = 4 . 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 n m couples (symbole, fiabilité) à partir desquels il génère un message de sortie contenant les n m meilleures combinaisons possibles des deux messages en entrée, le nombre total de combinaisons étant égal à n m à la puissance 2. 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. 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. 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. 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 . 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. 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. 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. 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 'A', 'T', 'C' et 'G'). 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. 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. 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. 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. 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 Deletion or Insertion" IEEE Transactions on Information Theory vol. IT-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. 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. 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. 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. 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. 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. Détails du procédé de décodage souple (composant 170) 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. La Fig. 3 représente les distributions statistiques obtenues pour 4 types de nucléotides 'A', '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. 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. 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 %. 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 Galois 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]. 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. Calcul du message intrinsèque 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é y k = PAM(x k ) + n k , k= 1 à B. Le coefficient de modulation est représenté par PAM(x k ) et n k 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] 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 C 1 à C 4 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. Soit L k (X), k= 1 à N, la valeur du logarithme du rapport de vraisemblance (Log Likehood Ratio, LLR) du k-ème symbole x k représentant l’échantillon k, k= 1 à N, dans un mot de code X à N symboles et [Math.3] étant le symbole GF(4) qui maximise la probabilité de y k sachant x, notée P(y k |x) (probabilité conditionnelle ). La première étape de l'algorithme Min-Sum est le calcul de la valeur L k (x) pour chaque symbole x du mot de code. Avec l'hypothèse que les quatre nucléotides sont équiprobables, la valeur L k (x) du symbole x dans le mot de code peut être définie par : [Math.4] avec [Math.5] Il est à noter que [Math.6] et que pour tout symbole x de GF(4) [Math.7] Ainsi, lorsque la valeur de L k (x) d'un symbole x augmente, sa fiabilité diminue. Cette définition de la L k (x) évite d'avoir à re-normaliser les messages après chaque mise à jour du nœud. Soit λ k le message Min-Sum intrinsèque associé au k-ème symbole x k sachant y k . 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 (1) GF =0, λ k (1) GF = α, λ k (1) GF = α 1 , λ 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 = L k (λ k ( i ) GF ) . Les valeurs de LLR λ k (i) L pour i = 1 à 4 vérifient la relation : λ k (1) L ≤ λ k (2) L ≤ λ k (3) L ≤ λ k (4) L . Avec le modèle de canal asymétrique considéré, la variable y k 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] où C i 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 . 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. Définition des messages correspondant à des arêtes du graphe de Tanner 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 h j,k , on note C2V(j,k) et V2C(j,k) les messages associés. Puisque d v = 2, seules 2 arêtes sont reliées à un nœud de variable VN k donné. On désigne C2V(j k (1),k) et C2V(j k (2),k) (respectivement V2C(j k (1),k) et V2C(j k (2),k)) les deux messages C2V (respectivement V2C) associés au VN k où j k (1) et j k (2) indiquent la position des deux valeurs non nulles de la colonne k de la matrice H. De même, on désigne C2V(j, k j (v)) (respectivement V2C(j, k j (v))) pour v= 1 à d c , les d c messages C2V (respectivement V2C) associés au CH j où k j (v) indiquent la position de la v-ème valeur non nulle de la ligne j de la matrice H. 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(l) L et les symboles GF associés V2C(l) GF , avec l= 1 à 4 . De même, le message C2N de sortie du CN contient les 4 valeurs LLR C2N(l) L (triées par ordre croissant) et les symboles GF C2N(l) GF qui leur sont associés. Traitement pour chaque VN 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. Etape 1 : le calcul de V2C(x) pour chaque x dans GF(4) [Math.11] Etape 2 : la détermination du minimum de la valeur de V2C) [Math.12] Etape 3 : normalisation [Math.13] Traitement pour chaque CN Un nœud de parité de degré d c peut être décomposé nœuds de contrôle élémentaires, par exemple en 3(d c – 2) nœuds de contrôle élémentaires. 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 & Iterative Information Processing, Brest, France, Septembre 2010. Décodage par un algorithme Min-Sum 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). 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 d v =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 d v =2 symboles distincts dans GF(4). Cette limitation dans le choix des valeurs réduit les besoins de stockage. 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. 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. Le processus de décodage itére n it 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 * dc 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é. 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. Etapes du d écodage par un algorithme Min-Sum Les étapes de l’algorithme Min-Sum peuvent être résumées comme suit. Dans une phase d’initialisation, le message intrinsèque est généré pour k= 1 à N: [Math.20] ce message intrinsèque correspondant aux 4 valeurs L k (x) calculées sur la base de la formule Math.1. Le message V2C est calculé pour k= 1 à N et v=1 à 2 : [Math.21] 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). A) calcul du message extrinsèque V2C associé au nœud de parité CN j pour v= 1 à d c : [Math.22] B) mise en œuvre du traitement associé au nœud de parité CN j pour v= 1 à d c de sorte à générer des nouveaux messages C2V [Math.25] C) pour chaque nœud de variable k j (v) connecté au nœud de parité CN j , on met à jour le deuxième message V2C en utilisant le nouveau message C2V et le message intrinsèque L k [Math.23] Puis les étapes A) à C) sont répétées à l’itération suivante. 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 L k . 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] 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 Decoder Based on the EMS Algorithm“ IEEE Transactions on Circuits and Systems I , vol.60, no.10, pp.2644-2656, Oct. 2013, doi: 10.1109/TCSI.2013.2279186 2013. D’autres exemples détaillés d’algorithmes Min-Sum sont décrits dans les références [29] et [28]. Procédé de décodage 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. 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é. 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. . 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. 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é. L’information de fiabilité pour une valeur de mesure y k 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. 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. 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. 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 codées dans un Corps de Galois d’ordre 4. 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. 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. Résultats 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. 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 nucleotide 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). Pour les valeurs expérimentales présentées dans la table de la Fig. 3, nous avons obtenu un SNER HD 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 10 6 séquences de nucléotides codés, c'est-à-dire 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) ne pouvait qu'améliorer le rendement. Ces simulations modélisent spécifiquement les erreurs de substitution et qu'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. 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. 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é. 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. Les fonctions et procédés décrits dans ce document peuvent ainsi être mises en œuvre 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). 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é. Ce logiciel / programme peut être codé au moyen de n’importe quel langage de programmation, et être sous la forme de code 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. 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. 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é. 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). 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. 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. Le support d'informations peut être n'importe 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. 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. 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. 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. Birney, “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 preservation 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., “Error 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. abs/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 Conference on Signals, Systems, and Computers, vol. abs/1801.04882, Oct. 2017. [17] C. R. O’Donnel, H. Wang, and W. B. Dunbar, “Error 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 deletions 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,dc)- 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 representation 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 series 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 preparation and specific 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 nucleotides 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 Intern. Conf. on Commun., ICC’2007. Glasgow, England, June 2007. [28] J. Zhao, F. Zarkeshvari, and A. H. Banihashemi, “On implementation 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 algorithms 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 Intern. 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. Dispositif de décodage comprenant des moyens matériels et/ou logiciels de mise en œuvre des étapes d’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, 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 (y 1 , y 2 , …y k ) 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) d’une valeur décodée pour chaque valeur de mesure considérée 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. Dispositif 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. Dispositif selon la revendication 1 ou 2 dans lequel l’algorithme de décodage souple avec code correcteur d’erreur est un turbo code ou un algorithme de décodage de code LDPC, Low-Density Parity-Check. Dispositif 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. Dispositif 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 données quaternaires codées dans un Corps de Galois d’ordre 4, chaque symbole Corps de Galois d’ordre 4 correspondant à un nucléotide. Dispositif selon la revendication 5 dans lequel 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. Dispositif selon l’une quelconque des revendications précédentes dans lequel l’information de fiabilité pour une valeur de mesure y k et un type de nucléotide i est calculée comme suit : [Math.8] 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. Système de stockage de données à base d’ADN, comprenant un séquenceur à nanopore et un dispositif de décodage selon l’une quelconque des revendications 1 à 7.