ALGORITMI DI GRAPH QUERYING PER LA RICERCA DI SOTTOSTRUTTURE IN GRANDI RETI BIOLOGICHE

Lo studio delle grandi reti biologiche rappresenta un importantissimo ambito di ricerca della Bioinformatica. Ai nostri giorni e assolutamente consolidata l'idea che la comprensione dei meccanismi che regolano queste grandi reti possa fornire preziose informazioni sulle attivit a della cellula e delle malattie correlate. La rappresentazione di tali reti mediante gra ha di fatto favorito lo sviluppo di modelli ed algoritmi innovativi che hanno trovato applicazione in molti contesti oltre a quello Bioinformatico, primi fra tutti quello chimico e sociologico. La disponibilità di grandi database di reti biologiche rappresenta una fonte indispensabile per la ricerca e contemporaneamente costituisce una s da computazionale a causa della mole dei dati trattati. Uno dei problemi più importanti nell'ambito del network querying e rappresentato dalla ricerca di sottogra, che rappresenta l'obiettivo della presentetesi. Ad esempio, data una sottostruttura da ricercare, ad esempio un complesso proteico, si vuole scoprire se tale complesso e presente o meno all'interno di un database di reti di interazione roteina-proteina di specie di erenti. I tool per la ricerca di sottostrutture sono estremamente utili poich e consentono, ad esempio, la ricerca di complessi o moduli in specie di erenti, di pathway, di domini strutturali in proteine. Lo stato dell'arte degli algoritmi e relativi tool che a rontano simili problemi e rappresentato da tre diverse tipologie di tool. La prima (1, 2) e costituita da quei tool che operano bene con piccole reti o database di piccole reti (costituite ad esempio da poche centinaia di nodi o archi), ma che non riescono a atto a manipolare reti di dimensioni maggiori (ad esempio di qualche migliaio di nodi o archi). Poi vi sono altri tool (3, 4, 5) che pur riuscendo a manipolare reti di grandi dimensioni lo fanno con performance assolutamente inaccettabili per quanto riguarda il tempo di esecuzione. Il lavoro svolto nell'ambito di questa tesi ha permesso lo sviluppo di due nuovi algoritmi: il primo, SING, per la ricerca esatta di sottogra ; il secondo, SIGMA, per la ricerca inesatta. Per tutti gli aspetti a rontati saranno presentate speci che sezioni sperimentali mediante le quali saranno messe in videnze le particolari applicazioni biologiche. Sia per la ricerca esatta sia per quella inesatta sono state sviluppate speci che sezioni sperimentali atte a mettere in evidenza possibili applicazioni biologiche. Nel primo caso sono stati e ettuati due esperimenti sulle reti biologiche: nel primo sono stati ricercati i Motif, de niti secondo quanto descritto in (6), all'interno delle rete di regolazione della trascrizione di E. Coli 7.4; nel secondo 7.5 sono stati ricercati i complessi proteici di S. Cereavice all'interno della rete di interazione roteina-proteina di H. Sapiens. In entrambi gli esperimenti si e potuto dimostrare che globalmente le performance di SING risultano essere migliori se paragonate agli altri tool presi in considerazione. Nel secondo caso e stata realizzata una ricerca inesatta dei complessi di S. Cereavice all'interno di un database di complessi di H. Sapiens, riuscendo ad identi care correttamente i complessi delle due specie che coincidono nonostante lievi di erenze.