Mining of Significant Patterns: Theory and Practice

I recenti progressi tecnologici permettono la raccolta e la memorizzazione di enormi quantita di dati in molte aree diverse. Il e il processo di estrazione di informazione nuova, interessante ed utile. Negli ultimi anni un cospicuo numero di soluzioni sono state sviluppate per l'analisi di grandi moli di dati, ma il processo di valutazione della significativita dei pattern estratti e di validazione delle previsioni basate su questi pattern sta diventando uno dei principali nell'ambito delle applicazioni che elaborano enormi quantita di dati. Questa tesi si focalizza sullo sviluppo di tecniche rigorose ed efficienti per l'estrazione di pattern significativi in tre diversi scenari rilevanti. Il primo scenario considerato e l'estrazione di pattern frequenti, chiamati , da dataset transazionali. Inizialmente vengono studiate due primitive molto utilizzate per questo problema: l'estrazione dei itemset chiusi piu frequenti, un problema proposto recentemente come alternativa all'estrazione degli itemset frequenti che fornisce un maggior controllo sulla taglia dell'output, che e una delle principali difficolta per il problema tradizionale; l'estrazione dei itemset piu frequenti tramite . La nozione di itemset chiusi piu frequenti fornisce un primo tentativo di migliorare l'efficacia del framework tradizionale, legando la significativita ad un ordinamento basato sulla frequenza invece che ad un semplice soglia di frequenza. Per entrambe queste primitive vengono sviluppati nuovi algoritmi e viene fornita evidenza sperimentale della loro efficacia. Successivamente viene studiato il problema dell'identificazione di una soglia di supporto significativa tale che gli itemset che risultano frequenti rispetto a tale soglia possono essere contrassegnati come significativi con un basso (FDR), che e definito come il rapporto atteso tra il numero di scoperte erronee e il numero totale di pattern prodotti in output. Una caratteristica cruciale che distingue il nostro approccio dalla maggior parte dei lavori precedenti e che il nostro framework considera l'intero dataset per valutare la significativita di un pattern. Vengono inoltre forniti i risultati dell'analisi sperimentale che mostrano l'efficacia del nostro approccio. Il secondo scenario che consideriamo e l'estrazione di pattern, chiamati , che si ripetono frequentemente, eventualmente con errori, in sequenze biologiche. Questo problema ha attratto molto interesse negli ultimi anni, dato che la similarita a livello di sequenza e spesso una condizione necessaria per avere correlazione a livello funzionale a livello di DNA, RNA o proteine. Per questo problema viene introdotta la nozione di , una misura semplice e flessibile per limitare il numero di errori, rappresentati tramite , in un motif. Viene sviluppato un nuovo algoritmo per l'estrazione di motif densi massimali da una sequenza, e viene fornita evidenza sperimentale della significativita biologica dei motivi che l'algoritmo estra. Inoltre, i motivi estratti dal nostro algoritmo vengono confrontati con quelli trovati da un altro algoritmo proposto recentemente, mostrando che il nostro algoritmo identifica motif che risultano piu significativi rispetto allo -score, una misura di significativita molto utilizzata. L'ultimo scenario che viene considerato e l'estrazione di pattern significativi da grandi reti di interazione fra geni e proteine, un problema di crescente interesse vista la sua importanza negli studi sul cancro. Per questo scenario viene definito il problema dell'identificazione di sottoreti . Viene introdotto il primo framework computazionale, al meglio della nostra conoscenza, che fornisce una strategia computazionale efficiente per l'identificazione di sottoreti mutate in maniera e vengono sviluppati due algoritmi per l'identificazione di tali sottoreti. Tali algoritmi sono valutati utilizzando una grande rete di interazione tra proteine e utilizzando dati di mutazione ottenuti da recenti studi su due tipi di cancro. I risultati di questa valutazione mostrano che i nostri algoritmi identificano correttamente le sottoreti che sono implicate nell'insorgenza del cancro.