Motif discovery in the next-generation sequencing era

Motivation Transcription Factor (TF) datasets still present unique challenges from a computational point of view, especially regarding the need of indexing hundreds of millions of sequences. Existing methods and tools have strong limitations from a computational point of view. Furthermore, most of them just provide a list of regions with an associated score for each pattern found, and nothing more. Results: in this work, we present two main methods: the first, which is based on De Bruijn graphs, aims to index and count approximate substrings occurrences contained in sequences; the second one permit, using a Gaussian Mixture Model, to infer the rules according to which these occurrences organize themselves on the DNA and, therefore, the interactions between different TF. We used the first algorithm to discover well-known pattern on several datasets, comparing the results to those already computed over the same datasets and to validated results for the same experiment. We implemented a tool that can easily run on a desktop computer, with very low memory usage. Its performances turned out to be very good and it also has proved to be biologically accurate. Using adjacencies De Bruijn graphs we can balance memory usage, using a contained substring length, while searching for patterns up to double the size. In the second part, we applied a Gaussian Mixture State Model to several datasets. We successfully partitioned human promotorial regions according to the interactions of two - or more - TF. Then we computed some correlation measures that confirmed our partitions. We then applied this method to other datasets, where we expect to find an enrichment of the pattern related to the experiment's target. This validation proved to be successful, correctly identifying a particular case.

Motivazioni: i dataset relativi a fattori di trascrizione - Transcription Factors (TFs) - presentano tutt'ora sfide uniche dal punto di vista computazionale, come la necessità di indicizzare centinaia di milioni di sequenze. I metodi e gli strumenti esistenti sono fortemente limitati dal punto di vista computazionale. Inoltre, la maggior parte di questi fornisce una lista di regioni con un punteggio associato per ogni pattern individuato, e nessun'altra informazione. Risultati: in questo lavoro presenteremo due metodi: il primo, basato su grafi di De Bruijn, per indicizzare le sottostringhe contenute nelle sequenze e il secondo basato su un modello a misture di gaussiane, per dedurre le regole secondo cui questi pattern si organizzano sul DNA e, di conseguenza, le interazioni tra i diversi TF. Abbiamo usato il primo algoritmo per individuare pattern conosciuti su diversi dataset. Abbiamo comparato i risultati con altri ottenuti dagli stessi dati e su alcuni validati per gli stessi esperimenti. Abbiamo implementato un tool che può essere utilizzato su un computer desktop senza difficoltà, grazie ad un utilizzo di memoria molto contenuto. Questo ha ottime performance e si è dimostrato biologicamente accurato. Usando i grafi di De Bruijn delle adiacenze siamo in grado di bilanciare da un lato l'utilizzo di memoria e dall'altro, grazie ad una dimensione delle sottostringhe contenuta, la ricerca di pattern di lunghezza fino al doppio di quella scelta per il grafo. Nella seconda parte, presenteremo i risultati ottenuti applicando il modello gaussiano su diversi dataset. Abbiamo partizionato le regioni promotoriali umane, in base all'interazione di due - o più - TF, con successo. Abbiamo poi confermato le partizioni usando diverse misure di correlazione. Abbiamo infine applicato questo metodo ad altri dataset dove ci si aspettava un arricchimento dei pattern legati all'obiettivo dell'esperimento. Questa validazione si è dimostrata corretta, permettendoci di identificare un caso particolare.