Riassunto analitico
La regolazione genica è un processo complesso controllato da proteine regolatrici note come Fattori di Trascrizione. Questi elementi regolatori si legano a specifiche sequenze di DNA a monte o a valle dei geni e attivano o inibiscono la loro espressione. L'identificazione della posizione dei siti di legame nelle sequenze di DNA è un elemento chiave per svelare i meccanismi coinvolti nella trascrizione di geni. In biologia computazionale i siti di legami dei fattori di trascrizione (TFBS in inglese) sono modellati come motivi e il problema relativo alla loro identificazione è conosciuto come il Motif Discovery Problem (MDP). Negli ultimi tre decenni sono stati sviluppati diversi metodi per risolvere il MDP, ma nonostante le diverse tecniche impiegate il problema è ancora aperto. Nel presente lavoro di tesi il MDP è stato affrontato con l'uso di tecniche combinatorie, che si sono dimostrate efficaci per lo sviluppo di strumenti software ad alte prestazioni. In particolare abbiamo affrontato due problemi in stretta relazione tra di loro: l’identificazione de-novo di TFBS singoli e di TFBS composti. Per quanto riguarda il primo problema abbiamo sviluppato due nuovi metodi. Il primo è un tool per la ricerca di motivi semplici chiamato Gap Motif Finder (GMF), che esegue la ricerca dei motivi basandosi sulla esistenza di un core commune tra i siti, ammettendo un numero fissato di posizioni degenerati all’intero del core. Il metodo combina diverse tecniche già utilizzate in letteratura tra cui: algoritmi enumerativi, clustering e l’ottimizazione della posizione dei siti. Gli esperimenti effettuati su due benchmark mostrano che la performance di GMF è migliore di quella di altri 11 tool esitenti per il problema. Il secondo metodo si chiama CE3 (Customizable and Easily Extensible Ensemble), ed utilizza un approccio diverso: combina i risultati di algoritmi esistenti per l’identificazione di motivi singoli con l’obbietivo di migliorare il risultato finale. La novità di CE3 sta nel fatto che supera le limitazione di estensibilita dei metodi di ensemble esistenti, permettendo la semplice inclusione di nuovi metodi terzi per l’identificazione di motivi singoli e di nuove funzioni di apprendimento per mezzi di file XML. Inoltre, CE3 include due nuove funzioni di apprendimento per la ricerca di motivi semplici. Gli esperimenti eseguiti confrontando CE3 con 11 tool e due ensemble per MDP su tre benchmark mostrano come CE3 sia altamente competitivo con gli strumenti presenti in literatura. Nel complesso, i risultati suggeriscono che l'approccio ensemble è in grado di produrre soluzioni ragionevoli per il MDP, ma anche che esiste la necessità di ulteriori indagini per quanto riguarda la scelta della configurazione dei metodi ensemble. Tuttavia, dagli esperimenti eseguiti è stato possibile identificare alcune interessanti regolarità tra i diversi dataset che hanno suggerito un metodo generale per una efficace configurazione di CE3 in grado di garantire miglioramenti sostanziali rispetto ai tradizionali metodi per la ricerca di motivi singoli. In relazione al secondo problema, in questa tesi viene presentato CMF (Composite Motif Finder) un tool che lavora in due fasi successive: nella prima vengono identificate le posizioni dei singoli TFBS, mentre nella seconda si individuano i moduli composti formati dai singoli TFBS utilizzando principalmente tecniche combinatorie. La performance di CMF è stata valutata utilizzando tre benchmarck di diversa natura, ottenendo un miglioramento significativo dei risultati rispetto a dieci metodi concorrenti presenti in letteratura.
|
Abstract
Gene regulation is a complex process controlled by regulatory proteins known as Transcription Factors. These regulatory elements bind to specific DNA sequences in the upstream or downstream of genes activating or repressing their expression. The identification of the binding sites location in the DNA sequences is a key element to unraveling the mechanisms involved in the transcription of genes. In computational biology Transcription Factor Binding Sites (TFBSs) are modeled as motifs and the problem related to their identification is known as the Motif Discovery Problem (MDP). In the last three decades several methods have been developed to solve the MDP, but despite the different techniques employed the problem still open. In the present work the MDP is tackled by the use of combinatorial techniques, which proved effective in the development of high performing software tools. In this thesis we approached two main related problems: the novo-identification of single TFBS and the identification of composite TFBS. Concerning the first problem we developed two novel methods. The first one is a motif finder named Gapped Motif Finder (GMF). In GMF the search of putative motifs is based in the existence of a motif core allowing a fixed number of degenerated positions inside of it. Also the method combines different techniques used in the novo-motif discovery such as: an enumerative algorithm, clustering and motif site position optimization. Experiments performed with GMF showed that the proposed tool outperforms 11 other motif finders on two different benchmarks. The second method developed called CE3 (Customizable and Easily Extensible Ensemble) uses a different approach, namely the adoption of possibly many single motif discovery algorithms together with a technique for improving their single results. The novelty of CE3 over the existing ensemble methods stands in facing the extensibility limitations of existing ensembles. In CE3 the addition of virtually any third-party tool for motif discovery whose code is publicly available, and the addition of new learning functions is easily performed by mean of XML configuration files. Also two new learning functions are proposed for the research of motifs. Several experiments were performed over CE3 and its performance was compared against 11 motif finders and already available ensembles over three know benchmarks. Results show that CE3 s average performance is better than the compared tools. Overall the results suggest that the ensemble approach can produce feasible solutions for the MDP, but also that further investigation is needed concerning ensembles configuration. However, from the experiments performed it was possible the identification of some interesting regularities among different datasets suggesting a general method to proper set up CE3 able to guarantee substantial improvements over single finders in a systematic way. Concerning the second problem, we present the Composite Motif Finder (CMF) aimed to the identification of composite motifs. It is developed using combinatorial methods based on two main steps: the identification of TFBS positions and the use of them to form modules by using mainly combinatory arguments. CMF performance was assessed using three benchmark data of different nature, where CMF attained significant better average performance against ten state-of-the-art competing methods.
|
