Fasi degli algoritmi DNA

Quando i legami tra due stringhe di DNA hanno luogo (sotto condizioni ideali) sappiamo che le basi opposte sono complementari, quindi basta cono­scerne una per avere l’altra, perché la complementarietà di Watson-Crick da un singolo filamento di DNA ci permette di ottenerne uno doppio. Questo fenomeno è cruciale nelle ultime due fasi del seguente schema generale di un algoritmo DNA.

Dato un problema, la tipica metodologia del DNA Computing si avvale di tre fasi:

1. Codifica

Consiste nel tradurre, con una funzione opportuna, l’istanza del proble­ma in un multinsieme di stringhe DNA.

2. Operazioni molecolari

Si tratta di operazioni in provetta che processano i dati in dimensione molecolare. Questa fase consiste nel favorire le condizioni che permet­tono alle molecole di DNA di reagire tra di loro, in modo da ottenere una provetta con stringhe codificanti un insieme di potenziali soluzione del problema (generalmente ottenute per “annealing” e “ligazione” dalle stringhe iniziali codificanti i dati

3. Estrazione del risultato

Si usano dei protocolli per estrarre il risultato (in forma molecolare): nella miscela ottenuta nella fase precedente si separano le soluzioni del problema (“stringhe buone”) dalle non soluzioni (“stringhe non buone”), e si estraggono.

Sono stati proposti algoritmi DNA per l’espansione dei determinanti simbolici, per la connessione dei grafi e il problema dello zaino usando la programmazione dinamica, per il problema della colorazione delle strade, per la moltiplicazione di matrici e per l’addizione.