Esta é uma tradução automática e o artigo original está em inglês. Ler o original
Trinta e nove cidades precisam de mais ADN do que a Terra
Uma busca de rotas por força bruta, com uma cadeia de ADN por cada ordenação candidata, precisa de meio grama de ADN para vinte cidades. Para trinta e nove, precisa de mais do que a massa da Terra.
Em 1994, Leonard Adleman dissolveu um problema de combinatória num tubo de ensaio. Codificou uma rede de estradas com sete cidades em cadeias curtas de ADN, deixou-as emparelhar em todas as rotas que a rede permitia e filtrou depois a sopa até sobrarem as rotas que passavam por cada cidade exatamente uma vez. A resposta precipitou dentro de um frasco. Foi preciso cerca de uma semana de laboratório para resolver um problema que um aluno resolve no papel num minuto, e isso não tinha a menor importância: qualquer coisa como 10¹⁴ cadeias tinham experimentado, cada uma a sua rota, ao mesmo tempo, num volume que cabia entre dois dedos.
A promessa era óbvia e enorme. A busca exponencial custa porque os candidatos explodem, e ali estava uma máquina que olhava para todos os candidatos de uma vez. Trinta anos depois, nada do que traz no bolso funciona a ADN, e a razão não é de engenharia. É aritmética que se faz nas costas de um envelope.
Conte as cadeias e depois pese-as
O paralelismo molecular compra-se uma molécula de cada vez. Cada candidato precisa da sua própria cadeia física, portanto o ADN necessário é o número de candidatos vezes a massa de uma cadeia.
O segundo fator é minúsculo. O ADN de cadeia simples anda pelos 330 gramas por mole de bases, pelo que, a vinte bases por cidade, uma cadeia de vinte cidades pesa cerca de 2 × 10⁻¹⁹ gramas. O primeiro fator é um fatorial, e um fatorial não quer saber do tamanho do segundo.
Vinte cidades: 0,53 gramas. Uma pitada de pó.
Trinta cidades: 8,7 × 10¹³ gramas. São 87 milhões de toneladas, quase a massa somada de todos os seres humanos vivos.
Trinta e nove cidades: mais do que a massa da Terra.
Nove cidades separam "uma pitada" de "o planeta", e é por isso que a DNA Computing Scale é um cursor e não um parágrafo. Subi-lo uma cidade de cada vez e ver a unidade passar de miligramas a planetas faz por si aquilo que a leitura do expoente não faz.
A objeção óbvia é que ninguém enumeraria as n! ordenações todas. Fixe a cidade de partida, recuse contar em separado um percurso e a sua imagem ao espelho, e a contagem fica dividida por 2n. Faça-o: o cruzamento passa de trinta e nove cidades para quarenta e uma. É este o retorno de todo o grupo de simetria, duas cidades.
É isto que "o paralelismo não muda a classe de complexidade" quer dizer quando se torna concreto. O tubo de Adleman comprou uma aceleração de cerca de 10¹⁴, que é um número espantoso e continua a ser uma constante. Um fatorial come 10¹⁴ e pede o prato seguinte. Duplicar o tubo compra uma fração de uma cidade.
A mesma parede, batida do outro lado
A biologia chegou primeiro a este argumento e usou-o para provar o contrário.
Em 1969, Cyrus Levinthal perguntou como é que uma proteína encontra a sua forma. Tome uma cadeia de cem resíduos e permita a cada junção apenas três orientações, uma subestimativa selvagem. Dá 3¹⁰⁰, cerca de 5 × 10⁴⁷ conformações. Deixe a cadeia experimentar uma a cada 10⁻¹³ segundos, mais ou menos uma vibração molecular e quase tão depressa quanto a física permite. Percorrê-las todas leva 1,6 × 10²⁷ anos: 10¹⁷ vezes a idade atual do universo.
As proteínas dobram-se em milissegundos.
O paradoxo de Levinthal não é um enigma sobre dobrar depressa. É uma prova de que dobrar não é procurar. A paisagem energética não é uma lotaria plana de conformações, é um funil, e uma cadeia dentro de um funil nunca está a escolher entre 10⁴⁷ opções. Está a cair. O que vale mesmo a pena levar daqui, tornado preciso por Zwanzig, Szabo e Bagchi em 1992, é a pouca inclinação de que o funil precisa. Pegaram num modelo simples e mostraram que um enviesamento energético da ordem de alguns kT contra as configurações localmente desfavoráveis chega para reduzir o tempo de Levinthal a uma dimensão biologicamente razoável. Não um algoritmo esperto. Um declive.
Mexa no número de resíduos e nos estados por resíduo no Levinthal Paradox Explorer e repare na violência com que o número resiste a tornar-se razoável. Baixar os estados por resíduo de três para dois compra um fator de 10¹⁷·⁶ e ainda deixa uma cadeia de cem resíduos a precisar de uma boa fatia da idade do universo. A base cobra-se uma vez; o expoente volta a cobrar por cada resíduo.
Ponha agora os dois argumentos lado a lado, porque a aritmética é a mesma. Uma proteína não consegue enumerar as suas conformações. Um tubo de ensaio não consegue enumerar as suas rotas. A resposta da natureza foi deixar de enumerar e construir uma paisagem que afunila. A resposta da computação com ADN foi enumerar com mais força, em paralelo, com mais moléculas, que é precisamente a jogada 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, que é outra coisa, e o argumento honesto é o melhor dos dois.
Comece pela energia. Landauer mostrou em 1961 que apagar um bit de forma irreversível tem de dissipar pelo menos kT ln 2, o que à temperatura do corpo dá 3,0 × 10⁻²¹ joules. É um piso posto pela termodinâmica e não pelo fabrico. Uma hidrólise de ATP, a moeda que a biologia gasta de facto, liberta cerca de vinte kT: 8,6 × 10⁻²⁰ joules, ou 29 vezes o piso. Uma operação lógica em CMOS de boa qualidade custa perto de um femtojoule, ou seja, 337.000 vezes o piso.
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 errado para o silício. A biologia não é um computador rápido, é um computador quase ótimo do ponto de vista termodinâmico, a trabalhar a uma temperatura em que um único evento molecular fica a dezenas de kT do mínimo teórico. Regule a temperatura e a energia por operação em Energy per Operation e a distância entre as duas deixa de se conseguir ignorar.
Depois, o armazenamento. Codifique os dados nas bases em vez de os codificar nas rotas e a densidade que tornava a força bruta absurda passa a ser o argumento inteiro: à volta 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 gastar energia nenhuma para ali ficarem quietos. A DNA Data Storage entra com as despesas reais, a indexação, os locais de ligação dos primers, os códigos que evitam longas repetições da mesma base, e a densidade sobrevive-lhes com folga.
Assim, a exponencial que mata o ADN como motor de busca é a mesma que faz dele um arquivo extraordinário. Procurar exige uma molécula por candidato, e os candidatos crescem fatorialmente. Arquivar exige uma molécula por dado, e os dados crescem linearmente. Química idêntica, densidade idêntica, veredictos opostos, e a única diferença está em qual das quantidades se mandou crescer.
A forma do argumento é a parte útil
Quando alguma coisa lhe oferecer paralelismo maciço, pergunte o que é que o paralelismo multiplica. Contra uma exponencial, não interessa quão grande é a constante: 10¹⁴ e 10²³ são o mesmo número quando o adversário é um fatorial. A experiência de Adleman não foi um protótipo precoce de supercomputador molecular. Foi uma demonstração lindamente executada de um fator constante, e o erro da área foi ler uma constante como se fosse um declive.
Levinthal fez a mesma contagem e tirou logo a conclusão certa, porque não andava a vender nada: se a contagem é impossível, o mecanismo não é o que supôs. O que sobrou depois de a história da busca se desfazer, energia quase ótima por evento e uma densidade absurda por grama, é uma mão de cartas genuinamente boa, e ninguém lhe teria olhado duas vezes enquanto a história da busca ainda estava em cima da mesa.