Modeling and querying genomic data

In the last decade, new technologies for fast DNA sequencing, known under the name of next-generation sequencing (NGS), had just become available; they enable reading the whole genome much faster, at higher resolution, and at lower cost, thereby giving us the data to answer fundamental biological questions and opening the ground to personalized genetic medicine. Huge investments were, and they still are, targeted to sequencing the DNA of large populations, with repositories of well-curated sequence data being collected and made public for investigation. Answers to many biomedical problems are hidden in these data, e.g. how cancer arises, how driving mutations occur, how much cancer is dependent on environment. While genetic sequencing are mature, a quantum leap is needed for building the computing infrastructure at the receiving end of DNA sequencing machines. In particular, genomic data management is struggling on the initial problem of storing the data which are fast produced by biologists in their laboratories. A powerful data infrastructure is required for going beyond pure storage, and enabling viewing, querying, analyzing, mining, and searching over a world-wide available collection of genetic data. This Thesis describes the GenData System. The first innovation proposed within GenData is the organization of genomic data through a uniform data model, the Genomic Data Model (GDM), capable of expressing the various features that are embedded in the produced biomolecular data, or in their correlated phenotypic data that can be extracted from clinical databases, or in the information inferred by applying data analysis methods to them. The most relevant feature of GDM is the subdivision of data into region data and metadata. Region data consists of structured data that captures the processed outcome of any NGS experiment. Metadata is a set of free attribute value pairs meant for representing biological and technical details of the experiments as well as clinical and phenotypic information about the sample donor. The vision of the project is completed by methods for querying, searching, and analyzing genomic data. While several prototypes were developed, this Thesis focuses on the GenoMetric Query Language (GMQL), a novel declarative high level query language, aimed to express complex queries on GDM instances for answering biological questions. It combines relational algebra and domain specific operators for genomics. GMQL has been implemented upon cloud based platforms; this choice was dictated by the big-data nature of genomic data. The Thesis describes many aspect of such implementation, mainly regarding the translation strategy for GMQL, the generation of an execution plan from a query, its logical optimization and the efficient algorithms designed for computationally heavy domain specific operations. In its last release, GMQL is initially compiled down to an intermediate representation, which consists of a graph where nodes represents atomic transformations and edges dependencies among the operations. The intermediate representation of a query is then interpreted and executed by an engine that actually elaborates genomic data stored within the GenData repository. Having an intermediate representation provides a framework for developing many optimization strategies, based both on the re-writing of the graph and on efficient implementation of single blocks. Most notable results comprise the so called “meta-first” optimization and the “binning algorithms”. The “meta-first” is a runtime optimization that leverages the fact that metadata are usually much smaller than region data; by tracking the execution of metadata it is possible to avoid unnecessary and heavy computation on region data. The “binning algorithms” are a class of distributed and highly parallel algorithms for the implementation of genomic operations; they are based on the splitting of genome into small portions, named bins. Although binning algorithms have been designed with genomic operations in mind, they are suitable for processing any interval based information, such as spatial or temporal data. Two real world case studies, where the GenData system was used for answering complex biological questions, conclude the manuscript. The first of them consists of a study of the 3D organization of the DNA across several human tissues and an investigation of how a variation of that structure may be linked with the rise of cancer. The latter explores how certain mutations, occurring within enhancers (particular DNA regions involved in the regulation of the gene expression), are associated with genetic diseases or phenotypes.

