Scalable data management and processing for genomic computing

The recent emergence of Next Generation Sequencing (NGS) technologies, in genomics field, produced vast amounts of genomic data. NGS resulted in dropped the cost of sequencing ("reading" in general terms) genomic material very fast. There exist many methods to extract signals from the genomic data, that associate a region of the genome with some interesting information - such as a mutation or a peak of expression. Thus, a new problem is emerging: making sense of these signals, heterogeneous in nature, through new kind of languages that can extract relevant information from various heterogeneous sources, integrate them in a new data management system, and compute interesting results. Biologists say that a huge amount of information is undiscovered within the repositories that have been built in the last decade - therefore, the focus of genomic data management for the next decade is querying and analysing heterogeneous genomic data. This thesis is about scalable data management and processing for genomic data. We developed a new system which consists of a new query language called GenoMetric Query Language (GMQL), a new data model for heterogeneous data (called Genomic Data Model - GDM), and a new processing engine which embeds scalable genomic algorithms implemented on several data flow engines. The name (GMQL) derives from the ability of the language of dealing with region-based operations which take into account the regions topological location to the reference genome. GDM mediates all existing heterogeneous data formats. In combination, GDM and GMQL introduce a paradigm shift, by providing a high-level, declarative query language which supports data-driven computations. GMQL is a collective effort which has involved a group of students and professors from Politecnico di Milano. The work reported in this PhD thesis is focused on the design, implementation and validation of the scalable genomic data management and processing system; The architecture of various prototypes of GMQL, GDM, and the scalable genomic processing algorithms. GMQL is a domain-specific language. In this thesis, we developed several scalable algorithms for genomic processing for serving the needs of GMQL queries. By the use of data flow engines as our target implementations, we capitalize upon existing frameworks which are available today and will be developed in the future by the data management community. In order to increase the parallelism of the genomic algorithms in data flow engines, we proposed new data binning methodologies that are suitable for genomic data and for the nature of the data flow engines. We also used our genomic algorithms for comparing dataflow engines and we developed versions of the scalable algorithms that take advantage of the nature of data flow engines - for example in SciDB, based on multidimensional arrays, we make use of the fast access to slices of the array. Along with the design of the system and the scalable genomic algorithms, the implementation has gone through phases, and specifically we delivered a first implementation of GMQL, called GMQL V1, based on Hadoop 1 and the target systems Pig; and a second implementation, called GMQL V2, based on Hadoop 2 and the target systems Spark, Flink, and SciDB. The thesis describes the rationale of the two implementations and the process that led from the first to the second prototype. GMQL engine has a well-designed system architecture with modular organization; system modules can be easily tested, maintained or replaced. GMQL is translated to an intermediate, target-independent representation, based on a Directed Acyclic Graph (DAG), which describes workflows of basic operation nodes. Each node is a primitive operation that implements a specific functionality of GMQL, and operations are mapped to specific target systems; in this way, we can support several implementations to several target systems. The GMQL engine architecture includes a repository abstraction which is technology-independent, hence several options (local file system, Hadoop File system, scientific database management) are made available by simply including a different repository interface. Several aspects of the architecture are designed for fast execution on big data sets. This thesis also includes a thorough performance analysis, by comparing GMQL engine V1 to V2, Flink to Spark implementations, and Spark to SciDB implementations. From such studies, we learnt about optimal parameters settings for the scalable genomic algorithms on diverse data sizes and platforms. We also include some preliminary results of a study which we are conducting in order to field-test GMQL applicability. We implemented a pipeline that uses GMQL for studying gene expression in normal and cancer cells in the context of DNA 3D structure; the study is based on big data sets for about twenty available tissues, thousands of samples for either normal or tumor cases are considered in the study. In summary, this thesis is a step forward in the development of a systemic approach to scalable genomic data management and processing. Whereas other approaches focused on extracting genomic features from data, our approach is on combining these heterogeneous features so as to solve complex biological problems. We believe that the importance of a systemic approach to genomic data management will grow in the near future, with the availability of huge repositories of genomic data sets.

