NATURAL COMPUTING: La Rivoluzione Copernicana dell'Informatica

Uno dei più grandi fisici del Novecento, Richard Feynman, in uno straordinario discorso tenuto nel 1959, aveva delineato le incredibili prospettive del processo di miniaturizzazione in atto nella tecnologia, ipotizzando che fosse possibile arrivare a costruire dispositivi di varia natura utilizzando individualmente persino gli stessi atomi. Erano gli anni in cui l'industria dei semiconduttori muoveva i primi passi e le dimensioni dei transistor erano ancora dell'ordine di frazioni di centimetro. I transistor avevano appena iniziato a sostituire le valvole termoioniche nella costruzione dei computer e nessuno poteva ancora immaginare con quanta rapidità si sarebbe evoluta la tecnica fotolitografica con la quale interi circuiti sarebbero stati disegnati sulle piastre di silicio. Nel 1965 Gordon Moore, uno dei fondatori della Intel©, osservò empiricamente che la potenza dei processori, ovvero il numero di transistor in un chip, raddoppiava ogni diciotto mesi circa. Oggi, quasi quaranta anni più tardi, la cosiddetta “legge di Moore” viene confermata ogni anno, e nel 2014 verrà raggiunto il limite fisico di miniaturizzazione dei transistor. Oltre non si potrà andare e, se si vorranno calcolatori più potenti, si dovrà cambiare necessariamente qualcosa. Questi sono i motivi fondamentali che, da poco più di un decennio, spingono i ricercatori di tutto il mondo a mettere a punto tecniche di computazione basate su principi e “materiali” diversi dal silicio.

L'utilizzo di alcune specifiche risorse naturali per risolvere problemi computazionali complessi, è lo scopo principale di quella disciplina ormai nota sotto il nome di Natural Computing che annovera, tra le sue file, diverse tecniche di computazione non convenzionale: Quantum Computing, Swarm Intelligence, Cellular Computing, Membrane Computing, Microfluidics Computing e DNA Computing. Tutte si basano sulle ridottissime dimensioni dei materiali utilizzati, un forte orientamento al parallelismo e la possibilità di immagazzinare informazioni utilizzando un alfabeto di simboli maggiore di due. Negli ultimi anni, la tecnica di computazione non convenzionale più sviluppata è stata quella del DNA computing, da un lato per la semplicità con cui è possibile reperire specifico materiale biologico, dall’altro per la tangibile possibilità di risolvere problemi computazionali complessi, anche di natura bioinformatica, proprio con l’utilizzo di molecole di DNA.




QUANTUM COMPUTING

Il Computer Quantistico è, teoricamente, un dispositivo di calcolo in grado di effettuare complesse elaborazioni numeriche sulla base di proprietà tipiche delle particelle elementari. Nonostante la difficile comprensione dei principi fondamentali della meccanica quantistica, la progettazione logica del computer quantistico si sta sviluppando in questi ultimi anni in maniera sempre più vivace. Immaginiamo, in un modello del tutto intuitivo, un atomo che abbia un solo elettrone nell'orbita più esterna. Questo elettrone può essere eccitato in un'orbita più ampia irradiandolo con una luce di una particolare frequenza. Se lo stato eccitato è abbastanza stabile possiamo utilizzare quest'ultimo e lo stato precedente rispettivamente come gli stati 1 e 0. Se lo stesso raggio di luce viene inviato sull'elettrone quando questo si trova nell'orbita esterna esso ritorna all'orbita interna, emettendo un fotone, particella elementare che compone la luce. Questo meccanismo, descritto in maniera quanto mai approssimativa, potrebbe essere utilizzato per realizzare a livello di un singolo atomo l'operatore NOT. Ma che succede se inviamo sull'elettrone un raggio di luce per una durata di tempo che è la metà di quella necessaria a farlo saltare nell'altra orbita? L'elettrone potrà trovarsi simultaneamente in entrambe le orbite. Questo fenomeno viene descritto come sovrapposizione di stati. Se, a questo punto, immaginiamo che l'atomo in questione sia un bit, esso potrebbe contenere contemporaneamente i due valori 0 e 1. Solo quando andremo a misurare il valore dell'atomo esso collasserà in uno stato definito. Un simile bit viene definito un qbit. È intuibile che un gruppo di qbit può contenere un certo insieme di valori. Per esempio tre qbit contengono contemporaneamente otto diverse combinazioni, da 000 a 111. Per ora il modello di computer quantistico è puramente teorico, anche se in diverse parti del mondo numerosi esperimenti stanno portando ad una realizzazione ibrida di microchip e di qbit, in cui una nube di elettroni è intrappolata sulla superficie del chip attraverso forze magnetiche, permettendo così il passaggio dei dati attraverso gli elettroni. Inoltre é in fase di studio la possibilità di trasmettere dati attraverso i “fotoni”. I dati così trasmessi verrebbero poi ordinati facendo passare il raggio di luce che li contiene attraverso particolari cristalli in grado di separarli e permettere così di ricostruirne la giusta sequenza.

