A new technology for reading the DNA, called Next Generation Sequencing (NGS), is changing biological research and medical practice, thanks to the low-cost availability of millions of whole genome sequences of a variety of species, and most important of humans. So far, the bio-informatics research community has been mostly challenged by primary and secondary analysis (data alignment and feature calling) but the emerging problem today is the so-called tertiary analysis, concerned with multi-sample processing, annotation and filtering of variants, and genome browser-driven exploratory analysis. The amount of data for tertiary analysis requires Big Data man- agement. The GenData 2020 project is focused on this problem. The project developed new abstractions for querying heterogeneous genomic datasets, centered on the notion of Genomic Data Model (GDM) and Genometric Query Language (GQL). GDM describes genomic datasets produced by NGS experments, and includes both regions and metadata associated to DNA experiments; GMQL is a high-level, algebraic language which operates upon GDM and provides both conventional and domain-specific operations. In this thesis we developed a new implementation of GMQL. We used SciDB, a data management system for scientific applications developed by Paradigm4, a startup company located in Cambridge. SciDB provides abstraction from storage management, data distribution, and optimized parallel execution. In the thesis, we provide a general framework for translating GDM and GMQL into SciDB; in particular, the translation of GMQL requires a general description of queries as DAGs of operations and then a specidfic translation of each GMQL operation into low-level DAG nodes. Other implementations of GMQL use cloud computing frameworks (Pig, Flink and Spark) to execute operations directly on files; our work covers all the GMQL language and provides a complete alternative baseline implementation, based on the SciDB database engine. In comparison, we obtained better performance on various operators which can exploit the data model of SciDB, but worse performance on massive operations (such as map and join), where the implementation based on Spark is faster. However, a lot of options exists for improving our baseline SciDB implementation. Along this objective, we focused on a new abstractions for parallelism; we realized that parallelism of massive operations on the genome requires bin- ning, i.e. the partitioning of the genome into portions so that operations are performed in parallel at each bin. We then studied the mono-dimensional binning supported by the current SciDB implementation, and we designed bi-dimensional binning, an alternative strategy also applicable to the SciDB data model. We focused on range intersection, where the challenge is to build a binning strategy comparing as few regions as possible, by limiting the comparison just to the regions that can intersect. In comparison, bi-dimensional binning obtains better performance on several datasets and scales better with data of increasing size.
Una nuova tecnologia per leggere il DNA, chiamata Next Generation Se- quencing (NGS), sta cambiando la ricerca biologica e le pratiche mediche, grazie alla disponibilit ́a a basso costo di milioni di sequenze di DNA di una vasta variet ́a di specie, tra cui l’uomo. Finora la comunit ́a di ricerca bioinformatica si ́e concentrata perlopiu ́ sull’analisi primaria e secondaria (allineamento e correlazione), ma il problema recente ́e quello dell’analisi terziaria, che riguarda il trattamento di molti sample sperimentali e l’ esplorazione attraverso browser visivi. La quantit ́a di dati processata per l’analisi terziaria richiede un sistema Big Data. GenData 2020 ́e un progetto di ricerca nato per affrontare questo problema. Lo sviluppo di questo progetto ha portato alla definizione di un nuovo sistema generico per l’interrogazione di sorgenti di dati eterogenee, basato su un modello dati chiamato GDM e un linguaggio di interrogazione del GDM, chiamato GMQL. GDM permette di descrivere i dati provenienti da esperimenti NGS, includendo dati relativi sia alle regioni che ai metadati derivati dagli esperimenti sul DNA; GMQL e' un linguaggio algebrico di alto livello che opera su GDM e fornisce sia operatori convenzionali che specifici al dominio genomico. In questa tesi abbiamo sviluppato una nuova implementazione di GMQL. Abbiamo deciso di utilizzare SciDB, un sistema per la gestione dati orientato alle applicazioni scientifiche e sviluppato da Paradigm4, una startup localizzata a Cambridge. SciDB permette di astrarre il sistema di gestione della persistenza, della distribuzione dei dati e della ottimizzazione delle operazioni tramite parallelismo. In questa tesi proponiamo un framework per la conversione di GDM e GMQL su SciDB; nello specifico, verranno descritte le traduzioni richieste per trasformare ogni singolo nodo del DAG in una operazione a basso livello di GMQL. Le implementazioni di GMQL esistenti fanno uso di framework basati sul cloud computing (Pig, Flink e Spark) per eseguire le operazioni diret- tamente su file; il nostro lavoro copre tutte le operazioni GMQL e fornisce una alternativa stabile e completa basata su SciDB. Comparando le implementazioni, abbiamo ottenuto migliori prestazioni su molti operatori in grado di sfruttare il particolare modello dati di SciDB, mentre risultati peggiori sono stati registrati su operazioni piu ́ pesanti (quali la map e la join), dove l’implementazione basata su Spark risulta vincente. In ogni caso, abbiamo definito una serie di valide opzioni per migliorare l’implementazione su SciDB. In tal senso, ci siamo concentrati su nuove metodologie di parallelismo; abbiamo realizzato che per eseguire parallelismo sulle maggiori operazioni ́e necessario effettuare del binning, per esempio partizionando l’intero genoma in varie sezioni, eseguendo quindi le varie operazioni su ogni singola sezione. Abbiamo studiato il binning mono-dimensionale, ad oggi implementato seguendo le metodologie proposte in letteratura, e abbiamo progettato il binning bi- dimensionale, una strategia alternativa applicabile al modello dati di SciDB. Ci siamo concentrati sulla intersezione di intervalli, dove l’obiettivo ́e costruire una strategia che sia in grado di comparare il minor numero di regioni, limitando la selezione a quelle regioni che possono effettivamente intersecarsi. Comparando le due metodologie, il binning bi-dimensionale ottiene prestazioni migliori su varie tipologie di dataset e scala in maniera piu` efficiente all’aumentare del numero di dati.
Genomic computing with SciDB, a data management system for scientific applications
CATTANI, SIMONE
2015/2016
Abstract
A new technology for reading the DNA, called Next Generation Sequencing (NGS), is changing biological research and medical practice, thanks to the low-cost availability of millions of whole genome sequences of a variety of species, and most important of humans. So far, the bio-informatics research community has been mostly challenged by primary and secondary analysis (data alignment and feature calling) but the emerging problem today is the so-called tertiary analysis, concerned with multi-sample processing, annotation and filtering of variants, and genome browser-driven exploratory analysis. The amount of data for tertiary analysis requires Big Data man- agement. The GenData 2020 project is focused on this problem. The project developed new abstractions for querying heterogeneous genomic datasets, centered on the notion of Genomic Data Model (GDM) and Genometric Query Language (GQL). GDM describes genomic datasets produced by NGS experments, and includes both regions and metadata associated to DNA experiments; GMQL is a high-level, algebraic language which operates upon GDM and provides both conventional and domain-specific operations. In this thesis we developed a new implementation of GMQL. We used SciDB, a data management system for scientific applications developed by Paradigm4, a startup company located in Cambridge. SciDB provides abstraction from storage management, data distribution, and optimized parallel execution. In the thesis, we provide a general framework for translating GDM and GMQL into SciDB; in particular, the translation of GMQL requires a general description of queries as DAGs of operations and then a specidfic translation of each GMQL operation into low-level DAG nodes. Other implementations of GMQL use cloud computing frameworks (Pig, Flink and Spark) to execute operations directly on files; our work covers all the GMQL language and provides a complete alternative baseline implementation, based on the SciDB database engine. In comparison, we obtained better performance on various operators which can exploit the data model of SciDB, but worse performance on massive operations (such as map and join), where the implementation based on Spark is faster. However, a lot of options exists for improving our baseline SciDB implementation. Along this objective, we focused on a new abstractions for parallelism; we realized that parallelism of massive operations on the genome requires bin- ning, i.e. the partitioning of the genome into portions so that operations are performed in parallel at each bin. We then studied the mono-dimensional binning supported by the current SciDB implementation, and we designed bi-dimensional binning, an alternative strategy also applicable to the SciDB data model. We focused on range intersection, where the challenge is to build a binning strategy comparing as few regions as possible, by limiting the comparison just to the regions that can intersect. In comparison, bi-dimensional binning obtains better performance on several datasets and scales better with data of increasing size.| File | Dimensione | Formato | |
|---|---|---|---|
|
Genomic-Computing-with-SciDB.pdf
accessibile in internet per tutti
Descrizione: Thesis text
Dimensione
8.84 MB
Formato
Adobe PDF
|
8.84 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/123101