Algoritmi bio-molecolari per problemi NP completi

Data inizio
21 febbraio 2003
Durata (mesi) 
36
Dipartimenti
Informatica
Responsabili (o referenti locali)
Manca Vincenzo
Parole chiave
DNA computing, Molecular computing, Problemi NP completi, Modelli di calcolo non convenzionali, Bioinformatica, Sistemi complessi

L'unita' si occupera' di:
  1. dirigere e orientare le attivita' di laboratorio biotecnologico per la realizzazione dei protocolli e delle metodiche di DNA Computing per un algoritmo basato su [Manca, Di Gregorio, Lizzari, Vallini, Zandron, 2001] rispetto a prefissate istanze di SAT. Tali protocolli dovrebbero avere un livello di analisi tale da farne dei 'pacchetti' autonomi da potere adattare e combinare per la soluzione di un'ampia classe di algoritmi combinatori. L'attivita' sperimentale fino al maggio 2002 sara' presentata all'8th Internationa Meeting on DNA Based Computers' di Sapporo, in Giappone;
  2. elaborare strumenti di analisi per valutare i parametri computazionali piu' significativi delle istanze di SAT (dimensione dello spazio delle soluzioni, numero di separazioni) e per analizzare i loro rapporti al variare dei metodi risolutivi di SAT;
  3. determinare operazioni e relative realizzazioni biologiche per i passi di separazione. Studiarne quindi l'affidabilita' e l'efficienza;
  4. individuare criteri informatici e matematici di pre-analisi di istanze SAT, in modo da determinare la complessita' "reale" di un'istanza, dal punto di vista del DNA Computing. Infatti, spesso il numero di variabili e di equazioni e' un parametro fittizio, nel senso che con semplici trasformazioni si passa da un'istanza con molte variabili e molte equazioni, ad una equivalente in cui tali numeri sono molto piu' bassi. Inoltre, spesso un'istanza di grande dimensioni si decompone in istanze piu' piccole ciascuna delle quali si risolve facilmente. Infine, in altri casi ancora, lo spazio delle soluzioni e' tale che solo un suo sottospazio e' significativo ai fini della ricerca della soluzione;
  5. inquadrare gli algoritmi DNA nella prospettiva piu' ampia di 'problem solvers' da potere implementare con altre strutture computazionali di ispirazione biologica, quali i P-systems (sviluppati dall'unita' di Milano) o altri sistemi basati su membrane e su loro modelli di realizzazione fisica;
  6. analizzare la natura dinamica dei sistemi indicati nel punto precedente da un punto di vista di 'dinamica simbolica'. Cercando di modellare con strumenti discreti non solo la risolubilita' combinatoria, ma anche caratteristiche dinamiche legate alla stabilita', all'interattivita', all'adattabilita' e alla riproducibilita';
  7. cercare di legare le analisi svolte nei due punti precedenti con i notevoli risultati sulla distribuzione statistica delle soluzioni di SAT e sulla formalizzazione di dinamiche cellulari, attraverso le reti booleane nel senso di Derrida e Kauffman.

Enti finanziatori:

Ministero dell'Istruzione dell'Università e della Ricerca
Finanziamento: assegnato e gestito da un ente esterno all'ateneo
Programma: FIRB

Partecipanti al progetto

Cinzia Giagulli
Vincenzo Manca
Professore ordinario

Attività

Strutture