Heuristic-based optimizations for genomic computing

Next Generation Sequencing (NGS), a high-throughput, massively parallel technology for reading the DNA, 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, responsible of exploring, querying and integrating processed data, so as to give answers to complex biological and clinical questions, ultimately yielding to personalized medicine. A new holistic approach for tertiary data analysis has been developed by the Genomic Computing team at Politecnico di Milano. The approach, based on the notion of Genomic Data Model (GDM) and on a new high-level language, called GenoMetric Query Language (GMQL), combines data modeling and management, big data, cloud computing, systems architecture and parallel algorithms into the new Genomic Data Management System (GDMS). Together with the system, new abstractions for parallelism have been introduced; the parallelism of massive operations on the genome is based on binning, i.e. the partitioning of the genome into portions so that operations are performed in parallel at each bin. Even though much efforts have been made to develop an efficient system, there are still cases in which query performance remains problematic. The main reason behind those performance issues is the lack of high level optimizations that, by reasoning on data and query characteristics, are able to put in place smart optimization strategies. This thesis focuses on the development on one such optimization; optimal binning. Since experiments demonstrated that the bin size is a critical parameter for the overall performance of domain-specific operations, we developed a mathematical model that, taking into account query and data characteristics, allows to predict a bin size that makes binning efficient. In order to perform optimal binning, we also introduce Genomic Profiling, which, taking into account the specificity of genomic data modeling, quantitatively defines the properties that better characterize a genomic dataset from the point of view of query optimization. Genomic Profiling and bin optimization become part of the Optimizer, a new module designed to collect the optimizations developed in this thesis and those optimizations that will come in the future.

La Next Generation Sequencing (NGS) è nuova tecnologia per il sequenziamento del DNA che sta cambiando la ricerca biologica e la pratica medica, supportata dalla disponibilità a basso costo di un grande quantità di DNA sequenziato di varie specie, tra cui quella umana. Finora, la comunità di ricerca bio-informatica si è concentrata sull’analisi primaria e secondaria (allineamento e correlazione), ma il problema emergente, negli ultimi anni, è la cosiddetta analisi terziaria, orientata all’esplorazione, interrogazione e integrazione dei dati sperimentali, per dare risposta a complessi quesiti biologici e clinici e per favorire lo sviluppo della medicina personalizzata. Un nuovo approccio all’analisi terziaria è stato sviluppato al Politecnico di Milano dal team di Genomic Computing. L’approccio, basato sulla nozione di Genomic Data Model (GDM) e su un nuovo linguaggio di interrogazione, chiamato GenoMetric Query Language (GMQL), combina le tradizionali teorie sulla modellazione e gestione dei dati alle moderne tecnologie impiegate per l’analisi dei big data, dando vita ad un moderno sistema chiamato Genomic Data Management System (GDMS). Con il sistema, sono state introdotte nuove astrazioni per rendere possibile il processamento in parallelo di grandi quantità di dati rappresentati DNA; tra queste il binning, ovvero il partizionamento del genoma in intervalli di eguale misura, chiamati bin, che permettono di decomporre una singola operazione sul genoma in un certo numero di operazioni da eseguire in parallelo su ciascun bin. Nonostante l’impegno speso per sviluppare algoritmi efficienti, ci sono ancora casi in cui l’esecuzione di query complesse risulta problematica in termini di performance. Queste problematiche sono in generale riconducibili ad una carenza di ottimizzazioni di alto livello in grado di tener conto delle caratteristiche dei dati e delle query sottoposte dall’utente. Questa tesi sviluppa una di queste ottimizzazioni; l’ottimizzazione del binning. Diversi esperimenti, infatti, hanno dimostrato che la dimensione di ogni bin è un parametro che influenza molto la performance complessiva degli operatori di dominio. Pertanto, abbiamo sviluppato un modello matematico che ci consente di calcolare, caso per caso, la dimensione ottimale di questo parametro. Per poter implementare questa ottimizzazione, abbiamo anche sviluppato un Profilatore, che, tenendo conto della specificità dei dati genomici, definisce quantitativamente le caratteristiche che meglio descrivono un dataset ai fini dell’ottimizzazione delle query. Il Profilatore e le euristiche per il binning ottimale diventano parte dell’Ottimizzatore, un nuovo modulo del GDMS progettato per contenere e supportare le ottimizzazioni sviluppate in questa tesi e quelle che verranno sviluppate in un prossimo futuro.