Advances in next generation sequencing (NGS), also known as high-throughput sequencing, ubiquitize DNA sequencing as a flexible tool for genome exploration. NGS has opened the possibility of a comprehensive characterization of the genomic and epigenomic landscapes, giving answers to fundamental questions for biological and clinical research, e.g., how DNA-protein interactions and chromatin structure affect gene activity, how cancer develops, how much complex diseases such as diabetes or cancer depend on personal (epi)genomic traits. This is opening the road to personalized and precision medicine. A distinguished aspect of NGS-based experiments is the large amount of data they produce. The generated data are broadly applicable and facilitate various functional analysis, including studies about DNA-protein interaction or histone modification (using Chromatin immunoprecipitation followed by massively parallel DNA sequencing (ChIP–seq)), transcriptional regulation (using RNA-seq), long range chromatin interactions explained by \textit{de novo} spatial structure of genome (using Hi-C6). Recent studies combine these studies into larger assays for in-depth interpretations of sequencing data. Yet such interpretations, and \textit{making sense} of data, demand complex computation and large scale data retrieval systems. The present dissertation has focused on \textit{sense-making}, e.g., discovering how heterogeneous DNA regions concur to determine particular biological processes or phenotypes. Towards such discovery, characteristic operations to be performed on region data regard identifying co-occurrences of regions, from different biological tests and/or of distinct semantic types, possibly within a certain distance from each others and/or from DNA regions with known structural or functional properties. The manuscript explains Di4 (1D interval incremental inverted index) and its predecessor Di3 (1D interval inverted index). Di4 and Di3 are single-dimension (1D) multi-resolution indexing frameworks, designed to be comprehensive, generic, extensible, and scalable back-end data structures for information retrieval on NGS interval-based data. Di4 and Di3 are defined at data access layer, agnostic to data, business logic, and presentation layers; this design makes them adaptable to any underlying persistence technology based on key-value pairs, spanning from classical B+tree to LevelDB and Apache HBase, and it makes them suitable for different business logic and presentation layer scenarios. Benchmarking Di4 and Di3 on real and simulated datasets and a comparison with common tools in bioinformatics realm, demonstrate the effectiveness of Di4 and Di3 as a back-end for general purpose genomic region manipulation. The applicability of Di4 and Di3 to different business logic and presentation scenarios, and extensibility to application-specific functions, is assessed in comparative evaluation of ChIP-seq samples. The ChIP-seq technology identifies protein-DNA interactions using enriched regions on DNA when the significance measure (p-value) is below a stringency threshold. Replicated samples are expected to have a degree of repeated evidence, which can locally lower the minimum significance required to accept an enriched region. The present dissertation discusses a method for the joint analysis of ChIP-seq replicates, which confirms overlapping enriched regions if their comparative evaluation complies a set of user-defined thresholds. The method is implemented using Di3 to demonstrate the extensibility of the frameworks. Additionally, Di3 is used as back-end data structure to implement common ChIP-seq data assessment methods, such as functional analysis, correlation assessment, nearest feature distance distribution, chromosome-wide statistics, and genome browser.