[Torna su]





SWARM INTELLIGENCE

La Swarm Intelligence è una particolare classe di algoritmi che ha origine da metafore di alcuni modelli comportamentali di insetti sociali, quali api, formiche, vespe etc. Questi particolari sistemi sono composti da esseri viventi dotati di modestissime capacità intellettive ed in grado di risolvere problemi di elevata complessità. Ogni insetto sembra comportarsi secondo un piano prestabilito in modo che il sistema, nel suo complesso, abbia un comportamento organizzato e finalizzato al raggiungimento di specifici obbiettivi. L’aspetto interessante di questi sistemi è che questi comportamenti emergono naturalmente, senza la presenza di un coordinatore o supervisore. Un tipico esempio di applicazioni di Swarm Intelligence è costituito dai cosiddetti “ant algorithms”, cioè algoritmi sviluppati a partire dal modello comportamentale delle formiche. Le formiche, infatti, hanno la capacità di trovare il percorso più breve dal formicaio ad un punto qualsiasi del terreno, in cui vi sia del cibo. L’aspetto interessante e curioso è che sono in grado di farlo senza informazioni visive, ma utilizzando segnali odorosi. Quando una formica ha trovato del cibo, ritorna al formicaio depositando sul terreno una certa quantità di una sostanza chimica detta feromone. La direzione del cammino di una formica dipende dalla quantità di feromone che essa percepisce: dove la concentrazione è più forte, è più probabile che la formica si diriga. Le tracce di feromone, però, evaporano nel tempo, quindi, devono essere rinforzate dal passaggio di altre formiche. A questo punto entra in gioco un meccanismo molto importante chiamato retroazione positiva: più formiche scelgono un percorso, più forte sarà la concentrazione di feromone presente sul terreno, quindi ancora più formiche saranno richiamate sullo stesso percorso. Perciò, dopo una prima fase transitoria, in cui le formiche scelgono direzioni diverse, si arriva ad una situazione stazionaria in cui la maggior parte delle formiche segue uno stesso percorso. Il percorso più breve sarà quello scelto, alla fine, dall’intero sistema di formiche. Algoritmi di questo tipo sono utilizzati per risolvere problemi di ottimizzazione, di cammino minimo su grafi o, in robotica, per l’analisi ed il coordinamento dei robot. Grazie al forte parallelismo di cui possono beneficiare, sono inoltre utilizzati per la risoluzione di problemi NP-Hard.

[Torna su]





CELLULAR COMPUTING

Con il termine Cellular Computing, si definisce una tecnica di computazione non convenzionale che si propone di utilizzare, come unità di calcolo, le cellule vive. In esse viene opportunamente sfruttato il meccanismo che regola l’espressione dei geni, basato sulla presenza di particolari sequenze lungo il Dna e di particolari proteine presenti nella cellula. Il Cellular Computing, come la gran parte delle computazioni basate su bioware, si rifanno ad un modello matematico di base: l’Automa Cellulare. Un Automa Cellulare rappresenta il modello matematico di un generico sistema dinamico, definito in uno spazio finito ed in tempi discreti. Esso fornisce una rappresentazione immediata di fenomeni in cui l’evoluzione globale dipende esclusivamente da leggi locali. Questo è il caso, ad esempio, del comportamento fisico dei gas perfetti (Microfluidics Computing), ma anche del movimento delle cellule in soluzione (Cellular Computing). Un Automa Cellulare può essere visto come una struttura regolare di elementi identici ed interagenti; un reticolo regolare, costituito da celle a coordinate intere. Si supponga che ciascuna delle celle rappresenti un elemento ben definito (una cellula, un calcolatore, ecc). Si supponga, inoltre, che tali elementi possano assumere un numero finito di “stati” (forme, colori, temperatura, ecc). Lo stato di ogni elemento dipende dal suo stato precedente e da quello delle celle adiacenti. Se a tempi fissati, tutti gli elementi cambiano il proprio stato contemporaneamente, ciascuno a seconda degli stati dei propri vicini, si avrà un automa cellulare. Una definizione formale di automa cellulare deve tener conto di due caratteristiche fondamentali. La prima è l’uniformità, dovuta al fatto che gli elementi che si trovano in ciascuna cella sono identici. La seconda è la località, in quanto ogni elemento tiene conto solo di ciò che succede entro una certa distanza da sé. Se indichiamo lo spazio come un ambiente euclideo, allora esso può essere definito come l’insieme degli interi “Z”. A questo punto bisogna definire l’insieme degli stati, che è finito e maggiore di uno. Dopodichè bisogna stabilire quali sono i vicini che influiscono sull’evoluzione di una singola cella, e a quale distanza giacciono. Possiamo riassumere quanto detto, dando la seguente definizione formale: un automa cellulare è una quadrupla [d,Q,N,f] dove:

