Research | Projects

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

L'obiettivo della ricerca sarà di continuare le attività avviate nello scorso anno di definizione, implementazione e sperimentazione relative ad 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.3) 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.4) 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.Le attività del progetto FARB 2013 di cui la presente proposta è la continuazione si sono concentrate sui punti precedenti con particolare riferimento alla bioinformatica. Il progetto corrente, oltre a estendere ulteriormente tali attività, cercherà di dare un maggiore spazio alle tematiche di social network analysis.Inoltre si cercherà di consolidare e sviluppare ulteriormente le relazioni internazionali costruite nello scorso anno, in particolare la collaborazione con il prof. Xiaoyi Jiang dell'Università di Münster, che ha portato all'organizzazione congiunta di un contest internazionale sul graph matching per database biologici, e alla proposta di uno special issue della prestigiosa rivista IEEE Transactions on Computational Biology and Bioinformatics, che è stata accettata dall'editorial board ed è prevista per la pubblicazione nel 2015.