Mining of Significant Patterns: Theory and Practice

Recent advances in technology allow for the collection and storage of vast amounts of data in many different areas. Data mining is the process of discovering new and useful information. Many techniques have been developed in recent years for the analysis of large datasets, but the task of assessing the significance of discovered patterns and the validity of forecast based on these discoveries is becoming a major challenge in data intensive applications. The objective of this thesis is the development of rigorous and efficient techniques for mining significant patterns in three different and important scenarios. The first scenario is the mining of frequent itemsets from transactional datasets. For this problem we first study two primitives: the extraction of top- frequent closed itemsets, a recently proposed alternative to the extraction of frequent itemsets, that provides a better control on the output size, which is one of the main challenges of the traditional problem; and the use of sampling for the extraction of top- frequent items/itemsets. The notion of top- frequent patterns provides a first attempt to enhance the effectiveness of the traditional framework by relating the significance to a frequency based ranking rather than to a mere frequency threshold. For both primitives we develop new algorithms and provide experimental evidence of their effectiveness. We then address the problem of identifying a meaningful frequency threshold such that that the itemsets that are frequent w.r.t. that threshold can be flagged as statistically significant with a small (FDR), which is defined as the expected ratio of false discoveries among all discoveries. A crucial feature of our approach is that, unlike most previous work, it takes into account the entire dataset rather than individual discoveries. Experimental results are reported which show the effectiveness of our approach. The second scenario is the mining of patterns, called , that repeat frequently, possibly with some errors, in biological sequences. This problem has attracted wide interest in recent years, since sequence similarity is often a necessary condition for functional correlation. We introduce , a simple and flexible measure for bounding the number of errors, modeled thorugh , in a motif. We design a new algorithm to extract maximal dense motifs from a sequence, and provide experimental evidence of the biological significance of the motifs that the algorithm returns. Moreover, we compare the motifs extracted by our algorithm with the ones found by a recently proposed algorithm, showing that our algorithm can identify motifs that are more significant according to -score, a widely employed measure of significance. The last problem we consider is the mining of significant patterns from large-scale gene and protein interaction networks, a problem of increasing interest since its importance in cancer studies. For this scenario we define the problem of identifying in large scale gene and protein interaction networks. We introduce a computational framework that is the first, to our knowledge, to demonstrate a computationally efficient strategy for identification of mutated subnetworks, and design two algorithms to efficiently extract the significantly mutated pathways. Moreover we test these algorithms on a large human protein-protein interaction network using mutation data from recent studies on two different type of cancers. The results of our tests show that our methods correctly identifies the pathways that are implicated in cancer.

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.