- d è un numero intero positivo, detto dimensione.
- Q è un insieme fittizio, detto spazio degli stati.
- N è un sottoinsieme finito di Zd , detto indice di vicinato.
- f è la funzione di transizione che permette il passaggio da uno stato all’altro.

L’obbiettivo degli automi cellulari è quello di fornire ambienti teorici fortemente paralleli, in cui è possibile di risolvere problemi computazionali esponenziali in tempo costante. Questo è infatti l’obbiettivo del Cellular Computing ed in generale di tutti i modelli biologici di computazione.

[Torna su]





MEMBRANE COMPUTING & P-SYSTEMS

Il Membrane Computing è un modello teorico di computazione parallelo e distribuito, introdotto nel 1998 da G. Paun. Tale modello nasce dall’osservazione che i processi che hanno luogo a livello cellulare, possono essere interpretati come processi di calcolo. Le operazioni fondamentali, eseguite a livello cellulare, sono rappresentate dalle reazioni chimiche che avvengono nella struttura compartimentale delle cellule vive. In altre parole, un generico passo computazionale è rappresentato dal risultato di una reazione chimica, avvenuta in una particolare regione della membrana cellulare. I modelli matematici che formalizzano questo tipo di processi sono chiamati P-Systems, ed hanno le seguenti caratteristiche: le sostanze chimiche sono descritte come simboli di un alfabeto, le reazioni chimiche, come regole di una grammatica e le parole generate dalla grammatica sono transizioni fra le configurazioni del sistema. Una sequenza di transizioni è un’operazione computazionale. La Membrane Computing si occupa dell’analisi di questi modelli computazionali, delle classi di linguaggi generati dalle grammatiche e delle differenze dei modelli matematici a seconda sistemi biologici di riferimento. La struttura della membrana cellulare può essere rappresentata matematicamente come un albero. Questa rappresentazione strutturata permette di considerare diversi parametri computazionali, come la profondità, il numero di nodi, i percorsi di raggiungibilità etc. La struttura della membrana cellulare e le regole ad essa associate permettono di processare i dati in parallelo, fornendo un mezzo computazionale altamente efficiente per la risoluzione di problemi computazionali, difficilmente risolvibili con i computer convenzionali. I P-System forniscono, inoltre, un modello di ambiente di calcolo parallelo molto efficiente, atto ad eseguire algoritmi di uso generale che lasciano intravedere applicazioni interessanti nel campo della bioinformatica.

[Torna su]





MICROFLUIDICS COMPUTING

Questo singolare modello computazionale, nato solamente qualche anno fa, si basa sul comportamento fisico di sostanze allo stato liquido o gassoso, sotto gli influssi delle leggi della fluidodinamica. L’idea di base è che ogni molecola in soluzione, si comporta esattamente come tutte le altre, simulando il comportamento di un’unità computazionale che lavora in parallelo insieme a tutte le altre. I dati sono codificati dalle caratteristiche fisiche della soluzione, quantità, densità, peso specifico etc. L’elaborazione vera e propria, invece, viene effettuata attraverso lo scambio di materiale tra diversi fluidi ed attraverso una manipolazione fisica delle soluzioni. I primi esperimenti portati avanti hanno designato l’implementazione di algoritmi paralleli, basati sui movimenti fisici dei microfluidi per risolvere problemi non polinomiali, in maniera non deterministica (per esempio il problema della clique di dimensione massima in un grafo).

[Torna su]





DNA COMPUTING

