Distributed processing and optimization methods for querying big genomic datasets

Next-Generation Sequencing (NGS) is an innovative approach that has revolutionized genomic research. Compared to prior technologies, NGS allows reading the whole genome much faster and with significant cost reductions, by reading millions of DNA fragments in parallel. Large and well-organized collections of sequence datasets have become publicly available, together with new technologies for integrating and querying them. The rapidly increasing amount of produced data helps answering fundamental biological questions and paves the way for personalized medicine. The data management technology developed within my group at Politecnico di Milano is based on the "GenoMetric Query Language" (GMQL), a high-throughput computational solution for integrating and processing big genomic datasets. The Genomic Data Model (GDM), on which GMQL relies, describes DNA regions similarly to interval data; a region of the DNA is encoded by its start and stop positions within the chromosome, followed by an arbitrary set of attributes. GMQL provides several operators inspired by standard relational algebra, including some domain-specific aspects, which take into account the regions' relative positions and distances. The Genomic Data Management System (GDMS) maps queries to DAGs of modules, each translating GMQL operations, that run on top of the cloud-computing framework Apache Spark. Custom "binning algorithms" enhance the parallelism of computationally expensive operations by splitting the genome into small portions, named bins, that are then processed in parallel. This thesis describes significant optimizations and extensions made to the GDMS. The first achievement is the improvement of domain-specific operations' performance, obtained by optimizing the underlying binning algorithms. Specifically, the thesis solves the problem of determining the optimal bin size, using complex analytical models that consider the input data's characteristics, the operation parameters, and the execution environment. A significant extension of the language, called Federated GMQL, is then introduced. Federated GMQL allows processing GMQL queries over a cluster of interconnected, but geographically-spread, GDMS instances, that act both as data providers and as computational nodes. In particular, the thesis describes how the GDMS architecture was extended to support the new functionalities. The third contribution of this thesis has the objective of approaching a larger set of Spark applications, in particular those that can be represented as DAGs of operations. In this setting, we designed and validated a performance prediction model for generic DAG-based applications running on Apache Spark. The proposed solution is a modular approach that mixes machine learning and analytical models for predicting the application execution time. Specifically, a machine learning model is built for each task (operation) in the application DAG. Then individual predictions are combined for estimating the execution time of the whole DAG, independently of its complexity. Analytical models, initially designed for the binning optimization, are re-used to estimate intermediate results and reduce the prediction error. This approach is applied to improve the performance of classes of execution plans for federated queries. While GMQL and GDMS are suited for massive manipulation of genomic regions, a complementary tool, called MutViz, targets a specific task of genomic analysis. Specifically, MutViz compares user-provided sets of genomic regions against a rich database of somatic mutations, giving useful hints on their role in the development of cancer. By combining traditional databases and distributed algorithms, we designed a high-performance system that supports different computations. A web interface shows the computation results through several interactive visualizations, while a python library allows further downstream processing. An ongoing work re-adapts Mutviz to support the visual analysis of SARS-CoV-2 variants.

Il Next-Generation Sequencing (NGS) è un approccio innovativo che ha rivoluzionato la genomica. Rispetto alle tecnologie precedenti, NGS consente di leggere l'intero genoma molto più rapidamente e con significative riduzioni dei costi, processando milioni di frammenti di DNA in parallelo. Negli ultimi anni, si sono resi disponibili diversi database pubblici di dati genomi e nuove tecnologie utili ad integrarli e interrogarli. Tali dati, in continuo aumento, ci aiutano a rispondere alle domande fondamentali della biologia e spianano la strada verso la medicina personalizzata. La tecnologia sviluppata dal gruppo di Genomic Computing (GeCo) del Politecnico di Milano si basa sul "GenoMetric Query Language" (GMQL), una soluzione di calcolo ad elevate performance per l'integrazione e l'elaborazione di grandi set di dati genomici. Il Genomic Data Model (GDM), su cui si basa GMQL, descrive le regioni del DNA come intervalli; una regione del DNA è codificata dalle sue posizioni di inizio e fine all'interno del cromosoma, seguite da un insieme arbitrario di attributi. GMQL fornisce diversi operatori ispirati all'algebra relazionale standard, e include alcuni aspetti specifici del dominio, che tengono conto delle posizioni e delle distanze relative delle regioni. Il Genomic Data Management System (GDMS) mappa ogni query in un digrafo aciclico (DAG) di moduli, ciascuno dei quali implementa le operazioni della query come operazioni del framework di cloud computing Apache Spark. Gli "algoritmi di binning”, specificamente sviluppati per il sistema, migliorano il parallelismo delle operazioni computazionalmente critiche suddividendo il genoma in piccole porzioni, denominate bin, che vengono poi processate in parallelo. Questa tesi descrive ottimizzazioni e le significative estensioni apportate al GDMS. Il primo contributo è il miglioramento delle prestazioni delle operazioni critiche del linguaggio, ottenuto ottimizzando gli algoritmi di binning sottostanti. In particolare, la tesi risolve il problema di determinare la dimensione ottimale dei bin, utilizzando complessi modelli analitici che considerano le caratteristiche dei dati di input, i parametri della query e l'ambiente di esecuzione. Viene quindi introdotta un'estensione significativa del linguaggio, denominata Federated GMQL. Questo sistema consente l'elaborazione di query GMQL su un insieme di istanze GDMS interconnesse ma geograficamente distanti, che agiscono sia come provider di dati che come nodi di calcolo. In particolare, la tesi descrive come l'architettura GDMS è stata re-ingegnerizzata a supporto delle nuove funzionalità. Il terzo contributo di questa tesi considera un più ampio set di applicazioni Apache Spark, in particolare quelle che possono essere rappresentate come DAG di operazioni. In questa impostazione, abbiamo progettato e validato un modello di previsione delle performance per applicazioni generiche basate su DAG ed implementate su Apache Spark. La soluzione proposta è un approccio modulare che combina machine learning e modelli analitici per prevedere il tempo di esecuzione dell'applicazione. In particolare, viene creato un modello di machine learning per ogni attività (operazione) nel DAG dell'applicazione. Quindi le singole previsioni vengono combinate per stimare il tempo di esecuzione dell'intero DAG, indipendentemente dalla sua complessità. I modelli analitici, inizialmente progettati per l'ottimizzazione del binning, vengono riutilizzati per stimare i risultati intermedi delle operazioni e ridurre l'errore di previsione. Questo approccio può essere infine applicato per migliorare la pianificazione dell’esecuzione delle query federate. Mentre GMQL e il GDMS sono adatti per processare grandi quantità di regioni genomiche, uno strumento complementare, chiamato MutViz, ha come obiettivo l’analisi delle mutazioni genetiche. In particolare, MutViz confronta set di regioni genomiche fornite dagli utenti con un ricco database di mutazioni somatiche, fornendo utili suggerimenti sul loro ruolo nello sviluppo di malattie come cancro. Combinando database tradizionali e algoritmi distribuiti, abbiamo progettato un sistema ad alte prestazioni che supporta diverse tipologie di calcolo. Un'interfaccia web mostra i risultati attraverso diverse visualizzazioni interattive, mentre una libreria python consente un'ulteriore elaborazione a valle. Un lavoro in corso riadatta Mutviz per supportare l'analisi visiva delle varianti del SARS-CoV-2.