Grazie agli sviluppi nel sequenziamento di nuova generazione (NGS), anche noto come High-Throughput Sequencing, il sequenziamento del DNA si è diffuso ovunque come strumento flessibile per l’esplorazione del genoma. Le tecniche di NGS hanno reso possibile una caratterizzazione globale del panorama genomico ed epigenomico, rispondendo a domande fondamentali nell’ambito della ricerca biologica e chimica quali l’effetto sull’attività genica delle interazioni tra proteine e DNA e della struttura della cromatina, le modalità di sviluppo di diverse forme di cancro e la dipendenza di malattie complesse come diabete dai tratti (epi)genomici dell’individuo. A loro volta questi sviluppi stanno aprendo la strada alla cosiddetta medicina di precisione, o personalizzata. Una caratteristica peculiare degli esperimenti basati sull’NGS è la grande quantità di dati da essi prodotti. Questi dati sono applicabili in diversi contesti e facilitano diversi tipi di analisi funzionali, ad esempio gli studi sull’interazione DNA-proteine o le modificazioni degli istoni (usando l’immunoprecipitazione della cromatina seguita dal sequenziamento massivo in parallelo del DNA – il ChIP-Seq), la regolazione della trascrizione (RNA-Seq) oppure l’interazione a lungo raggio della cromatina spiegata attraverso una struttura spaziale del genoma de novo (usando Hi-C6). Lavori più recenti hanno combinato queste ricerche in studi più estesi sull’interpretazione approfondita dei dati di sequenziamento; tuttavia sia queste interpretazioni che l’attività stessa di estrapolare un significato dai dati richiedono calcoli onerosi e sistemi di estrazione dati di portata superiore. Questa discussione si concentra sul sense-making, ovvero indagare come regioni eterogenee del DNA concorrano nel determinare particolari processi biologici o fenotipi. Al fine di effettuare tali indagini, certe operazioni tipiche devono essere effettuate su dati di regioni provenienti da diversi test biologici e/o diversi tipi semantici, al fine di identificare eventuali co-occorrenze e, possibilmente, a quale distanza ciascuna di esse si manifesti rispetto alle altre e/o ad altre regioni del DNA la cui struttura o le cui proprietà funzionali siano già note. Il manoscritto descrive Di4 (un indice inverso incrementale per intervalli monodimensionali) ed il suo predecessore non incrementale Di3. Di4 e Di3 sono framework di indicizzazione monodimensionali (1D) multi-risoluzione, pensati per essere strutture dati generiche, estendibili, globali e scalabili per effettuare ricerca e recupero di informazioni su dati NGS di natura intervallare. Di4 e Di3 sono definiti a livello di accesso dati e sono agnostici al dato, ai processi di business ed al livello di presentazione; questa definizione permette loro di essere adattabili a qualsiasi pre-esistente tecnologia che sia basata su coppie chiave-valore, a partire dal classico B-tree fino a LevelDB ed a Apache HBase: questo li rende adatti per diversi scenari di business e livelli di presentazione. Diversi studi di benchmarking su Di4 e Di3 effettuati sia su dataset reali che sintetici ed un confronto con strumenti già esistenti nel campo della bioinformatica hanno mostrato l’efficacia di questi indici come back-end per la manipolazione a qualunque fine delle regioni genomiche. Sia l’applicabilità di Di4 e Di3 a diversi scenari di presentazione di business che la loro estendibilità a funzioni specifiche per alcune applicazioni sono state valutate tramite indagini comparative di campioni di ChIP-Seq. La tecnologia ChIP-Seq identifica le interazioni proteina-DNA usando regioni arricchite sul DNA con un valore di significatività (pvalue) al di sotto di una certa soglia critica. Ci si aspetta che campioni duplicati abbiano un certo grado di replicazione nei risultati, cosa che può ridurre a livello locale la minima significatività richiesta per accettare una regione arricchita. Questa discussione verte su di un metodo per l’analisi incrociata dei duplicati di ChIP-Seq la quale valida regioni arricchite sovrapposte se la loro valutazione comparative sottostà a certi vincoli imposti dall’utente. Il metodo è stato implementato usando Di3 al fine di dimostrare l’estendibilità dei framework. In aggiunta, Di3 viene utilizzato come struttura dati di back-end per implementare altri metodi più comuni di valutazione del dato ChIP-Seq, quali analisi funzionali, valutazioni di correlazione, distribuzione della distanza delle feature più vicine, statistiche a livello di cromosoma e visualizzatori di genoma.

Efficient data structures for cross-samples inferences on genomic data

JALILI, VAHID

Abstract