Maggiormente futuribile è il concetto di DNA Computing, dove l’idea di base è quella di codificare l'informazione attraverso una o più sequenze di DNA. La doppia elica del DNA è formata da due filamenti, avvolti a spirale e tenuti insieme dai legami che si stabiliscono tra le quattro basi. Tali legami hanno un ordine obbligatorio: l’adenina (A) può legarsi solo alla timina (T) e la guanina (G) solo alla citosina (C). Le due catene hanno quindi sequenze complementari e l'informazione risiede nell’ordine di successione delle basi. La ricerca ha prodotto due diverse tecniche per la computazione attraverso sequenze di DNA, la computazione in vitro e quella in vivo. Nella computazione in vitro le catene che costituiscono l'input di un programma sono sintetizzate in laboratorio e raccolte in una provetta (da questo il termine in vitro) così da essere libere di combinarsi, evolvere e duplicarsi secondo le regole chimico-biologiche che gli sono proprie. Dopo una serie di operazioni bio-fisiche, le sequenze di DNA rimaste nella provetta rappresentano l'output del programma. Le tecnologie attuali permettono di preparare sequenze di DNA specifiche, di far duplicare catene selezionate di nucleotidi e di leggere le sequenze in uscita. L’idea della computazione in vivo é quella di manipolare le sequenze di DNA direttamente all’interno di cellule “vive” attraverso i processi chimici e biologici operati dagli enzimi per la sintesi delle proteine. I bioinformatici considerano l’enzima della Dna-Polimerasi la più complessa nanomacchina molecolare conosciuta, in grado di leggere un’elica di DNA e scrivere la sua versione complementare in una nuova elica. Il comportamento di questo enzima ricorda quello della macchina di Turing, paradigma di qualsivoglia computer, nella quale viene letto un nastro che a sua volta viene riscritto in qualche modo. Il fatto che nell'elica del DNA ci siano quattro possibili simboli (A,T,G,C), mentre nel nastro di Turing i simboli sono due (O e 1), è sostanzialmente irrilevante. Ma l’idea dei calcolatori molecolari va oltre il concetto di DNA Computing. All’Università di Berkeley, in California, è stato costruito il primo chip bionico, costituito da una cellula completamente integrata con circuiti elettrici. Il bio-chip funziona così: la cellula non trasferisce corrente fino a quando non viene raggiunto un voltaggio prestabilito. A quel punto i pori della membrana si aprono e la corrente attraversa la cellula, trasportando lo “stimolo” elettrico. Cellule diverse funzionano a voltaggi differenti. All’Applied Chaos Laboratory, del Georgia Institute of Technology, sono riusciti a creare un prototipo di computer organico, un ibrido al confine tra vita animale e vita artificiale. L’elaboratore non ha memoria RAM, neppure dischi fissi, ma la memoria di base è assicurata da alcuni neuroni di sanguisuga collegati a una piastrina di silicio. Oggi il computer riesce a fare solo qualche addizione e sottrazione, ma in futuro il nuovo dispositivo potrebbe essere considerato il predecessore dei computer biologici.

PRINCIPALI APPLICAZIONI

Il primo a dimostrare sperimentalmente la possibilità di utilizzare sequenze di Dna come mezzo di computazione fu Leonard Adleman, che nel 1994 risolse una particolare istanza del problema del “Cammino Hamiltoniano” attraverso alcuni strumenti dell’ingegneria molecolare, gettando così le basi di un nuovo paradigma di computazione. Successivamente la ricerca si indirizzò verso la risoluzione di problemi NP-Hard ed NP-Completi e sviluppò modelli teorici per creare un computer universale basato su DNA. Altre ricerche si sono concentrate invece sul miglioramento dei tassi d’errore delle operazioni biologiche e sull’identificazione di specifiche tecniche di ingegneria molecolare che potessero essere utilizzate per scopi computazionali e di memorizzazione. Da questo lavoro ne scaturisce una ricca bibliografia che tocca diversi campi d’applicazione, dai problemi computazionali classici alla crittografia, dalla risoluzione di problemi NP-Completi alla realizzazione di memorie di massa, fino alla giovanissima DNA2DNA Computing, che rappresenta la nuova sfida nel campo della Bioinformatica.

Problemi computazionali classici – Uno dei maggiori vantaggi offerti dal DNA Computing è la possibilità di occuparsi di milioni di operazioni in parallelo. Questo massiccio parallelismo è la caratteristica che ha spinto i ricercatori a risolvere, attraverso il DNA Computing, problemi già affrontati con successo con i computer tradizionali. Le operazioni aritmetiche, ad esempio, sono uno di questi problemi.

Risoluzione di problemi NP-Complete - Dopo i risultati di Adleman la ricerca ha concentrato i suoi sforzi sulla risoluzione di problemi NP-Completi. L’informatica teorica classifica questo tipo di problemi come “intrattabili” e riesce a trovare soluzioni solamente con un certo grado di approssimazione. Vedremo che con l’ausilio della computazione molecolare a molti di questi problemi è stata data una soluzione in tempo polinomiale o addirittura lineare rispetto all’input. La possibilità di ottenere soluzioni trattabili per problemi NP-Completi ed altri problemi “Hard Computationally” rende enormi benefici ai problemi di vita reale. Basti pensare a tutti quei casi di pianificazione, di gestione dei trasporti o di analisi dei sistemi di trasmissione, tutti facilmente risolubili attraverso un adeguato rimaneggiamento di molecole di DNA.

