Gerando números aleatórios usando DNA





Acidentes. Para alguns, tudo o que acontece ao redor é um simples acidente. E alguém afirma que não há acidentes. Você pode filosofar e argumentar sobre esse assunto por muitas horas, mas ainda haverá muitas conclusões. Movendo-se de pensamentos metafísicos para pensamentos mais reais, você pode ver que os números aleatórios encontraram sua aplicação em muitos aspectos de nossa vida: de máquinas caça-níqueis a sistemas de codificação de informação. O processo durante o qual é gerada uma sequência de números / símbolos aleatórios que não podem ser previstos é chamado de geração de número aleatório (RNG). Ao longo da longa história da humanidade, muitos métodos RNG foram criados. Alguns são bastante simples e diretos: dados, moedas (cara / coroa), um baralho de cartas, etc.



Outros usam processos físicos muito mais complexos: por exemplo, devido aos movimentos de alta frequência dos elétrons, a resistência elétrica do fio não é constante, ou seja, varia aleatoriamente. Medindo esse ruído de fundo, uma sequência de números aleatórios pode ser obtida. Mas as técnicas de RNG não se limitam apenas à física. Um grupo de cientistas da Escola Técnica Superior Suíça de Zurique (ou ETHZ para abreviar) criou um novo método para gerar números aleatórios com base na síntese de DNA. Como exatamente isso foi alcançado, quão aleatórios são os números obtidos e eles podem ser previstos? As respostas a essas perguntas nos aguardam no relatório dos cientistas. Vai.



Base de pesquisa



Qual é uma das principais limitações dos dados como um gerador de números aleatórios? O fato de que esses números não serão tanto (36 combinações de dados, se exagerados, ou seja, sem probabilidades e outras coisas). Quanto menos variação tivermos, mais fácil será prever o resultado possível. Consequentemente, para uma codificação mais complexa e, conseqüentemente, segura baseada em RNG, é necessário que os números gerados sejam maiores e eles próprios sejam mais complexos. Esta é uma explicação muito simplificada, porém transmite a essência do assunto.





Variantes de combinações de dois dados.



Portanto, o uso de processos físicos que não podem ser previstos com precisão tornou-se a base de muitos métodos modernos de RNG. No entanto, é importante lembrar que existem duas áreas principais do RNG - a geração de números aleatórios (verdadeiramente aleatórios) e pseudo-aleatórios. No primeiro caso, uma fonte não determinística (caótica) é usada para gerar números aleatórios. O segundo cria uma sequência determinística de números que depende da entrada (semente). Se a semente de entrada for conhecida, toda a sequência de números aleatórios pode ser reproduzida. À primeira vista, o pseudo-RNG parece ser menos eficiente, mas esse método tem melhores propriedades estatísticas e pode frequentemente gerar números aleatórios muito mais rápido do que o RNG.



É bastante óbvio que não apenas os processos físicos ou algoritmos de software, mas também as reações químicas são adequadas para gerar números verdadeiramente aleatórios. Por outro lado, as reações químicas são processos estatísticos nos quais a formação de produtos químicos segue uma certa distribuição de probabilidade dependendo da energia de ativação da reação. Mas, por outro lado, a capacidade de identificar moléculas individuais após a síntese é praticamente nula, apesar da capacidade de prever estatisticamente o resultado da reação.



Já foram feitas pesquisas sobre o uso da química para gerar números aleatórios. Por exemplo, neste trabalhoé descrito um dispositivo que fornece um impressionante pool de entropia de macroestados detectáveis ​​de cristais em crescimento no curso de reações químicas. O problema é que a incapacidade de identificar moléculas individuais leva à perda de aleatoriedade ao analisar processos químicos estocásticos. Em outras palavras, parece que as reações químicas não são adequadas para RNGs. No entanto, como declaram os autores do trabalho que estamos considerando hoje, a situação com a síntese de DNA é completamente diferente.



A produção de DNA sintético é um processo químico estocástico com uma vantagem importante: moléculas individuais na sequência de DNA sintetizada podem ser facilmente identificadas e analisadas usando tecnologias de sequenciamento modernas (NGS de sequenciamento de última geração) O próprio sequenciamento existe desde os anos 1970, mas as técnicas atuais permitem que você leia moléculas individuais e, assim, use o DNA como fonte para gerar números aleatórios.



