Ricerca | Progetti

ALGORITMI DI GRAPH MATCHING PER LA BIOINFORMATICA E LA SOCIAL NETWORK ANALYSIS

L'obiettivo della ricerca sarà di definire, implementare e sperimentare algoritmi di graph matching che siano specificamente progettati per le caratteristiche dei grafi incontrati nei due campi di applicazione menzionati, risultando quindi più efficienti di algoritmi generali come quelli presenti in letteratura. Gli algoritmi proposti saranno inoltre validati attraverso una analisi sperimentale comparativa, che includerà il confronto con i più recenti metodi presenti nella letteratura scientifica.Il progetto di ricerca è articolato nelle seguenti fasi:1) Studio dello stato dell'arte nell'ambito del graph matching, con specifico riferimento alle tecniche adottate per gestire grafi di grandi dimensioni e per il matching inesatto.2) Individuazione di alcune problematiche nei settori di bioinformatica e social network analysis da usare come testbed per la validazione degli algoritmi proposti, e costruzione di un database (da rendere pubblicamente disponibile alla comunità di ricerca) di grafi derivati da questi ambiti applicativi.4) Progettazione e realizzazione di algoritmi di graph matching specifici per i problemi individuati, attraverso l'introduzione di strutture dati apposite e di meccanismi euristici per la riduzione (nel caso medio) del tempo di elaborazione e dell'occupazione di memoria.3) Valutazione sperimentale delle prestazioni degli algoritmi realizzati, usando il database di grafi precedentemente costruito, e confrontando le prestazioni con i più recenti algoritmi di graph matching presenti in letteratura. La valutazione verrà fatta analizzando le prestazioni in termini di tempo e spazio occupato al variare di diverse caratteristiche dei grafi, in modo da poter delineare sotto quali condizioni ciascun determinato algoritmo può risultare vantaggioso.