Le tecnologie di Next Generation Sequencing, associate ad una progessiva caduta del costo di sequenziamento, hanno prodotto enormi quantità di dati genomici. Esistono molti metodi per estrarre segnali dai dati genomici, associando a regioni del genoma informazioni interessanti – tra cui le mutazioni o i picchi di espressione. Così, un nuovo problema sta emergendo: dare un senso a questi segnali, eterogenei in natura, attraverso nuovi tipo di linguaggi di interrogazione per estrarre informazioni rilevanti da varie fonti eterogenee e integrarli in un nuovo sistema di gestione dei dati. I biologi dicono che i repository che sono stati costruiti negli ultimi dieci anni comprendono grandi quantità di informazioni ancora da scoprire - di conseguenza, il principale obiettivo della gestione dei dati genomici per il prossimo decennio è l'interrogazione e l'analisi di dati genomici eterogenei. Questa tesi affronta l'elaborazione e gestione dei dati genomici. Abbiamo sviluppato un nuovo sistema che consiste in un nuovo linguaggio di query (chiamato GenoMetric Query Language, GMQL), un nuovo modello di dati per i dati eterogenei (chiamato Genomic Data Model - GDM), e vari sistemi per la loro elaborazione che incorporano algoritmi genomici scalabili. Il nome (GMQL) deriva dalla capacità del linguaggio di supportare operazioni che tengano conto della posizione delle regioni rispetto al genoma di riferimento. In combinazione, GDM e GMQL introducono un cambiamento di paradigma, fornendo un linguaggio di query dichiarativo di alto livello.   GMQL è uno sforzo collettivo che ha coinvolto un gruppo di studenti e professori del Politecnico di Milano. Il lavoro riportato in questa tesi di dottorato è incentrato sulla progettazione, realizzazione e validazione della gestione scalable dei dati genomici tramite un sistema di elaborazione, mostrando vari pototipi di GMQL e vari algoritmi di elaborazione. Abiamo sfruttato la presenza di sistemi open-souce per la gestione di dati in ambiente cloud (Spark, Flink, SciDB). Al fine di aumentare il parallelismo degli algoritmi genomici, abbiamo proposto nuovi algoritmi di binning (suddivisione) del genoma, che consentono elaborazioni parallele. La progettazione di sistema e algoritmi è passata attraversato fasi, e in particolare abbiamo sviluppato una prima implementazione di GMQL, chiamata GMQL V1, basato su Hadoop 1 e Pig; ed una seconda implementazione, chiamata GMQL V2, basata su Hadoop 2 e Spark, Flink, e SciDB. La tesi descrive la logica delle due implementazioni e il processo che ha portato dal primo al secondo prototipo. Il ssitema GMQL V2 ha una organizzazione modulare; I moduli di sistema possono essere facilmente testati, mantenuti o sostituiti. GMQL è tradotto in una rappresentazione intermedia indipendente dal target, sulla base di una grafo diretto aciclico (DAG) che descrive flussi di operazioni elementari. Ogni nodo del grafo è un'operazione primitiva che corrisponde a una funzionalità specifica di GMQL e viene implementata sui tre sistemi target   L'architettura del motore GMQL comprende un repository astratto, indipendente dalla tecnologia, che può essere realizzato in vari modi (file locali, file system Hadoop, database scientifico). Diversi aspetti dell'architettura sono progettati per l'esecuzione efficiente su grandi basi di dati. La tesi include anche un'analisi approfondita delle prestazioni, confrontando i motori GMQL V1 e V2, e le implementazioni Flink, Spark e SciDB. Da tali studi, abbiamo imparato a conoscere le impostazioni ottimali per i parametri degli algoritmi genomici, resi scalabili su diversi formati e piattaforme di dati.   La tesi contiene anche alcuni risultati preliminari di uno studio che stiamo conducendo al fine di verificare la applicabilità di GMQL. Abbiamo implementato una pipeline che utilizza GMQL per lo studio dell'espressione genica in cellule normali e tumorali nel contesto della struttura del DNA 3D; lo studio si basa su una ventina di tessuti disponibili; migliaia di campioni normali o tumorali sono considerati nello studio. In sintesi, questa tesi è un passo in avanti nello sviluppo di un approccio sistemico alla gestione scalabile dei dati genomici. Mentre altri approcci sono focalizzati su estrazione di caratteristiche genomiche dai dati, il nostro approccio è basato sulla combinazione di queste caratteristiche eterogenee, in modo da risolvere i problemi biologici complessi. L'importanza di un approccio sistemico alla gestione dei dati genomici crescerà nel prossimo futuro, con la disponibilità di enormi repository di dati genomici.