Esta é uma tradução automática; o artigo original foi redigido em inglês. Ler o original
Trinta e nove cidades precisam de mais ADN do que a Terra
Uma pesquisa de rotas por força bruta com uma cadeia de ADN por ordenação candidata necessita de meio grama de ADN para vinte cidades. Para trinta e nove, necessita de mais do que a massa da Terra.
Em 1994, Leonard Adleman dissolveu um problema combinatório num tubo de ensaio. Codificou uma rede rodoviária de sete cidades sob a forma de cadeias curtas de ADN, deixou-as hibridar em todas as rotas que a rede permitia e, em seguida, filtrou a mistura até obter as rotas que visitavam cada cidade exatamente uma vez. A resposta precipitou a partir de um frasco. Foi necessária cerca de uma semana de trabalho laboratorial para resolver um problema que um estudante resolve no papel num minuto, e isso era completamente irrelevante: cerca de 10¹⁴ cadeias tinham experimentado, cada uma, uma rota em simultâneo, num volume que se podia segurar entre dois dedos.
A promessa era evidente e enorme. A pesquisa exponencial é difícil porque os candidatos explodem; ali estava uma máquina que examinava todos os candidatos de uma só vez. Trinta anos mais tarde, nada no seu bolso funciona a ADN, e a razão não é de engenharia. É aritmética que se pode fazer num envelope.
Contar as cadeias, depois pesá-las
O paralelismo molecular adquire-se uma molécula de cada vez. Cada candidato necessita da sua própria cadeia física, pelo que o ADN necessário é o número de candidatos multiplicado pela massa de uma cadeia.
O segundo fator é muito pequeno. O ADN de cadeia simples tem cerca de 330 gramas por mole de bases, pelo que, a vinte bases por cidade, uma cadeia para vinte cidades pesa aproximadamente 2 × 10⁻¹⁹ gramas. O primeiro fator é um fatorial, e a um fatorial é indiferente quão pequeno seja o segundo fator.
Vinte cidades: 0,53 gramas. Uma pitada de pó.
Trinta cidades: 8,7 × 10¹³ gramas. Isso são 87 milhões de toneladas, cerca de um quinto da massa combinada de todos os seres humanos vivos.
Trinta e nove cidades: mais do que a massa da Terra.
Dezanove cidades separam "uma pitada" de "o planeta", razão pela qual o DNA Computing Scale é um cursor deslizante em vez de um parágrafo. Avance uma cidade de cada vez e a escala comparável sobe de "menos de um grama", passando por quilogramas e toneladas, até "pelo menos uma massa da Terra". Ver isso acontecer produz um efeito que a leitura do expoente não consegue.
A objeção óbvia é que ninguém enumeraria todas as n! ordenações. Fixe-se a cidade de partida e recuse-se contar um percurso e a sua imagem especular separadamente, e a contagem divide-se por 2n. Faça-se isso: o ponto de transição passa de trinta e nove cidades para quarenta e uma. Esse é todo o benefício obtido de todo o grupo de simetria — duas cidades.
É isto que significa "o paralelismo não altera a classe de complexidade" quando tornado concreto. O tubo de Adleman proporcionou uma aceleração de cerca de 10¹⁴, o que é um número assombroso e, ainda assim, uma constante. Um fatorial engole 10¹⁴ e pede o prato seguinte. Duplicar o tubo rende uma fração de uma cidade.
O mesmo muro, atingido pelo outro lado
A biologia chegou primeiro a este argumento e utilizou-o para provar o ponto oposto.
Em 1969, Cyrus Levinthal perguntou de que modo uma proteína encontra a sua forma. Tome-se uma cadeia de cem resíduos e permita-se a cada junção apenas três orientações, uma estimativa largamente por defeito. Isso dá 3¹⁰⁰, cerca de 5 × 10⁴⁷ conformações. Deixe-se a cadeia experimentar uma a cada 10⁻¹³ segundos, sensivelmente uma vibração molecular e tão rápido quanto a física permite. Amostrá-las a todas levaria 1,6 × 10²⁷ anos: 10¹⁷ vezes a idade atual do universo.
As proteínas enovelam-se em milissegundos.
O paradoxo de Levinthal não é um enigma sobre enovelar-se rapidamente. É uma prova de que o enovelamento não é uma pesquisa. A paisagem de energia não é uma lotaria plana de conformações, mas sim um funil, e uma cadeia num funil nunca está a escolher entre 10⁴⁷ opções. Está a cair. Zwanzig, Szabo e Bagchi calcularam em 1992 quão pequena pode ser a inclinação do funil. Utilizaram um modelo simples e demonstraram que uma inclinação energética da ordem de alguns kT contra configurações localmente desfavoráveis é suficiente para reduzir o tempo de Levinthal para uma dimensão biologicamente razoável. Não um algoritmo engenhoso. Um declive.
Altere o número de resíduos e os estados por resíduo no Levinthal Paradox Explorer e veja com que violência o número resiste a tornar-se razoável. Reduzir os estados por resíduo de três para dois rende um fator de 10¹⁷·⁶ e ainda deixa uma cadeia de cem resíduos a necessitar de uma boa fração da idade do universo. A base vale um único pagamento; o expoente volta a cobrar por cada resíduo.
Agora coloque os dois argumentos lado a lado, porque se trata da mesma aritmética. Uma proteína não pode enumerar as suas conformações. Um tubo de ensaio não pode enumerar as suas rotas. A resposta da natureza foi parar de enumerar e construir uma paisagem que afunila. A resposta da computação com ADN foi enumerar ainda mais afincadamente, em paralelo, com mais moléculas, o que é precisamente o movimento que a contagem proíbe.
O que sobrevive
Nada disto faz da computação molecular um beco sem saída. Torna errado o argumento de venda, o que é algo diferente, e a proposta honesta é a melhor.
Comece-se pela energia. Landauer demonstrou em 1961 que apagar um bit de forma irreversível tem de dissipar pelo menos kT ln 2: à temperatura corporal, 3,0 × 10⁻²¹ joules. Trata-se de um limite mínimo imposto pela termodinâmica, não pelo fabrico. Uma hidrólise de ATP, a moeda que a biologia efetivamente gasta, liberta cerca de vinte kT: 8,6 × 10⁻²⁰ joules, ou 29 vezes o limite mínimo. Uma operação lógica num bom CMOS custa algo próximo de um femtojoule, o que representa 337 000 vezes o limite mínimo.
evento molecular ≈ 29 × kT ln 2 · lógica em silício ≈ 337 000 × kT ln 2
Quatro ordens de grandeza, e estão do lado desfavorável para o silício. Uma célula computa lentamente e quase no mínimo termodinâmico, a dezenas de kT de um limite mínimo que um transístor falha por centenas de milhares. Defina a temperatura e a energia por operação em Energy per Operation e a diferença torna-se difícil de ignorar.
Depois, o armazenamento. Codifiquem-se os dados nas bases em vez de nas rotas e a densidade que tornava a força bruta absurda torna-se todo o argumento de venda: cerca de 3 × 10²⁰ bytes por grama. Todos os filmes alguma vez estreados, em menos volume do que um cubo de açúcar, estáveis durante séculos no escuro e sem consumir energia em repouso. O DNA Data Storage inclui as sobrecargas reais — indexação, locais de ligação de iniciadores, os códigos que evitam sequências longas da mesma base — e a densidade sobrevive-lhes confortavelmente.
Assim, a exponencial que inviabiliza o ADN como motor de pesquisa é a mesma exponencial que faz dele um arquivo extraordinário. Pesquisar necessita de uma molécula por candidato, e os candidatos crescem fatorialmente. Arquivar necessita de uma molécula por dado, e os dados crescem linearmente. Química idêntica, densidade idêntica, veredictos opostos, e a única diferença é qual a quantidade que se pediu para escalar.
A estrutura do argumento
Quando algo lhe propuser paralelismo massivo, pergunte o que é que o paralelismo multiplica. Contra uma exponencial, não importa quão grande seja a constante: 10¹⁴ e 10²³ são o mesmo número quando o adversário é um fatorial. A experiência de Adleman foi uma demonstração magnificamente executada de um fator constante, e a área interpretou-a como um declive.
Levinthal fez a mesma contagem e tirou imediatamente a conclusão correta, porque não estava a vender nada: se a contagem é impossível, o mecanismo não é o que se supôs. O que restou quando a narrativa da pesquisa se desvaneceu — energia por evento quase ótima, densidade absurda por grama — é um trunfo genuinamente valioso, e ninguém teria olhado duas vezes para ele enquanto a história da pesquisa ainda estivesse sobre a mesa.