Les accidents. Pour certains, tout ce qui se passe n'est qu'un pur accident. Et quelqu'un prétend qu'il n'y a pas d'accident. Vous pouvez philosopher et argumenter sur ce sujet pendant de nombreuses heures, mais il y aura encore de nombreuses conclusions. En passant des pensées métaphysiques à des pensées plus réelles, vous pouvez voir que les nombres aléatoires ont trouvé leur application dans de nombreux aspects de notre vie: des machines à sous aux systèmes de codage d'informations. Le processus au cours duquel une séquence de nombres / symboles aléatoires est générée qui ne peut pas être prédite est appelé génération de nombres aléatoires (RNG). Au cours de la longue histoire de l'humanité, de nombreuses méthodes RNG ont été créées. Certains sont assez simples et directs: des dés, des pièces (face / queue), un jeu de cartes, etc.
D'autres utilisent des processus physiques beaucoup plus complexes: par exemple, en raison des mouvements à haute fréquence des électrons, la résistance électrique du fil n'est pas constante, c'est-à-dire varie au hasard. En mesurant ce bruit de fond, une séquence de nombres aléatoires peut être obtenue. Mais les techniques RNG ne se limitent pas à la seule physique. Un groupe de scientifiques de l'École technique supérieure suisse de Zurich (ou ETHZ en abrégé) a créé une nouvelle méthode de génération de nombres aléatoires basée sur la synthèse d'ADN. Comment exactement cela a-t-il été réalisé, à quel point les nombres sont-ils aléatoires et peuvent-ils être prédits? Les réponses à ces questions nous attendent dans le rapport des scientifiques. Aller.
Base de recherche
Quelle est l'une des principales limitations des dés en tant que générateur de nombres aléatoires? Le fait que ces chiffres ne seront pas tant (36 combinaisons de dés, si exagérés, c'est-à-dire sans probabilités et autres). Moins nous avons de variation, plus il est facile de prédire le résultat possible. Par conséquent, pour un codage plus complexe et, par conséquent, sûr basé sur RNG, il est nécessaire que les nombres générés soient plus grands et qu'ils soient eux-mêmes plus complexes. C'est une explication très simplifiée, mais elle véhicule néanmoins l'essence de la question.
Variantes de combinaisons de deux dés.
Par conséquent, l'utilisation de ces processus physiques qui ne peuvent être prédits avec précision est devenue la base de nombreuses méthodes RNG modernes. Cependant, il convient de rappeler qu'il existe deux directions principales du RNG: la génération de nombres aléatoires (vraiment aléatoires) et pseudo-aléatoires. Dans le premier cas, une source non déterministe (chaotique) est utilisée pour générer des nombres aléatoires. Le second crée une séquence déterministe de nombres qui dépend de l'entrée (graine). Si la graine d'entrée est connue, la séquence entière de nombres aléatoires peut être reproduite. À première vue, le pseudo-RNG semble moins efficace, cependant, cette méthode a de meilleures propriétés statistiques et peut souvent générer des nombres aléatoires beaucoup plus rapidement que le RNG.
Il est tout à fait évident que non seulement les processus physiques ou les algorithmes logiciels, mais aussi les réactions chimiques conviennent pour générer des nombres vraiment aléatoires. D'une part, les réactions chimiques sont des processus statistiques dans lesquels la formation de produits chimiques suit une certaine distribution de probabilité en fonction de l'énergie d'activation de la réaction. Mais d'un autre côté, la capacité à identifier des molécules individuelles après synthèse est pratiquement nulle, malgré la capacité de prédire statistiquement le résultat de la réaction.
Des recherches ont déjà été menées sur l'utilisation de la chimie pour générer des nombres aléatoires. Par exemple, dans ce travailun dispositif est décrit qui fournit un pool impressionnant d'entropie de macrostats détectables de cristaux en croissance au cours de réactions chimiques. Le problème est que l'incapacité d'identifier les molécules individuelles entraîne une perte de caractère aléatoire lors de l'analyse des processus chimiques stochastiques. En d'autres termes, il semble que les réactions chimiques ne conviennent pas aux GNR. Cependant, comme le déclarent les auteurs des travaux que nous examinons aujourd'hui, la situation de la synthèse d'ADN est complètement différente.
La production d'ADN synthétique est un processus chimique stochastique avec un avantage important: les molécules individuelles de la séquence d'ADN synthétisée peuvent être facilement identifiées et analysées à l'aide de technologies de séquençage modernes (NGS de séquençage de nouvelle génération). Le séquençage lui-même existe depuis les années 1970, mais les techniques actuelles vous permettent de lire des molécules individuelles et donc d'utiliser l'ADN comme source pour générer des nombres aléatoires.
Résultats de recherche
Il convient de noter qu'en biologie, les méthodes d'identification des schémas globaux d'un composant microbien nécessitent la synthèse de nucléotides aléatoires à certaines positions d'amorces afin d'évaluer les régions hypervariables (par exemple, pour le gène de l'ARNr 16S) pour la classification taxonomique. D'autres utilisations de la synthèse de nucléotides aléatoires peuvent être trouvées dans le code à barres, où à l'aide d'identificateurs moléculaires uniques (UMI d' identificateurs moléculaires uniques ) peuvent être éliminés par l'amplification par déplacement PCR * .
Réaction en chaîne par polymérase (PCR) * - une méthode qui vous permet d'obtenir une augmentation significative des petites concentrations de certains fragments d'acide nucléique (ADN) dans le matériel biologique.Les scientifiques notent que ces nucléotides aléatoires sont marqués de la lettre N (selon les normes NC-IUB, c'est-à-dire le comité de nomenclature de la communauté internationale sur la biochimie). Par conséquent, les scientifiques ont profité de l'occasion pour synthétiser un nucléotide aléatoire pour chaque position indiquée par la lettre N dans la conception de l'ADN utilisé.
Image # 1 Les
brins d'ADN utilisés dans l'étude ont été conçus de telle manière qu'une région aléatoire de 64 nucléotides s'écoule d'une région prédéterminée de l' amorce avant * à une extrémité et d'une région prédéterminée de l'amorce inverse à l'autre extrémité (Fig.1).
Primer * est un court fragment d'acide nucléique.La longueur totale du brin d'ADN modifié était de 105 nucléotides, y compris deux régions d'amorce et une région aléatoire.
Image # 2 Le
brin d'ADN conçu a ensuite été mis en œuvre physiquement en utilisant des technologies modernes de synthèse à l'état solide (image # 2).
Le mélange des éléments constitutifs des nucléotides d'ADN a également trouvé des applications dans le domaine du stockage de l'ADN. Des études antérieures ont montré que l'élargissement de l'alphabet * ADN en déterminant d'abord le rapport de mélange des quatre nucléotides d'ADN à des positions spécifiques dans la séquence d'ADN peut augmenter la densité de stockage logique en utilisant des lettres composées pour la synthèse de l'ADN.
* — : A ( ), T (), G () C ().Les séquences d'ADN aléatoires ont été synthétisées trois fois: deux fois par Microsynth et une fois par Eurofins Genomics . La première entreprise s'est vu confier la tâche supplémentaire de mélanger les éléments constitutifs avant la fusion (synthèse 1). La deuxième société a réalisé la synthèse sans aucune intervention supplémentaire dans le processus (synthèse 2).
En conséquence, la synthèse 1 a donné 204 ug d'ADN séché synthétisé dans la direction 3 'vers 5'. Pour déterminer le caractère aléatoire, un pool d'ADN a été séquencé puis filtré numériquement.
Si vous regardez la composition des brins d'ADN en fonction de la position dans une région aléatoire (image n ° 3), vous pouvez voir deux tendances générales:
- : G , A C;
- : A C 60 , G 5' 3', T 5' 3'. Microsynth ( ), Eurofins ( ).
Image # 3 Les
tendances observées fournissent une première indication de la fiabilité des données et peuvent en partie s'expliquer par les processus chimiques qui se produisent lors de la synthèse de l'ADN. L'écart entre le pourcentage de nucléotides G, T et A, C (inéquivalence nucléotidique) peut être causé par plusieurs facteurs. Selon Microsynth, les volumes des blocs de construction individuels pendant la synthèse ne sont pas contrôlés au microlitre le plus proche.
Par conséquent, des différences de concentration peuvent conduire à une distribution moins uniforme des nucléotides le long de la chaîne. De plus, l'efficacité de la liaison diffère pour chaque bloc de construction et dépend de variables telles que la période d'utilisation des réactifs pour la synthèse par les fabricants ou les groupes protecteurs attachés à chaque bloc de construction. Le résultat de l'efficacité de liaison différente est très probablement associé à la distribution inégale des quatre nucléotides.
Une diminution de G et une augmentation de T de 5 'à 3' (non-équivalence de positions) peuvent être le résultat d'une procédure chimique que le brin d'ADN subit pendant la synthèse. Lorsque la synthèse d'ADN se déroule dans la direction 3 '- 5', les nucléotides en position 60 (image n ° 3) sont d'abord ajoutés au brin d'ADN. Etant donné que les fragments d'ADN synthétisés restent dans la chambre de synthèse jusqu'à ce que la longueur souhaitée du brin d'ADN soit obtenue, les nucléotides ajoutés au brin d'ADN au début de la synthèse restent dans l'environnement de synthèse le plus long. Ainsi, ces nucléotides sont passés par la plupart des étapes de synthèse et, par conséquent, la plupart des étapes d'oxydation.
Cette caractéristique de la performance de la synthèse chimique d'ADN peut être une explication de la tendance n ° 2 (non-équivalence des positions), lorsque la composition de G diminue le long de la chaîne dans la direction 5 '- 3', et la composition de T augmente dans la direction 5 '- 3'.
L'oxydation peut conduire à un phénomène appelé transversion G-T ( 3e ), dans lequel la base G est chimiquement modifiée de telle manière qu'elle peut être remplacée par une base T pendant les étapes de réplication de l'ADN.
Outre les tendances décrites ci-dessus, les différences dans les courbes dans les graphiques peuvent être associées à des différences dans une stratégie de synthèse (avec et sans mélange de blocs de construction).
Il existe deux principales sources potentielles de biais qui peuvent affecter les résultats: le biais de couverture (lorsque certains des éléments étudiés sont en dehors du retour sur investissement) et le biais dû à des erreurs.
La première option est principalement exprimée par une erreur, qui peut être associée à la disposition spatiale sur la puce de synthèse et à la stochasticité de la PCR. La deuxième option est le résultat d'insertions, de délétions (réarrangements chromosomiques, lorsqu'une partie du chromosome est perdue) ou de substitutions de nucléotides erronés lors des étapes de synthèse, de PCR et de séquençage.
Dans cette étude particulière, le biais de couverture affecte la distribution des nucléotides uniquement s'il existe un écart significatif entre la couverture de chaque séquence aléatoire. Cependant, l'analyse des données a montré que cette variante de l'erreur ne peut pas être la cause de l'absence d'équivalence de nucléotides observée et d'absence d'équivalence de position.
En ce qui concerne le biais dû aux erreurs, il est extrêmement difficile de faire la distinction entre les erreurs de synthèse et de séquençage, car les deux processus ne peuvent pas être complètement séparés, car l'accès à la morphologie moléculaire de l'ADN n'est possible que par séquençage de l'ADN. Cependant, des études ont montré qu'avec un traitement approprié des données, des erreurs de séquençage se produisent à des endroits aléatoires.
Lors de la synthèse d'ADN, la croissance des brins peut être interrompue jusqu'à ce que la longueur désirée soit atteinte et ainsi provoquer une erreur dans le pool. Mais le processus de séquençage n'a pas montré d'effet significatif sur le résultat ( 3a - 3c ). Par conséquent, le biais dû aux erreurs est causé uniquement par le processus de synthèse de l'ADN, et non par le séquençage.
En normalisant la synthèse 1 ( 3a ), une carte thermique a été obtenue illustrant la prédominance de la liaison de deux nucléotides ( 3d ). Cela vous permet également de voir la troisième erreur: la prédominance de la liaison nucléotidique.
La liaison d'une seule base à un nucléotide existant dépend en partie de la nature du nucléotide existant: G est moins susceptible de se lier à A s'il a la capacité de se lier librement à A, T, C ou G; de plus, G est plus susceptible de se lier à G s'il peut se lier librement à A, T, C ou G.
Du point de vue de la synthèse, cette imprécision peut être corrigée tout simplement. Par exemple, vous pouvez ajouter plus de blocs T au lieu de G (modifiant ainsi le rapport cible des nucléotides A, G, T et C), ce qui augmentera le décalage de la transversion.
Cependant, en raison de la complexité de ce processus, les scientifiques ont décidé de ne pas effectuer de modifications «physiques» dans le cadre de l'étude, mais d'utiliser un algorithme de post-traitement informatique pour supprimer le biais créé lors de la synthèse d'ADN, augmentant ainsi la fiabilité et la reproductibilité de l'ensemble de la procédure.
Au stade du traitement des données (c'est-à-dire au stade de la préparation du RNG), le pool obtenu à partir de la synthèse 1 (Microsynth) a été utilisé. Bien que cette variante présente le déplacement le plus important résultant de la transversion, les courbes lisses montrent le mélange et la jonction les plus uniformes lors des étapes de synthèse.
La lecture aléatoire à partir de brins d'ADN synthétisés nécessite la lecture de brins individuels, ce qui a été fait en utilisant le séquençage (dans ce cas, le système iSeq100 a été utilisé). Après le séquençage, les données de sortie (fichier numérique) ont été traitées de manière à sélectionner les séquences correctes (c'est-à-dire sans erreur) dans le pool.
Les erreurs qui peuvent s'être produites incluent des erreurs de suppression, d'insertion et de substitution. Ils peuvent rendre le brin d'ADN trop court, trop long ou contenir une base endommagée. Pour minimiser l'impact des erreurs (en particulier les erreurs dues à la suppression) sur le caractère aléatoire, toutes les séquences ont été réduites à 60 nucléotides. Parmi les chaînes obtenues, seules celles qui contenaient la longueur correcte de nucléotides aléatoires ont été sélectionnées.
Une fois que le pool d'ADN traité par ordinateur a été limité (seules les séquences de 60 nucléotides de longueur), les nucléotides d'ADN ont été mappés en bits en utilisant le schéma suivant: A → 0, C → 0, T → 1, G → 1. En conséquence, le brin d'ADN numérisé a été converti en binaire.
Les chaînes de bits (flux binaires) obtenues après appariement ont ensuite été vérifiées pour le caractère aléatoire en utilisant la suite de tests statistiques du NIST. Les scientifiques affirment que leur méthode d'évaluation des chances était extrêmement difficile: la séquence n'était considérée comme suffisamment aléatoire que lorsque tous les tests étaient passés avec succès séparément (si au moins un test échouait, la séquence était exclue).
L'évaluation des flux binaires initiaux à l'aide de la suite de tests statistiques NIST a montré que tous les tests n'ont pas réussi. Cela signifie que les flux binaires résultants n'ont pas les mêmes propriétés statistiques qu'une séquence complètement aléatoire, c'est-à-dire ils contiennent encore une certaine redondance et un biais. Par conséquent, un traitement de bits supplémentaire était nécessaire pour supprimer le déplacement qui s'était produit au stade de la synthèse de l'ADN.
Afin de résoudre le problème du décalage des bits de sortie (lorsque certains nombres sont plus importants que d'autres), les scientifiques ont décidé d'utiliser l'algorithme de von Neumann. L'algorithme considère les bits en séquence par paires, puis effectue l'une des trois actions suivantes: si deux bits consécutifs sont égaux, ils sont supprimés (ignorés); la séquence "1, 0" est convertie en un; la séquence "0, 1" est convertie en zéro.
Dans le cadre de cette étude, on s'attendait à ce que l'algorithme de von Neumann fonctionne comme suit:
- si l'entrée est "0, 1" ou "1, 0", le premier chiffre devient la sortie et le second chiffre est rejeté;
- si l'entrée est "0, 0" ou "1, 1", il n'y a pas de sortie, donc les deux chiffres d'entrée sont ignorés.
L'un des plus gros inconvénients de cette méthode est la grande perte de données: environ 75% des données d'entrée sont rejetées en raison de son fonctionnement. Par conséquent, l'entrée doit être suffisamment importante pour compenser les pertes supplémentaires.
Image # 4
L'effet du nivellement de l'offset (diagramme ci-dessus) est clairement visible lors de l'analyse de la différence entre les trains binaires bruts (contenant l'offset) et les trains binaires traités (pas d'offset).
La somme cumulative de chaque flux binaire brut (chacun 60 nucléotides de longueur) et chaque flux binaire traité (chacun moins de 60 nucléotides de longueur) a été calculée en mettant chaque 0 à "-1" et chaque 1 à "1". En outre, tous les flux de bits sans décalage ont été combinés en un bloc de bits.
Les scientifiques notent que bien que la perte de données soit significative (plus de 75% de tous les bits sont perdus) et que l'efficacité de calcul est assez faible (le débit de sortie de données moyen est quatre fois plus lent que le débit d'entrée de données moyen), l'élimination du biais a été parfaitement effectuée (en sortie, le biais est complètement absent).
Le bitblock obtenu après traitement avec l'algorithme de von Neumann a été réévalué via le système NIST.
Tableau 1: Résultats des tests statistiques NIST.
Tous les flux binaires traités ont réussi les tests statistiques NIST avec un score de passage> 54/56 pour chaque test, ce qui dépasse le minimum statistiquement requis (52/56). Une évaluation plus poussée du train binaire a montré que la valeur P ≥ 0,001. Il s'ensuit que la séquence est aléatoire avec un niveau de confiance de 99,9%.
Image # 5
Le diagramme ci-dessus est un processus complet pour générer des nombres aléatoires en utilisant la synthèse d'ADN. Comme on s'en souvient, à la suite de la synthèse, 204 μg d'ADN ont été obtenus, ce qui correspond à environ 4x10 15 brins d'ADN. Le processus de synthèse de cette quantité d'ADN prend environ 8,75 heures et le coût de production est d'environ 100 $.
L'échantillon d'ADN sec contient une entropie théorique de 28 PB (s'il n'y a pas de biais dans les données) et 7 PB de caractère aléatoire lorsque le décalage est supprimé à l'aide de l'algorithme de von Neumann (c'est-à-dire après 75% de perte de bits). Par conséquent, contrairement au stockage de données à l'aide de l'ADN, la synthèse elle-même n'est pas un goulot d'étranglement (un facteur limitant les performances) dans la génération de nombres aléatoires, car elle peut générer du hasard à un taux de 225 gigaoctets par seconde à un coût de 0,000014 USD / Go.
Cependant, le séquençage, au contraire, est un goulot d'étranglement en termes de temps et de coût de traitement. Le système iSeq utilisé dans ce travail a des options plus productives (par exemple, le NovaSeq 6000), capables d'effectuer jusqu'à 20 milliards de lectures de séquence en 36 heures. Les coûts financiers sont assez impressionnants (22 000 $). Par conséquent, en tenant compte de toutes les étapes du RNG, le résultat peut être obtenu à une vitesse de 300 kilo-octets par seconde au prix de 600 $ par Go. Il est possible de réduire les coûts en combinant plusieurs cycles de synthèse et de séquençage.
Pour une connaissance plus détaillée des nuances de l'étude, je vous recommande de consulter le rapport des scientifiques et des éléments supplémentaires .
Épilogue
Les générateurs de nombres aléatoires existent depuis des milliers d'années (les dés les plus anciens trouvés en Iran ont environ 5200 ans), même si les gens de cette époque ne connaissaient pas leur plein potentiel. La technologie moderne et les progrès scientifiques leur ont permis de créer des algorithmes et des dispositifs complexes capables de générer un caractère aléatoire qu'une personne ne serait pas capable de prédire. Cependant, là où la personne prend du retard, la technologie rattrape son retard. En d'autres termes, là où il y a un chiffrement, il y a aussi un décrypteur. Par conséquent, l'amélioration progressive des méthodes de codage d'informations, où des générateurs de nombres aléatoires sont utilisés, entraîne une amélioration parallèle des méthodes de piratage de tels systèmes. Cette course sans fin de serrures et de crochets de serrure oblige les deux parties à constamment proposer de nouvelles méthodes.
De nombreux RNG modernes sont basés sur des processus physiques et des algorithmes. Mais les réactions chimiques ont été en marge pendant de nombreuses années, car on pensait qu'elles ne pouvaient pas être une base fiable pour un GNR. Dans ce travail, les scientifiques ont montré que la synthèse d'ADN, étant un processus chimique, peut être non seulement une option valable pour la base d'un RNG, mais aussi surpasser ses concurrents «physiques» à bien des égards.
Naturellement, cette méthode reste un diamant brut qui nécessite un broyage sous forme de recherche supplémentaire, dont le but sera d'augmenter la productivité et de réduire les coûts. Néanmoins, la génération de nombres aléatoires au moyen de l'ADN est actuellement une direction extrêmement prometteuse.
Merci pour votre attention, restez curieux et passez une bonne semaine de travail, les gars.
Un peu de publicité
Merci de rester avec nous. Aimez-vous nos articles? Vous voulez voir du contenu plus intéressant? Soutenez-nous en passant une commande ou en recommandant à des amis, Cloud VPS pour les développeurs à partir de 4,99 $ , un analogue unique des serveurs d'entrée de gamme que nous avons inventé pour vous: The Whole Truth About VPS (KVM) E5-2697 v3 (6 Cores) 10GB DDR4 480GB SSD 1Gbps à partir de 19 $ ou comment diviser correctement le serveur? (options disponibles avec RAID1 et RAID10, jusqu'à 24 cœurs et jusqu'à 40 Go de DDR4).
Le Dell R730xd 2x est-il moins cher dans le centre de données Equinix Tier IV à Amsterdam? Seulement, nous avons 2 x Intel TetraDeca-Core Xeon 2x E5-2697v3 2,6 GHz 14C 64 Go DDR4 4x960 Go SSD 1 Gbps 100 TV à partir de 199 $ aux Pays-Bas!Dell R420 - 2 x E5-2430 2,2 GHz 6C 128 Go DDR3 2 x 960 Go SSD 1 Gbps 100 To - À partir de 99 $! Lisez à propos de Comment construire l'infrastructure de bldg. classe avec les serveurs Dell R730xd E5-2650 v4 coûtant 9000 euros pour un sou?