Modello di Adleman nei DNA Computing

Modello di Adleman nei DNA Computing

Nel suo famoso articolo del 1994 Adleman mostrò la possibilità di eseguire delle computazioni a livello molecolare (da qui la nascita del DNA Computing). Egli presentò una “soluzione biologica” per una istanza del problema del percorso hamiltoniano. Un cammino hamiltoniano su un grafo orientato è un percorso che inizia da un vertice ed arriva ad un altro dopo essere passato per tutti i vertici esattamente una volta; tale cammino, se esiste, sarà formato da n-1 lati se il grafo ha n vertici. Il problema del percorso hamiltoniano per un grafo orientato (PPHO) affrontato da Adleman chiede di stabilire se in un dato grafo orientato, in cui siano stati scelti due vertici, esiste almeno un cammino hamiltoniano che li unisce.

Algoritmo del modello di Adleman

L’algoritmo è il seguente:

passo 1) si generano tutti i cammini attraverso il grafo;

passo 2) si considerano solo i percorsi che iniziano dal nodo di partenza e terminano nel nodo di arrivo;

passo 3) si considerano solo i percorsi che attraversano esattamente n vertici;

passo 4) si considerano solo i percorsi che passano per un vertice una sola volta; passo 5) si verifica se almeno un percorso è rimasto dopo le selezioni dei passi precedenti; in caso positivo quello è il cammino che si stava cercando.

Frammenti di DNA come oggetti di calcolo

Adleman utilizzava dei frammenti di DNA come oggetti di calcolo e particolari enzimi e tecniche di biologia molecolare come operatori. L’implementazione di questo algoritmo si basava sull’intuizione di Adleman di codificare in maniera opportuna l’istanza del problema da risolvere.

Adleman riusci, dunque, a codificare il grafo con le seguenti regole:

  • ad ogni vertice i del grafo G si associa un filamento di una sequenza casuale di DNA della lunghezza di 20 nucleotidi;
  • ogni arco i → j in G viene codificato con un filamento di DNA di 20 nucleotidi ottenuto concatenando gli ultimi 10 nucleotidi del vertice i ed i primi 10 nucleotidi del vertice j.

In questo modo i filamenti potevano accoppiarsi per formare una macromolecola che codificasse un percorso attraverso il grafo: uno dei filamenti è la concatenazione delle sequenze di codifica di archi consecutivi, l’altro filamento è la concatenazione delle sequenze complementari associate ai vertici del percorso considerato.

Modello di Adleman nei DNA Computing
Modello di Adleman nei DNA Computing

Algoritmo biologico di Adleman

L’algoritmo biologico proposto da Adleman è il seguente:

passo 1) per ogni vertice e per ogni lato si codificano un numero sufficientemente grande di filamenti di DNA che si mettono in una provetta con acqua, con l’enzima ligasi, sali ed altre sostanze che favoriscono l’accoppiamento. In questo modo si codificano pressoché istantaneamente (quasi) tutti i possibili cammini tra i vertici.

passo 2) si procede con la reazione a catena della polimerasi per amplificare solo quei filamenti di DNA che possiedono il corretto vertice di partenza e di arrivo;

passo 3) con l’elettroforesi su gel si separano tutte le molecole di DNA che hanno la lunghezza giusta (120 nucleotidi nell’esperimento di Adleman in cui il cammino hamiltoniano era lungo 6 lati da 20 nucleotidi ciascuno).

passo 4) si selezionano i percorsi che passano per tutti i vertici con la tecnica di separazione per affinità. Questa tecnica permette di estrarre tutte le sequenze che contengono la codifica di un dato vertice, sfruttando il principio di complementarietà delle basi; ripetendo questa estrazione per ogni vertice si riescono ad estrarre tutti i percorsi che passano per ogni vertice.

passo 5) si verifica se almeno un filamento di DNA è rimasto dopo le selezioni dei passi precedenti procedendo prima ad amplificazione con polimerasi e poi con elettroforesi su gel che permette di individuare l’eventuale filamento; se esiste, quel filamento codifica il cammino hamiltoniano che si stava cercando.

La soluzione biologica

Questo esperimento non dimostrò soltanto la possibilità di ottenere una “soluzione biologica” al problema di ricerca del cammino hamiltoniano, ma anche e soprattutto la possibilità più generale di calcolare con il DNA.

Il numero di operazioni richieste in laboratorio cresce linearmente con il numero n di vertici del grafo, benché è noto che questo problema è NP-completo. Il numero di molecole diverse richieste per la computazione è lineare nel numero m degli archi del grafo; infatti il passo 1 richiede la sintesi artificiale di n+m sequenze di DNA, il passo 4 richiede la ripetizione della procedura per n volte e gli altri passi si svolgono in un tempo costante.

Questo significa che un computer a DNA offre una enorme capacità di calcolo parallelo che può renderlo molto più rapido di un supercomputer elettronico per la risoluzione di alcuni problemi, soprattutto all’aumento del numero di variabili coinvolte. Nell’esempio del PPHO il parallelismo si manifesta nella velocità con cui all’inizio si codificano (quasi) tutti i possibili cammini attraverso il grafo.

Inoltre la capacità di memorizzazione del DNA è enormemente superiore rispetto a un computer tradizionale poiché un grammo di DNA, equivalente all’incirca ad un centimetro cubo, può immagazzinare l’informazione contenuta in circa mille miliardi di CD.

 

Precedente DNA Computing e Sicurezza Informatica Successivo Modello di Lipton nei DNA Computing

Lascia un commento

*