Nel corso degli ultimi anni sono state introdotte nuove tecnologie per il sequenziamento del DNA, conosciute sotto il nome Next-Generation-Sequencing (NGS). I macchinari NGS consentono la lettura di tutto il genoma molto velocemente, ad alta risoluzione, e ad un costo contenuto, dandoci così i dati per poter rispondere alle fondamentali domande biologiche e aprendo il terreno alla medicina genetica personalizzata. Ingenti investimenti sono stati, e sono tuttora, mirati al sequenziamento del DNA di grandi popolazioni; conseguentemente grandi repository curati di dati di sequenze di DNA stanno venendo creati e resi pubblici per ulteriori ricerche biomediche. Le risposte a molti problemi biomedici sono nascoste in questi dati, per esempio come insorge il cancro, come avvengono le mutazioni driver, quanto il cancro dipende dalle condizioni ambientali. Mentre le tecnologie per il sequenziamento genetico sono ormai mature, un salto di qualità è necessario per costruire l'infrastruttura di calcolo per i dati generati dai sequenziatori. In particolare, dal punto di vista della gestione dei dati, ci si è focalizzati sul problema iniziale di memorizzare i dati; tuttavia, una più potente infrastruttura è necessaria per andare oltre al mero stoccaggio dei dati e consentirne invece la visualizzazione, l'interrogazione, l'analisi e l'estrazione di conoscenza. Questa Tesi descrive il sistema GenData. La prima innovazione proposta all'interno di GenData è l'organizzazione dei dati genomici attraverso un modello uniforme, chiamato Genomic Data Model (GDM), in grado di esprimere sia le varie informazioni contenute nei dai biomolecolari prodotti, sia i dati associati riguardo a caratteristiche fenotipiche o cliniche del campione analizzato e le informazioni sul metodo con cui i dati sono stati generati e processati. La caratteristica più rilevante di GDM è la suddivisione dei dati in dati di regioni e metadati. I dati di regione sono dati strutturati che catturano l'esito di qualsiasi esperimento NGS. I metadati sono un insieme arbitrario coppie attributo-valore, pensato per rappresentare i dettagli biologici e tecnici degli esperimenti così come le informazioni cliniche e fenotipiche s del campione. La visione del progetto è completato da metodi per l’interrogazione, la ricerca e l'analisi di dati genomici. Diversi prototipi sono stati sviluppati, questa tesi si concentra su uno di essi, Query Language GenoMetric (GMQL), un linguaggio di interrogazione dichiarativo e di alto livello, volto ad esprimere query complesse su istanze di GDM per rispondere a domande biologiche. GMQL combina operatori dell’algebra relazionale e specifici di dominio per la genomica. GMQL è stato implementata su piattaforme cloud; questa scelta è stata dettata dalla natura big-data dei dati genomici. La Tesi descrive molti aspetti di tale implementazione, soprattutto legati alla strategia di traduzione di GMQL, la generazione del piano di esecuzione di una query, la sua ottimizzazione logica e gli algoritmi efficienti progettati per operazioni di dominio che risultano essere computazionalmente pesante. Nella sua ultima release, GMQL è inizialmente compilato in una rappresentazione intermedia, che consiste di un grafico dove i nodi rappresentano trasformazioni atomici e gli archi le dipendenze tra le operazioni. La rappresentazione intermedia di una query viene interpretata ed eseguita da un motore che elabora effettivamente i dati genomici memorizzati all'interno del repository GenData. Avere una rappresentazione intermedia fornisce una piattaforma per lo sviluppo di molte strategie di ottimizzazione, basate sia sulla riscrittura del grafo e che sulla implementazione efficiente dei singoli blocchi. I risultati più importanti comprendono la cosiddetta ottimizzazione "meta-first" e gli "algoritmi di binning". La "meta-first" è una ottimizzazione runtime che sfrutta il fatto che i metadati sono solitamente molto più piccoli dei dati di regioni; monitorando l'esecuzione sui metadati è possibile evitare calcoli inutili sui dati di regioni. Gli "algoritmi di binning" sono una classe di algoritmi distribuiti e altamente paralleli per la realizzazione delle operazioni di genomica; si basano sulla divisione genoma in piccole partizioni, chiamate bin. Sebbene gli algoritmi di binning siano stati progettati con le operazioni genomici in mente, sono adattabili all'elaborazione di qualsiasi informazione basata sul concetto di intervallo, come ad esempio i dati spaziali o temporali. Due casi di studio reali, in cui il sistema GenData è stato utilizzato per rispondere a domande biologiche complesse, concludono il manoscritto. Il primo di essi è costituito da uno studio dell'organizzazione 3D del DNA in più tessuti umani e un'indagine di come certe variazioni di tale struttura possano essere collegato con l’insorgenza del cancro. Il secondo esplora come alcune mutazioni, che si verificano all'interno di enhancer (particolari regioni del DNA coinvolti nella regolazione dell'espressione genica), sono associate a malattie genetiche o particolari tratti fenotipici.