← Biologia e Química

Escala da computação com DNA

O DNA pode testar muitas rotas em paralelo, mas n! candidatos ainda exigem n! moléculas.

A carregar a simulação interativa...

Paralelismo não elimina complexidade

O experimento de Adleman provou que reações moleculares podem filtrar caminhos candidatos. Não eliminou o crescimento fatorial. Dar uma molécula a cada rota apenas converte tempo de computação em material: o número e a massa das fitas continuam crescendo como n!.

Nenhuma codificação vale uma cidade

Multiplique por dez as bases por cidade e a massa necessária multiplica-se exatamente por dez — e o ponto em que ultrapassa a massa da Terra não se move nada: 39 cidades com 20 bases cada, 39 com 200. Mesmo uma impossível base única por cidade apenas o empurra para 40. A codificação é um fator constante. n! não é.

Cada cidade nova custa mais do que a anterior

Acrescentar uma cidade multiplica o necessário por (n+1)²/n: as permutações novas e, para cada uma delas, uma cadeia mais longa. São 22× com vinte cidades, 32× com trinta e 41× ao passar de trinta e nove para quarenta. Um grama cobre 21 cidades e uma tonelada cobre 25: mais quatro cidades por um fator de um milhão.

Problema resolvido na íntegra

  1. A rota de 20 cidades que cabe em meio grama, e a de 39 cidades que não cabe na Terra 6 passos

    Uma rota do caixeiro-viajante de 20 cidades é codificada da forma como Adleman fez: uma cadeia de DNA por rota candidata, 20 nucleótidos por cidade. Calcule quanto pesa a biblioteca de DNA. Depois, adicione cidades até deixar de ser possível e diga qual é realmente o limite.

    Abrir este problema na ferramenta

    1. Comece por contar os candidatos. Com a cidade inicial fixa, uma rota é uma ordenação das restantes cidades, pelo que existem 20! delas. Isto é 2.432.902.008.176.640.000 — digamos 2,43 × 10¹⁸.

      20!=2,432,902,008,176,640,000≈2.43×101820! = 2{,}432{,}902{,}008{,}176{,}640{,}000 \approx 2.43 \times 10^{18}

    2. Pese agora um candidato. Cada uma das 20 cidades contribui com 20 nucleótidos, pelo que uma cadeia tem 400 nt de comprimento, e o DNA de cadeia simples tem cerca de 330 g por mole de nucleótido.

      L=20×20 nt=400 ntL = 20 \times 20\ \mathrm{nt} = 400\ \mathrm{nt}

    3. Uma mole corresponde ao número de Avogadro de cadeias, pelo que se divide por este para obter a massa de uma única molécula: 400 × 330 ÷ 6,022 × 10²³, o que dá 2,19 × 10⁻¹⁹ g.

      m1=400×3306.022×1023=2.19×10−19 gm_1 = \frac{400 \times 330}{6.022 \times 10^{23}} = 2.19 \times 10^{-19}\ \mathrm{g}

    4. Multiplique os dois. 2,43 × 10¹⁸ cadeias a 2,19 × 10⁻¹⁹ g cada uma dá 0,533 g — meio grama, num tubo de ensaio, e é este o número que faz a computação por DNA parecer funcionar.

      M=2.43×1018×2.19×10−19=0.533 gM = 2.43 \times 10^{18} \times 2.19 \times 10^{-19} = 0.533\ \mathrm{g}

    5. Adicione uma cidade. A contagem multiplica-se por 21 e a cadeia cresce para 420 nt, pelo que a massa multiplica-se por 21 × (420/400) = 22,05, o que dá 11,8 g. A cidade extra custou vinte e duas vezes a biblioteca anterior inteira.

      M21M20=21×420400=22.05  ⇒  11.8 g\frac{M_{21}}{M_{20}} = 21 \times \frac{420}{400} = 22.05 \;\Rightarrow\; 11.8\ \mathrm{g}

    6. Continuando, o próprio multiplicador cresce, porque é (n+1) × (1 + 1/n). Com 38 cidades, a biblioteca pesa 2,18 × 10²⁶ g, o que representa 3,65% da Terra. Com 39, pesa 8,72 × 10²⁷ g, e a Terra pesa 5,97 × 10²⁷.

      M39=8.72×1027 g  >  M⊕=5.97×1027 gM_{39} = 8.72 \times 10^{27}\ \mathrm{g} \;>\; M_{\oplus} = 5.97 \times 10^{27}\ \mathrm{g}

    Resposta

    Meio grama com 20 cidades, e 1,46 Terras com 39. O salto de 38 para 39 é um fator de 40,0, e leva o requisito de um vigésimo sétimo do planeta para uma vez e meia o planeta — uma única cidade. Este é todo o argumento contra a força bruta molecular, e repare no que ele não é: não é que o DNA seja lento, nem que a química seja pouco fiável, nem que não consigamos construir as cadeias. Cada um desses aspetos poderia ser resolvido. O que não se pode resolver é que n! moléculas pesam n! moléculas. O paralelismo massivo divide o TEMPO pelo número de processadores e deixa a contagem de processadores exatamente onde estava, pelo que um problema que precise de mais processadores do que átomos disponíveis não está à espera de melhor engenharia. A ferramenta desenha a curva de massa contra a linha da Terra; o que não consegue desenhar é o crescimento desse multiplicador, porque imprime uma massa e nunca uma razão.

Percurso de aprendizagem

Calcular com moléculas

Referências (2)

· Verificado com fontes publicadas. Correções bem-vindas.