Advances in next generation sequencing (NGS), also known as high-throughput sequencing, ubiquitize DNA sequencing as a flexible tool for genome exploration. NGS has opened the possibility of a comprehensive characterization of the genomic and epigenomic landscapes, giving answers to fundamental questions for biological and clinical research, e.g., how DNA-protein interactions and chromatin structure affect gene activity, how cancer develops, how much complex diseases such as diabetes or cancer depend on personal (epi)genomic traits. This is opening the road to personalized and precision medicine. A distinguished aspect of NGS-based experiments is the large amount of data they produce. The generated data are broadly applicable and facilitate various functional analysis, including studies about DNA-protein interaction or histone modification (using Chromatin immunoprecipitation followed by massively parallel DNA sequencing (ChIP–seq)), transcriptional regulation (using RNA-seq), long range chromatin interactions explained by \textit{de novo} spatial structure of genome (using Hi-C6). Recent studies combine these studies into larger assays for in-depth interpretations of sequencing data. Yet such interpretations, and \textit{making sense} of data, demand complex computation and large scale data retrieval systems. The present dissertation has focused on \textit{sense-making}, e.g., discovering how heterogeneous DNA regions concur to determine particular biological processes or phenotypes. Towards such discovery, characteristic operations to be performed on region data regard identifying co-occurrences of regions, from different biological tests and/or of distinct semantic types, possibly within a certain distance from each others and/or from DNA regions with known structural or functional properties. The manuscript explains Di4 (1D interval incremental inverted index) and its predecessor Di3 (1D interval inverted index). Di4 and Di3 are single-dimension (1D) multi-resolution indexing frameworks, designed to be comprehensive, generic, extensible, and scalable back-end data structures for information retrieval on NGS interval-based data. Di4 and Di3 are defined at data access layer, agnostic to data, business logic, and presentation layers; this design makes them adaptable to any underlying persistence technology based on key-value pairs, spanning from classical B+tree to LevelDB and Apache HBase, and it makes them suitable for different business logic and presentation layer scenarios. Benchmarking Di4 and Di3 on real and simulated datasets and a comparison with common tools in bioinformatics realm, demonstrate the effectiveness of Di4 and Di3 as a back-end for general purpose genomic region manipulation. The applicability of Di4 and Di3 to different business logic and presentation scenarios, and extensibility to application-specific functions, is assessed in comparative evaluation of ChIP-seq samples. The ChIP-seq technology identifies protein-DNA interactions using enriched regions on DNA when the significance measure (p-value) is below a stringency threshold. Replicated samples are expected to have a degree of repeated evidence, which can locally lower the minimum significance required to accept an enriched region. The present dissertation discusses a method for the joint analysis of ChIP-seq replicates, which confirms overlapping enriched regions if their comparative evaluation complies a set of user-defined thresholds. The method is implemented using Di3 to demonstrate the extensibility of the frameworks. Additionally, Di3 is used as back-end data structure to implement common ChIP-seq data assessment methods, such as functional analysis, correlation assessment, nearest feature distance distribution, chromosome-wide statistics, and genome browser.
BONARINI, ANDREA
CERI, STEFANO
MASSEROLI, MARCO
29-apr-2016
Grazie agli sviluppi nel sequenziamento di nuova generazione (NGS), anche noto come High-Throughput Sequencing, il sequenziamento del DNA si è diffuso ovunque come strumento flessibile per l’esplorazione del genoma. Le tecniche di NGS hanno reso possibile una caratterizzazione globale del panorama genomico ed epigenomico, rispondendo a domande fondamentali nell’ambito della ricerca biologica e chimica quali l’effetto sull’attività genica delle interazioni tra proteine e DNA e della struttura della cromatina, le modalità di sviluppo di diverse forme di cancro e la dipendenza di malattie complesse come diabete dai tratti (epi)genomici dell’individuo. A loro volta questi sviluppi stanno aprendo la strada alla cosiddetta medicina di precisione, o personalizzata. Una caratteristica peculiare degli esperimenti basati sull’NGS è la grande quantità di dati da essi prodotti. Questi dati sono applicabili in diversi contesti e facilitano diversi tipi di analisi funzionali, ad esempio gli studi sull’interazione DNA-proteine o le modificazioni degli istoni (usando l’immunoprecipitazione della cromatina seguita dal sequenziamento massivo in parallelo del DNA – il ChIP-Seq), la regolazione della trascrizione (RNA-Seq) oppure l’interazione a lungo raggio della cromatina spiegata attraverso una struttura spaziale del genoma de novo (usando Hi-C6). Lavori più recenti hanno combinato queste ricerche in studi più estesi sull’interpretazione approfondita dei dati di sequenziamento; tuttavia sia queste interpretazioni che l’attività stessa di estrapolare un significato dai dati richiedono calcoli onerosi e sistemi di estrazione dati di portata superiore. Questa discussione si concentra sul sense-making, ovvero indagare come regioni eterogenee del DNA concorrano nel determinare particolari processi biologici o fenotipi. Al fine di effettuare tali indagini, certe operazioni tipiche devono essere effettuate su dati di regioni provenienti da diversi test biologici e/o diversi tipi semantici, al fine di identificare eventuali co-occorrenze e, possibilmente, a quale distanza ciascuna di esse si manifesti rispetto alle altre e/o ad altre regioni del DNA la cui struttura o le cui proprietà funzionali siano già note. Il manoscritto descrive Di4 (un indice inverso incrementale per intervalli monodimensionali) ed il suo predecessore non incrementale Di3. Di4 e Di3 sono framework di indicizzazione monodimensionali (1D) multi-risoluzione, pensati per essere strutture dati generiche, estendibili, globali e scalabili per effettuare ricerca e recupero di informazioni su dati NGS di natura intervallare. Di4 e Di3 sono definiti a livello di accesso dati e sono agnostici al dato, ai processi di business ed al livello di presentazione; questa definizione permette loro di essere adattabili a qualsiasi pre-esistente tecnologia che sia basata su coppie chiave-valore, a partire dal classico B-tree fino a LevelDB ed a Apache HBase: questo li rende adatti per diversi scenari di business e livelli di presentazione. Diversi studi di benchmarking su Di4 e Di3 effettuati sia su dataset reali che sintetici ed un confronto con strumenti già esistenti nel campo della bioinformatica hanno mostrato l’efficacia di questi indici come back-end per la manipolazione a qualunque fine delle regioni genomiche. Sia l’applicabilità di Di4 e Di3 a diversi scenari di presentazione di business che la loro estendibilità a funzioni specifiche per alcune applicazioni sono state valutate tramite indagini comparative di campioni di ChIP-Seq. La tecnologia ChIP-Seq identifica le interazioni proteina-DNA usando regioni arricchite sul DNA con un valore di significatività (pvalue) al di sotto di una certa soglia critica. Ci si aspetta che campioni duplicati abbiano un certo grado di replicazione nei risultati, cosa che può ridurre a livello locale la minima significatività richiesta per accettare una regione arricchita. Questa discussione verte su di un metodo per l’analisi incrociata dei duplicati di ChIP-Seq la quale valida regioni arricchite sovrapposte se la loro valutazione comparative sottostà a certi vincoli imposti dall’utente. Il metodo è stato implementato usando Di3 al fine di dimostrare l’estendibilità dei framework. In aggiunta, Di3 viene utilizzato come struttura dati di back-end per implementare altri metodi più comuni di valutazione del dato ChIP-Seq, quali analisi funzionali, valutazioni di correlazione, distribuzione della distanza delle feature più vicine, statistiche a livello di cromosoma e visualizzatori di genoma.
Tesi di dottorato
File allegati
File Dimensione Formato  
JaliliThesis.pdf

accessibile in internet per tutti

Descrizione: Vahid Jalili Thesis Text
Dimensione 13.66 MB
Formato Adobe PDF
13.66 MB Adobe PDF Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/120263