Resultados da pesquisa



Deve-se notar que em biologia, os métodos para identificar os esquemas globais de um componente microbiano requerem a síntese de nucleotídeos aleatórios em certas posições do iniciador, a fim de avaliar regiões hipervariáveis ​​(por exemplo, para o gene 16S rRNA) para classificação taxonômica. Outros usos da síntese de nucleotídeos aleatórios podem ser encontrados no código de barras, onde com a ajuda de identificadores moleculares únicos (UMI de identificadores moleculares únicos ) podem ser eliminados PCR por amplificação por deslocamento * .
A reação em cadeia da polimerase (PCR) * é um método que permite um aumento significativo em pequenas concentrações de certos fragmentos de ácido nucléico (DNA) em material biológico.
Os cientistas observam que esses nucleotídeos aleatórios são marcados com a letra N (de acordo com os padrões NC-IUB, ou seja, o comitê de nomenclatura da comunidade internacional de bioquímica). Consequentemente, os cientistas aproveitaram a oportunidade para sintetizar um nucleotídeo aleatório para cada posição indicada pela letra N no desenho do DNA usado.





Imagem # 1 As



fitas de DNA usadas no estudo foram projetadas de tal forma que uma região aleatória de 64 nucleotídeos flui de uma região predeterminada do primer direto * em uma extremidade e uma região predeterminada do primer reverso na outra extremidade (Fig. 1).
Primer * é um pequeno fragmento de um ácido nucléico.
O comprimento total da fita de DNA projetada foi de 105 nucleotídeos, incluindo duas regiões de primer e uma região aleatória.





Imagem # 2 A