Crittografia - Il primo esempio di utilizzo della computazione molecolare per sistemi di crittografia fu dato da D. Boneh, C. Dunworth e R. J. Lipton, che, in un testo del 1995, descrivono la procedura biologica per un possibile attacco al DES, il più famoso cifrario a blocchi americano, capace di cifrare stringhe di 64 bit attraverso una chiave da 56 bit. La sicurezza di questo sistema si basa solamente sulla segretezza della chiave, visto che l’algoritmo di cifratura è pubblico ed accessibile a tutti. L’attacco cosiddetto “di forza bruta”, consisteva nel rappresentare tutte le 256 possibili chiavi attraverso sequenze di DNA e, a partire da una coppia testo in chiaro testo cifrato, trovare la giusta chiave di cifratura. Un attacco di questo tipo era gia stato portato avanti con i sistemi convenzionali ma con un grossissimo sforzo computazionale e di tempo. Grazie al forte parallelismo con cui è possibile lavorare sulle molecole di DNA un attacco di questo tipo raggiunge l’obbiettivo prefissato in molto meno tempo e con uno sforzo computazionale assai ridotto. Dopo questo esperimento altri esempi di crittografia e steganografia sono stati realizzati attraverso la computazione molecolare e per molti studiosi rappresenta la vera innovazione nel campo della sicurezza delle trasmissioni.

Memoria di massa ed associativa - Una delle caratteristiche del DNA Computing è la possibilità di immagazzinare una grande quantità di informazioni attraverso le quattro basi che la compongono. Nel 1996 il prof. E. Baum ipotizzò la possibilità di utilizzare molecole di DNA per realizzare una memoria indicizzabile con caratteristiche simili alle capacità associative del cervello umano. Secondo questo modello sarebbe possibile reperire facilmente le informazioni attraverso input anche non completi, così come avviene nel cervello umano, dove le informazioni sono recuperate attraverso stimoli nervosi diversi. In questo modo si avrebbe una forte accelerazione nei tempi di ricerca e nel reperimento delle informazioni, rispetto alle tecniche attualmente in uso. Inoltre se si pensa che il cervello umano può immagazzinare e distinguere approssimativamente 106 concetti diversi, mentre in un litro di soluzione contenente soli 50g di DNA potremmo immagazzinare circa 1020 parole, sarebbe possibile immagazzinare tutto lo scibile umano in poche centinaia di grammi di DNA. Questa ipotesi, ancora oggi spinge gli studiosi di tutto il mondo alla realizzazione pratica della prima memoria associativa a DNA.

DNA2DNA - Il DNA2DNA Computing nasce dall’esigenza, da parte dei bioinformatici, di leggere ed analizzare l’intero patrimonio genetico di una cellula animale. Anche gli algoritmi più complessi, su computer convenzionali, hanno portato solamente a soluzioni parziali per questo tipo di problemi e con uno sforzo computazionale ed economico eccessivo. I problemi maggiori sono dovuti alla necessaria rappresentazione delle sequenze di nucleotidi come successione di bit 0/1, producendo un’impressionante mole di dati, impossibile da memorizzare, ordinare ed analizzare. Il DNA2DNA computing si basa sull’utilizzo di molecole di DNA per compiere operazioni su altri frammenti ignoti di DNA, senza doverli prima tradurre in bit ed ordinare in sequenza. In termini generali questo si realizza riprogrammando ed amplificando sequenze ignote in una forma ridondante, in modo da essere utilizzate nelle normali tecniche di computazione molecolare. In altre parole sequenze conosciute di DNA vanno ad interagire con quelle sconosciute producendo risultati facilmente interpretabili e che permettono di risalire alle sequenze iniziali. Le potenziali applicazioni di una riprogrammazione naturale del DNA sono innumerevoli, ma quelle sulle quali si sta maggiormente lavorando sono le seguenti:

- Sequenziamento del DNA per il riconoscimento del Genoma Umano
- Messa a punto di linee guida per una ”impronta digitale” genetica
- Riconoscimento di mutazioni di DNA per la prevenzione e la cura di malattie genetiche
- Altre operazioni di base sul DNA, già in atto con tecniche approssimative

[Torna su]