DNA computing per la risoluzione di problemi NP-completi e per la costruzione di una macchina di Turing universale

1. Introduzione L'informatica è una scienza e una tecnologia, come scienza del calcolabile il suo scopo più profondo è quello di giungere a un sistema di conoscenze oggettive, ottenute con metodo scientifico, atte a descrivere la realtà e le leggi che regolano l'occorrenza dei fenomeni; come tecnologia (l'arte del fare) il suo fine ultimo è quello di estendere i limiti del possibile. Nell'incontro con le altre scienze, matematica e informatica si assomigliano molto, entrambe sono strumenti indispensabili al loro servizio, ma è proprio nell'incontro con queste che l'informatica e la matematica ampliano loro stesse, nel rendere modellabile e calcolabile ciò che non lo era e, nell'osservarle dal loro particolare punto di vista, trarne ispirazione per nuovi modelli; ciò è evidente nel rapporto che lega la biologia all'informatica. La biologia sempre più attinge dall'informatica algoritmi e strumenti di calcolo per problemi specifici; dalla fine degli anni 70 con lo sviluppo delle tecnologie del DNA ricombinante e quindi con la pubblicazione delle prime sequenze di acidi nucleici nasce una nuova disciplina, la bioinformatica [1], che si occupa principalmente di: • Fornire modelli statistici validi per l'interpretazione dei dati provenienti da esperimenti di biologia molecolare e biochimica al fine di identificare tendenze e leggi numeriche. • Generare nuovi modelli e strumenti per l'analisi di sequenze di DNA, RNA e proteine al fine di creare un corpus di conoscenze relative alla frequenza di sequenze rilevanti, la loro evoluzione ed eventuale funzione. • Organizzare le conoscenze acquisite a livello globale su genoma 1 e proteoma 2 in basi di dati, al fine di rendere tali dati accessibili a tutti ed ottimizzare gli algoritmi di ricerca dei dati stessi per migliorarne l'accessibilità. D'altra parte informatica e biologia spesso si ritrovano a dover affrontare problemi con scenari simili [2], in riferimento alla Figura 1: (A) I sistemi biologici e computazionali spesso devono coordinare e mantenere la funzionalità senza fare affidamento su un controllore centrale. (B) Le reti sono spesso il mezzo attraverso il quale i processi si propagano, sia sul Web che nelle cellule. 1 Genoma:l'informazione ereditabile di un organismo (contenuta nel DNA o, per alcuni virus, nell' RNA). 2 Proteoma:l'insieme delle proteine di un organismo o di un sistema biologico, ovvero le proteine prodotte dal genoma. 1