fita de DNA projetada foi posteriormente implementada fisicamente usando tecnologias modernas de síntese de estado sólido (imagem # 2).



A mistura dos blocos de construção dos nucleotídeos do DNA também encontrou aplicações no campo do armazenamento de DNA. Estudos anteriores demonstraram que expandir o * alfabeto do DNA determinando primeiro a proporção de mistura de todos os quatro nucleotídeos do DNA em posições específicas na sequência do DNA pode aumentar a densidade de armazenamento lógico usando letras compostas para a síntese do DNA.
* — : A ( ), T (), G () C ().
As sequências aleatórias de DNA foram sintetizadas três vezes: duas vezes por Microsynth e uma vez por Eurofins Genomics . A primeira empresa recebeu a tarefa adicional de misturar blocos de construção antes da fusão (síntese 1). A segunda empresa produziu a síntese sem qualquer intervenção adicional no processo (síntese 2).



Como resultado, a síntese 1 deu 204 μg de DNA seco sintetizado na direção 3 'para 5'. Para determinar a aleatoriedade, um pool de DNA foi sequenciado e posteriormente filtrado digitalmente.



Se você olhar para a composição das fitas de DNA como uma função da posição em uma região aleatória (imagem nº 3), você pode ver duas tendências gerais:



  • : G , A C;
  • : A C 60 , G 5' 3', T 5' 3'. Microsynth ( ), Eurofins ( ).




Imagem # 3 As



tendências observadas fornecem uma primeira indicação da confiabilidade dos dados e podem ser parcialmente explicadas pelos processos químicos que ocorrem durante a síntese de DNA. A discrepância entre a porcentagem de nucleotídeos G, T e A, C (desigualdade de nucleotídeos) pode ser causada por vários fatores. De acordo com a Microsynth, os volumes dos blocos de construção individuais durante a síntese não são controlados ao microlitro mais próximo.



Consequentemente, as diferenças na concentração podem levar a uma distribuição menos uniforme dos nucleotídeos ao longo da cadeia. Além disso, a eficiência da ligação difere para cada bloco de construção e depende de variáveis ​​como o período de uso dos reagentes para síntese pelos fabricantes ou os grupos de proteção anexados a cada bloco de construção. O resultado da eficiência de ligação diferente está provavelmente associado à distribuição desigual dos quatro nucleotídeos.



Uma diminuição em G e um aumento em T de 5 'para 3' (não equivalência de posições) pode ser o resultado de um procedimento químico que a fita de DNA sofre durante a síntese. Conforme a síntese de DNA prossegue na direção 3 '- 5', os nucleotídeos na posição 60 (imagem # 3) são adicionados primeiro à fita de DNA. Uma vez que os fragmentos de DNA sintetizados permanecem na câmara de síntese até que o comprimento desejado da fita de DNA seja obtido, os nucleotídeos adicionados à fita de DNA no início da síntese permanecem no ambiente de síntese por mais tempo. Assim, esses nucleotídeos passaram pela maioria das etapas de síntese e, portanto, pela maioria das etapas de oxidação.



Esta característica de desempenho da síntese química de DNA pode ser uma explicação para a tendência # 2 (não equivalência de posição), quando a composição G diminui ao longo da cadeia na direção 5 '- 3' e a composição T aumenta na direção 5 '- 3'.



A oxidação pode levar a um fenômeno denominado transversão G - T ( 3e ), em que a base G é quimicamente alterada de tal forma que pode ser substituída por uma base T durante as etapas de replicação do DNA.



Além das tendências descritas acima, as diferenças nas curvas nos gráficos podem estar associadas a diferenças em uma estratégia de síntese (com e sem mistura de blocos de construção).



Existem duas fontes principais de enviesamento que podem afetar os resultados: enviesamento de cobertura (quando alguns dos itens sob investigação estão fora do ROI) e enviesamento devido a erros.



A primeira opção é expressa principalmente por um erro, que pode estar associado ao arranjo espacial no chip de síntese e à estocasticidade da PCR. A segunda opção é o resultado de inserções, deleções (rearranjos cromossômicos, quando uma porção do cromossomo é perdida) ou substituições de nucleotídeos errôneos durante as etapas de síntese, PCR e sequenciamento.



Neste estudo específico, o viés de cobertura afeta a distribuição de nucleotídeos apenas se houver uma discrepância significativa entre a cobertura de cada sequência aleatória. No entanto, a análise dos dados mostrou que essa variante do erro não pode ser a causa da não-equivalência de nucleotídeos observada e da não-equivalência de posição.



No que diz respeito ao viés por erros, é extremamente difícil distinguir entre erros de síntese e de sequenciamento, uma vez que os dois processos não podem ser completamente separados, uma vez que o acesso à morfologia molecular do DNA só é possível por meio do sequenciamento do DNA. No entanto, estudos têm mostrado que, com o processamento adequado dos dados, os erros de sequenciamento ocorrem em locais aleatórios.



Durante a síntese de DNA, o crescimento das fitas pode ser interrompido até que o comprimento desejado seja alcançado e, assim, causar um erro no pool. Porém, o processo de sequenciamento não mostrou efeito significativo no resultado ( 3a - 3c ). Portanto, o viés devido a erros é causado unicamente pelo processo de síntese do DNA, e não pelo sequenciamento.



Normalizando a síntese 1 ( 3a ), um mapa de calor foi obtido ilustrando a predominância de ligação de dois nucleotídeos ( 3d ). Ele também permite que você veja o terceiro erro: a predominância da ligação de nucleotídeos.



A ligação de uma única base a um nucleotídeo existente depende em parte da natureza do nucleotídeo existente: G é menos provável de se ligar a A se for livre para se ligar a A, T, C ou G; nesse caso, G se liga com mais frequência a G se puder se ligar livremente a A, T, C ou G.



Do ponto de vista da síntese, essa imprecisão pode ser corrigida de maneira bastante simples. Por exemplo, você pode adicionar mais blocos T em vez de G (alterando assim a proporção do alvo dos nucleotídeos A, G, T e C), o que aumentará o deslocamento da transversão.



No entanto, devido à complexidade desse processo, os cientistas decidiram não realizar edições "físicas" como parte do estudo, mas usar um algoritmo de pós-processamento computacional para remover o viés criado durante a síntese de DNA, aumentando a confiabilidade e reprodutibilidade de todo o procedimento.



No estágio de processamento de dados (ou seja, no estágio de preparação para o RNG), foi utilizado o pool obtido da síntese 1 (Microsynth). Embora esta variante mostre o deslocamento mais forte resultante da transversão, as curvas suaves mostram a mistura e conexão mais homogênea durante as etapas de síntese.



A leitura da aleatoriedade de fitas de DNA sintetizadas requer a leitura de fitas individuais, o que foi feito por meio de sequenciamento (neste caso, foi utilizado o sistema iSeq100). Após o sequenciamento, os dados de saída (arquivo digital) foram processados ​​de modo a selecionar as sequências corretas (ou seja, sem erros) do conjunto.



Os erros que podem ter ocorrido incluem erros de exclusão, inserção e substituição. Eles podem fazer com que a fita de DNA seja muito curta, muito longa ou contenha uma base danificada. Para minimizar o efeito dos erros (especialmente erros devido à deleção) na aleatoriedade, todas as sequências foram reduzidas para 60 nucleotídeos. Das cadeias obtidas, foram selecionadas apenas aquelas que continham o comprimento correto de nucleotídeos aleatórios.



Depois que o pool de DNA processado por computador foi limitado (apenas sequências de 60 nucleotídeos de comprimento), os nucleotídeos de DNA foram mapeados em bits usando o seguinte esquema: A → 0, C → 0, T → 1, G → 1. Como resultado, a fita de DNA digitalizada foi convertido para binário.



As bitstrings (bitstrings) obtidas após a correspondência foram subsequentemente verificadas quanto à aleatoriedade usando o conjunto de testes estatísticos do NIST. Os cientistas afirmam que seu método de avaliação de chances era extremamente difícil: a sequência foi considerada suficientemente aleatória apenas quando todos os testes foram aprovados separadamente (se pelo menos um teste falhou, a sequência foi excluída).



A avaliação dos fluxos de bits iniciais usando o conjunto de testes estatísticos NIST indicou que nem todos os testes foram aprovados com êxito. Isso significa que os fluxos de bits resultantes não têm as mesmas propriedades estatísticas de uma sequência completamente aleatória, ou seja, eles ainda contêm alguma redundância e preconceito. Portanto, um processamento adicional de bits era necessário para remover o deslocamento que havia surgido no estágio de síntese de DNA.



Para resolver o problema de deslocamento dos bits de saída (quando alguns números são maiores que outros), os cientistas decidiram usar o algoritmo de von Neumann. O algoritmo considera os bits em sequência em pares e, a seguir, executa uma das três ações: se dois bits consecutivos forem iguais, eles são removidos (ignorados); a sequência "1, 0" é convertida em um; a sequência "0, 1" é convertida para zero.



No contexto deste estudo, esperava-se que o algoritmo de von Neumann funcionasse da seguinte forma:



  • se a entrada for "0, 1" ou "1, 0", o primeiro dígito se torna a saída e o segundo dígito é descartado;
  • se a entrada for "0, 0" ou "1, 1", não há saída, então ambos os dígitos de entrada são descartados.


Uma das maiores desvantagens desse método é a grande perda de dados: cerca de 75% dos dados de entrada são descartados devido ao seu funcionamento. Portanto, a entrada deve ser grande o suficiente para compensar perdas futuras.





Imagem nº 4



O efeito do nivelamento de deslocamento (diagrama acima) é claramente visível ao analisar a diferença entre os fluxos de bits brutos (contendo deslocamento) e fluxos de bits processados ​​(sem deslocamento).



A soma cumulativa de cada bitstream bruto (cada 60 nucleotídeos de comprimento) e cada bitstream processado (cada um com menos de 60 nucleotídeos de comprimento) foi calculada definindo cada 0 como "-1" e cada 1 como "1". Além disso, todos os fluxos de bits sem deslocamento foram combinados em um bloco de bits.



Os cientistas observam que embora a perda de dados seja significativa (mais de 75% de todos os bits são perdidos) e a eficiência computacional seja bastante baixa (a taxa média de saída de dados é quatro vezes mais lenta do que a taxa média de entrada de dados), a eliminação do viés foi realizada perfeitamente (na saída, o viés é completamente ausente).



O bitblock obtido após o processamento com o algoritmo de von Neumann foi reavaliado através do sistema NIST.





Tabela 1: Resultados do teste estatístico NIST.



Todos os fluxos de bits processados ​​passaram nos testes estatísticos NIST com uma pontuação de aprovação de> 54/56 para cada teste, o que excede o mínimo exigido estatisticamente (52/56). Uma avaliação posterior do fluxo de bits mostrou que o valor P ≥ 0,001. Conclui-se que a sequência é aleatória com um nível de confiança de 99,9%.





Imagem # 5



O diagrama acima é um processo completo para gerar números aleatórios usando a síntese de DNA. Como lembramos, como resultado da síntese, foram obtidos 204 μg de DNA, o que corresponde a aproximadamente 4x10 15 fitas de DNA. O processo de síntese dessa quantidade de DNA leva cerca de 8,75 horas e o custo de produção é de cerca de US $ 100.



A amostra de DNA seco contém uma entropia teórica de 28 PB (se não houver polarização nos dados) e 7 PB de aleatoriedade quando o deslocamento for removido usando o algoritmo de von Neumann (ou seja, após 75% de perda de bits). Portanto, ao contrário do armazenamento de dados usando DNA, a síntese em si não é um gargalo (um fator de limitação de desempenho) na geração de números aleatórios, pois pode gerar aleatoriedade a uma taxa de 225 gigabytes por segundo a um custo de $ 0,000014 / GB.



No entanto, o sequenciamento, ao contrário, é um gargalo em termos de tempo e custo de processamento. O sistema iSeq utilizado neste trabalho possui opções mais eficientes (por exemplo, o NovaSeq 6000), capaz de realizar até 20 bilhões de leituras de sequência em 36 horas. Os custos financeiros são bastante impressionantes ($ 22.000). Portanto, levando em consideração todas as etapas do RNG, o resultado pode ser obtido a uma velocidade de 300 kilobytes por segundo a um preço de $ 600 por GB. É possível reduzir custos combinando várias execuções de síntese e sequenciamento.



Para um conhecimento mais detalhado das nuances do estudo, recomendo que você leia o relatório dos cientistas e materiais adicionais a ele.



Epílogo



Os geradores de números aleatórios existem há milhares de anos (os dados mais antigos encontrados no Irã têm cerca de 5.200 anos), mesmo que as pessoas daquela época não conhecessem todo o seu potencial. A tecnologia moderna e o progresso científico permitiram que eles criassem algoritmos e dispositivos complexos capazes de gerar aleatoriedade que os humanos seriam incapazes de prever. No entanto, onde a pessoa fica para trás, a tecnologia o acompanha. Em outras palavras, onde há uma cifra, também há um descriptografador. Portanto, o aperfeiçoamento gradual dos métodos de codificação de informações, onde são usados ​​geradores de números aleatórios, causa uma melhoria paralela nos métodos de hackeamento de tais sistemas. Essa corrida interminável de fechaduras e arrombamentos exige que ambos os lados apresentem cada vez mais métodos novos.



Muitos RNGs modernos são baseados em processos físicos e algoritmos. Mas as reações químicas ficaram paralisadas por muitos anos, pois se acreditava que não poderiam ser uma base confiável para um RNG. Nesse trabalho, os cientistas mostraram que a síntese de DNA, sendo um processo químico, pode não apenas ser uma versão valiosa da base de um RNG, mas também superar seus competidores "físicos" em muitos aspectos.



Naturalmente, esse método ainda é um diamante bruto que requer retificação na forma de pesquisas adicionais, cujo objetivo será aumentar a produtividade e reduzir custos. No entanto, a geração de números aleatórios usando DNA é uma direção extremamente promissora no momento.



Obrigado pela atenção, fiquem curiosos e tenham uma boa semana de trabalho, pessoal.



Um pouco de publicidade



Obrigado por ficar com a gente. Você gosta de nossos artigos? Quer ver mais conteúdo interessante? Ajude-nos fazendo um pedido ou recomendando a amigos VPS em nuvem para desenvolvedores a partir de US $ 4,99 , um análogo exclusivo de servidores básicos que inventamos para você: The Whole Truth About VPS (KVM) E5-2697 v3 (6 núcleos) 10 GB DDR4 480 GB SSD 1 Gbps de $ 19 ou como dividir o servidor corretamente? (opções disponíveis com RAID1 e RAID10, até 24 núcleos e até 40 GB DDR4).



O Dell R730xd 2x é mais barato no data center Equinix Tier IV em Amsterdã? Apenas temos 2 x Intel TetraDeca-Core Xeon 2x E5-2697v3 2.6GHz 14C 64GB DDR4 4x960GB SSD 1Gbps 100 TV a partir de $ 199 na Holanda!Dell R420 - 2x E5-2430 2,2 Ghz 6C 128 GB DDR3 2x960 GB SSD 1 Gbps 100 TB - a partir de $ 99! Leia sobre como construir a infraestrutura do prédio. classe com o uso de servidores Dell R730xd E5-2650 v4 a um custo de 9.000 euros por um centavo?



All Articles