ArchivIA - Archivio istituzionale dell'Universita' di Catania >
Tesi >
Tesi di dottorato >
Area 06 - Scienze mediche >
Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/10761/1012
|
Data: | 20-feb-2012 |
Autori: | Di Natale, Raffaele |
Titolo: | Algoritmi di graph querying per la ricerca di sottostrutture in grandi reti biologiche |
Abstract: | 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à 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 rappre-
sentato dalla ricerca di sottogra, che rappresenta l'obiettivo della presente
tesi. 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 proteina-proteina di specie di erenti.
I tool per la ricerca di sottostrutture sono estremamente utili poich e con-
sentono, 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.
I lavoro svolto nell'ambito di questa tesi ha permesso lo sviluppo di due nuo-
vi 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 speri-
mentali mediante le quali saranno messe in evidenze le particolari applica-
zioni biologiche.
Sia per la ricerca esatta sia per quella inesatta sono state sviluppate spe-
ci 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. Cerea-
vice all'interno della rete di interazione proteina-proteina di H. Sapiens. In
entrambi gli esperimenti si e potuto dimostrare che globalmente le perfor-
mance 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. |
In | Area 06 - Scienze mediche
|
Full text:
File |
Descrizione |
Dimensioni | Formato | Consultabilità |
DNTRFL72T13I754Z-Tesi-Dottorato-Raffaele-Di-Natale-2011.pdf | ALGORITMI DI GRAPH QUERYING PER LA RICERCA DI SOTTOSTRUTTURE IN GRANDI RETI BIOLOGICHE | 3,01 MB | Adobe PDF | Visualizza/apri
|
|
Tutti i documenti archiviati in ArchivIA sono protetti da copyright. Tutti i diritti riservati.
|