Metodi Formali e Algoritmici per la Bioinformatica su Scala Genomica

Questo progetto di ricerca è inquadrabile nelle aree di Algoritmi e Strutture Dati e Data Mining, e ha importanti applicazioni alle Scienze della Vita, in particolare alla Genomica ed alla Proteomica'. Il suo principale oggetto di studi sono gli algoritmi per la scoperta di pattern e regole associative in sequenze biologiche. Sebbene molti di questi problemi siano ormai classici, le soluzioni algoritmiche note non sono più adeguate in quanto negli ultimi anni abbiamo assistito ad un cambio di paradigma nelle Scienze della Vita. Le nuove tecnologie sperimentali, ad esempio Chip-Chip e Chip-Seq, producono grandissime quantità di dati. L'efficienza degli algoritmi, sia in tempo che in spazio, è quindi fondamentale per l'analisi di questi dati. A grandi linee, i principali obiettivi di questa ricerca sono: (1) fondazionali: individuare, formalizzare e studiare primitive computazionali necessarie per l'analisi delle bio-sequenze al fine di ottenere una maggiore comprensione dei principi fondamentali del pattern-discovery su scala genomica; (2) di sviluppo e ingegnerizzazione: sviluppare in maniera coordinata algoritmi efficienti per le primitive identificate, possibilmente arrivando alla realizzazione di software. Malgrado l'informatica abbia contribuito in maniera sostanziale alla rivoluzione post-genomica, le fondamenta matematiche del pattern discovery in biosequenze non sono ancora solide. Una più precisa identificazione di queste fondamenta costituisce una delle sfide maggiori che la scienza dell'informazione deve affrontare nel prossimo futuro. I progressi in questa direzione avrebbero un impatto rilevante nella pratica: lo sviluppo di metodi computazionali che possano trattare efficientemente le grandi quantità di dati prodotti dalle moderne tecnologie. Uno studio recente di ricercatori in questo progetto ha indicato che le metodologie basate sulla Compressione Dati possono essere parte delle fondamenta matematiche del pattern discovery. I principi alla base di queste metodologie sono che sia possibile manipolare ed estrarre informazioni dai dati mantenuti in formato compatto, ad esempio con indici compressi o viste gerarchiche. Lo scopo di questo progetto è di portare queste osservazioni fino alla loro piena maturità sviluppando questo nucleo iniziale di metodologie e teorie. Di conseguenza, questo progetto è incentrato sullo studio delle leggi fondamentali della scienza dell'informazione che possano supportare metodi computazionali per le scienze della vita, e non si limita ad uno studio di metodi computazionali per un insieme specifico di problemi biologici. Più in dettaglio, gli obiettivi specifici includono lo studio di modelli, algoritmi e programmi per la scoperta di pattern nei seguenti contesti: regolazione dell'espressione genica, sequenze promotrici e terminatorie, predizione delle regioni di codifica, post trascrizione, accoppiamento e iniziazione della sintesi proteica, ripetizioni invertite e tandem, allineamenti di sequenze multiple, ricerca di omologie, ricerca di dyad e altre associazioni. Gli strumenti principali che caratterizzano fortemente i partecipanti di questo progetto sono, per citarne alcuni, Compressori Dati, Tecniche di Indicizzazione, Algoritmi di Validazione Statistica di Clustering. Risultati recenti ottenuti da ricercatori del progetto indicano che questi validi strumenti possono giocare un ruolo cruciale per l’analisi di dati biologici su scala genomica. L’unità di ricerca comincerà su basi estremamente solide; infatti, le tecniche sviluppate dai ricercatori partecipanti hanno portato negli ultimi cinque anni ad un numero sostanziale di pubblicazioni sulle migliori riviste di Computer Science, come Journal of the ACM, BMC Bioinformatics, Genomics, BioInformatics. Inoltre, alcune delle ricerche condotte da componenti del progetto hanno portato allo sviluppo di diversi servizi web e sistemi software orientati alla Bioinformatica. Per esempi