Clique aqui para voltar à página inicial  http://www.novomilenio.inf.br/ano98/9801bfu1.htm
Publicado originalmente pelo editor de Novo Milênio no caderno Informática do jornal A Tribuna de Santos/SP, em 13 de janeiro de 1998
Publicado em Novo Milênio em (mês/dia/ano/horário): 12/04/00 04:44:42
HISTÓRIA DO COMPUTADOR - 47 - O futuro que vem aí
Um segundo para percorrer o Caminho Hamiltoniano

O computador baseado em DNA deveria resolver um problema denominado Caminho Hamiltoniano (em homenagem ao matemático irlandês William Rowan Hamilton, que planejou o enigma em 1857). Uma versão simplificada, conhecida como o problema do caixeiro-viajante, poderia ser assim formulada: dada uma relação arbitrária de Representação de um dos vários 'tijolos' de DNA usados na solução do problemacidades pelas quais um vendedor deve passar, qual a rota mais curta ligando todas elas? A versão de Adleman limitou o número de rotas interligando as cidades ao especificar em quais o vendedor deveria iniciar e terminar sua jornada. Uma vez que nem todas as cidades estão diretamente ligadas, o objetivo seria descobrir um caminho contínuo ligando todas elas. 

Ligar quatro ou cinco cidades pode ser uma tarefa simples de se fazer com um pedaço de papel, mas quando o número de cidades cresce, o problema aumenta exponencialmente, passando ao que é conhecido como “problema pesado”, em Como na representação, bases incompatíveis não se ligam...termos matemáticos. Problemas pesados não podem ser resolvidos eficientemente por equações algébricas, as respostas só podem ser encontradas pela investigação de todas as possíveis soluções, o que pode ser difícil até para os computadores executarem. Conectar 100 cidades, num problema assim, usando um algoritmo bem conhecido e um computador que executasse um trilhão de operações por segundo, envolve um tempo de cálculo superior à própria idade do universo, ainda segundo o texto da Wired

O pesquisador limitou seu teste a sete cidades conectadas por 14 rotas possíveis, buscando um caminho que pudesse ligar as cidades norte-americanas de Atlanta e Detroit, passando pelas demais da sua lista. No dia de Natal de 1993, ele foi para o laboratório de virologia da University of Southern California. Ele vinha pesquisando O bloco vermelho representa a cidade A e o bloco laranja, a B. Sua união representa a ligação entre as cidades A e Bcomo os glóbulos brancos do sangue eram selecionados para morrer pelo HIV, mas naquele dia fez uma experiência diferente: preparou 21 tubos de ensaio com seqüências simples de DNA (uma para cada uma das sete cidades e das 14 rotas de conexão entre elas). 

Dias depois, tinha nos tubos um material que foi reunido num tubo de ensaio com solução aquosa. Em apenas um segundo, veio a resposta, a primeira do mundo dada por um computador molecular: trilhões de cópias de uma molécula com longas seqüências de “palavras” de quatro letras representando a solução do caminho hamiltoniano entre Atlanta e Detroit. Um dia depois de sua criação, o computador-DNA de Adleman (batizado como TT-100, por utilizar tubos de ensaio de 100 microlitros) já se mostrava mais rápido, econômico e de tamanho mais reduzido que seu primo eletrônico. 

A ligação – Uma versão simplificada (para facilitar a explicação) do experimento de Adleman, com quatro cidades como Atlanta, Baltimore, Chicago e Detroit e definindo-se que a partida seria em Atlanta e a chegada em Detroit, implicaria em quatro opções de vôo: Atlanta/Chicago, Chicago/Detroit, Chicago/Baltimore e Baltimore/Detroit. O caminho mais curto poderia ser voar de Atlanta a Chicago, de Chicago a Baltimore e de Baltimore a Detroit. Simples, não? Mas, experimente acrescentar algumas cidades nesse roteiro... 

Para resolver o problema com quatro cidades, Adleman usou os quatro tipos de nucleotídeos (A,T,G,C) para formar “palavras” com seqüências de seis bases: denominou Atlanta como ATGCGA, Baltimore como CGATCC, Chicago como GCTTAG e Detroit como GTCCGG. A escolha da ordem das letras não é casual: as bases das espirais do DNA só se unem de uma forma: G com C e T com A. 

Para batizar os vôos de conexão entre as cidades, pegou as três últimas letras do nome DNA da cidade de origem e as três primeiras do nome DNA da cidade de destino. Assim, o vôo Atlanta-Chicago foi chamado de CGAGCT, o de Chicago a Detroit foi batizado como TAGGTC, Chicago-Baltimore seria TAGCGA e Baltimore-Detroit seria TCCGTC. Em seguida, montou as seqüências complementares de DNA conforme a compatibilidade das bases (trocando G por C e T por A). Assim, Atlanta passou de ATGCGA para TACGCT; Chicago, para CGAATC; Baltimore, para GCTAGG e Detroit, para CAGGCC. 

Trecho da solução por DNA do problema das cidades, mostrando a união dos oligonucleotídeos no caminho B-C-D
Colocadas no tubo de ensaio, as seqüências referentes às cidades foram se ligando naturalmente de acordo com os pares de bases compatíveis. Adicionadas ao tubo de ensaio enzimas que destruíram as seqüências que não compreendiam as quatro cidades ou que começassem ou terminassem com a cidade errada, sobrou a resposta certa: Atlanta-Chicago-Baltimore-Detroit. Trilhões de moléculas executaram a operação centenas de vezes mais rápido que o mais moderno supercomputador serial da atualidade, e com um consumo de energia um bilhão de vezes mais eficiente que os computadores eletrônicos, além de uma capacidade de armazenamento de informações um trilhão de vezes mais densa que os melhores meios de armazenagem de dados atuais. 

E a computação por DNA já tem seus hackers: o pesquisador Richard Lipton e dois estudantes graduados, Dan Boneh e Christopher Dunworth, descobriram - apenas três meses depois - como esse computador genético poderia desmontar (“craquear”) rapidamente o algoritmo usado pelo governo americano para codificar seus documentos secretos: o Data Encryption Standard (DES)...