Não-determinismo está no núcleo
das dificuldades que o experimento original de Adleman foi desenvolvido
para superar. A classe NP é definida como a classe dos problemas
algoritmos cujas soluções podem ser verificadas mas não
necessariamente eficientemente achadas. Do ponto de vista computacional,
implementar não-determinismo por um processo determinístico
é talvez a melhor contribuição de Adleman. Por outro
lado, não-determinismo é , supostamente, bem entendido no
contexto dos autômatos de estados finitos, uma vez que a construção
de subconjuntos produzem um equivalente determinístico para um autômato
não-determinístico dado. É aceitável que uma
melhor idéia sobre as dificuldades pode ser ganha tentando achar
meios de implementar não-determinismo diretamente em DNA.
Um exemplo é mostrado abaixo, ele checa a
divisibilidade por 2 e por 3 numa string binária. Ele vai ser usado
durante a nossa implementação. Um fsm não-determinístico
faz computação em runs. Uma run é uma seqüência
de transições de estados válida de acordo com a tabela
de transição W . Isto é : cada q t e W (q t-1 , x
t ) , onde x : = x , x2 ... xm é a string de entrada
e q0 é o estado inicial. No geral há mais de uma run para
uma máquina não-determinística. A nfsm aceita a entrada
se houver pelo menos uma run que seja legal e chegue com sucesso no estado
final. Alternativamente, um nfsm pode ser visto como um fsm ordinário
determinístico com a capacidade de fazer copias dele mesmo quando
faz um movimento não determinístico, e cada uma das cópias
correspondendo a um dos movimentos. Esta última visão serve
bem para a implementação de DNA devido ao grande paralelismo
na computação DNA.
A saliência da cadeia simples é nomeada
depois dos símbolos de entrada correspondentes. A cadeia dupla é
responsável pelos símbolos de entrada ( GAG é código
do nucleotídeo para 0, GCA para o 1 ; há uma molécula
inicial especial ) , e pela saliência no código onde é
informado o estado atual.
Especificamente, os estados nas fsm são codificados
por seqüências de nucleotídeos contendo bases discriminativas
dadas por:
estado [0] : atat
estado [0,3] : ttat
estado [1,3] : gctg
estado [2,3] : ctca
estado [0,2] : tatt
estado [1,2] : gtcg
A molécula inicial é :
GGGGAGATCatatCTTAA
CCCCTCTAG
Para uma boa simulação da transição, cada um dos estados precisa ter tantos anéis quantas forem as transições neles necessárias. A codificação é similar ao caso determinístico. A principal diferença é que como há mais de um caso saindo de um estado com a mesma escolha ( 0 ou 1 ) os dois casos serão apresentados.
Obs. : A cadeia de DNA é composta de duas "faixas" onde uma é o simétrico da outra trocando: A por T , G por C e vice-versa.
Exemplo :
Legenda:
- Parte do encaixe :
Onde a molécula
irá se encaixar com a seqüência. Ele deve ser simétrico
à parte de encaixe da seqüência.
- Próximo estado :
Próximo estado do
autômato.
- Caminho escolhido ( 0 ou 1 ) :
Bit que será lido
pelo autômato.
- Enzima de restrição SmaI :
As enzimas de restrição
têm como função básica fazer a ligação
e a separação ( se for o caso ) entre duas moléculas.
Esta é colocada
aqui para o encaixe entre as moléculas poder ser realizado.
- Enzima de restrição EcoRI :
Esta é colocada
para o caso de se querer fazer uma nova ligação. A parte
à direita desta enzima é desprezada e ela está pronta
para o próximo encaixe.
- Anel :
É uma cadeia dupla
de DNA com um oligo não hibridizado na forma de um loop. Os tamanhos
do loop e do nucleotídeo no anel vão variar de acordo com
o tamanho do fsm que está sendo simulado.
- Esta parte é importante :
Pois na molécula
de DNA é imprescindível que haja simetrização
entre suas “faixas”. Esta parte é escolhida sendo igual à
parte no final do loop. No [0]0 , ela ( ATC ) é igual à do
final do loop ( atC ). No momento que desprezamos a parte à
direita do EcoRI para fazer a próxima ligação, a parte
que restou à direita , de baixo , ( TAG ) deslizará para
encaixar com a parte à esquerda ( ...CTC ) . Então
o ( TAG ) passará a ser o simétrico do ( ATC ) e não
mais do loop ( atC ) como antes.
[0] 0 :
TCt
A
t
CCCGGGGAG
atCTTAAGAG c
tataGAATTGGGCCCCTC
- TAGAATTCTC
TCt
T a
CCCGGGGAG
ttCTTAAGAG c
tataGAATTGGGCCCCTC -
AAGAATTCTC
[0] 1 :
TCg
A t
CCCGGGGCA
cgCTTAAGAG c
tataGAATTGGGCCCCGT -
GCGAATTCTC
GCg
T c
CCCGGGGCA
tgCTTAAGAG c
tataGAATTGGGCCCCGT -
ACGAATTCTC
[0,3 ] 0 :
TCt
A t
CCCGGGGAG
atCTTAAGAG c
aataGAATTGGGCCCCTC -
TAGAATTCTC
[0,3 ] 1 :
GCg
T c
CCCGGGGCA
tgCTTAAGAG c
aataGAATTGGGCCCCGT -
ACGAATTCTC
[1,3 ] 0 :
ACc
C t
CCCGGGGAG
caCTTAAGAG c
cgacGAATTGGGCCCCTC -
GTGAATTCTC
[1,3 ] 1 :
TCt
A t
CCCGGGGCA
atCTTAAGAG c
cgacGAATTGGGCCCCGT -
TAGAATTCTC
[2,3 ] 0 :
GCg
T c
CCCGGGGAG
tgCTTAAGAG c
gagtGAATTGGGCCCCTC -
ACGAATTCTC
[2,3 ] 1 :
ACc
C t
CCCGGGGCA
caCTTAAGAG c
gagtGAATTGGGCCCCGT -
GTGAATTCTC
[0,2 ] 0 :
TCt
T a
CCCGGGGAG
ttCTTAAGAG c
ataaGAATTGGGCCCCTC -
AAGAATTCTC
[0,2 ] 1 :
GCg
C t
CCCGGGGCA
cgCTTAAGAG c
ataaGAATTGGGCCCCGT -
GCGAATTCTC
[1,2 ] 0 :
TCt
T a
CCCGGGGAG
ttCTTAAGAG c
cagcGAATTGGGCCCCTC -
AAGAATTCTC
[1,2 ] 1 :
GCg
C t
CCCGGGGCA
cgCTTAAGAG c
cagcGAATTGGGCCCCGT -
GCGAATTCTC
Vamos supor que queremos transformar a string "010" numa cadeia de DNA indo pelo caminho: [0] , [0,2] , [1,2] , [0,2] .
Legenda:
- Molécula Inicial
- Saindo de [0] lendo 0.
- Saindo de [0,2] lendo 1.
- Saindo de [1,2] lendo 0.
GGGGAGATCatatCTTAACCCGGGGAGATCttatCTTAACCCGGGGCACGC
gtcgCTTAACCC
CCCCTCTAGtataGAATTGGGCCCCTCTAGataaGAATTGGGCCCCGTGCGcagcGAATTGGG