145 research outputs found
BWaveR : an FPGA-accelerated genomic sequence mapper leveraging succinct data structures
No full textLAUREA MAGISTRALELo sviluppo di tecnologie di sequenziamento sempre più efficienti, che prendono il nome di Next Generation Sequencing (NGS), ha portato ad un rapidissimo aumento della quantità di dati genomici disponibili, ponendo le basi per la nascita della medicina personalizzata.
Purtroppo però, l'analisi di una tale quantità di dati richiede, ad oggi, ancora troppo tempo e troppa energia.
Nuovi strumenti computazionali sono quindi necessari per accelerare la ricerca in questo campo, e per garantire lo sviluppo e la democratizzazione della medicina personalizzata.
In tale contesto, lo scopo di questa tesi è la progettazione e la realizzazione di un tool per l'allineamento di sequenze genomiche, che risulti efficiente e facile da utilizzare in diverse applicazioni bioinformatiche.
Il funzionamento di tale tool è basato su una struttura dati succinta, che permette di comprimere efficacemente i dati genomici, riducendo l'utilizzo di memoria e permettendo, allo stesso tempo, un rapido accesso a tali dati.
In questo elaborato verrà fornita un'ampia descrizione della struttura dati proposta, del suo utilizzo, e delle sue caratteristiche in termini di utilizzo di memoria e tempi d'esecuzione.
Questa tesi presenta anche la realizzazione di BWaveR, un sistema eterogeneo per l'allineamento di sequenze, che si avvale delle ridotte dimensioni della struttura dati proposta per sfruttare al meglio l'architettura parallela dei Field Programmable Gate Arrays (FPGAs).
Tali dispositivi offrono vantaggi significativi dal punto di vista dell'efficienza energetica, ma risultano particolarmente difficili da programmare.
BWaveR, invece, consente di sfruttare i vantaggi dell'accelerazione hardware attraverso una semplice ed intuitiva applicazione web, che garantisce un facile utilizzo ed una buona user experience.
Il tool sviluppato è stato validato e valutato attreverso il confronto con applicativi software equivalenti.
I test di validazione dimostrano l'affidabilità di BWaveR e provano la consistenza dei risultati prodotti.
Inoltre, i risultati sperimentali mostrano che l'architettura hardware proposta è in grado di ridurre il tempo d'esecuzione ed il consumo energetico del processo di allineamento di sequenze genomiche.
Pertanto, BWaveR si propone come una valida soluzione per accelerare una vasta gamma di applicazioni bioinformatiche, permettendo anche ad utenti senza competenze di programmazione di beneficiare dei vantaggi di un'architettura hardware specializzata.The advent of Next Generation Sequencing (NGS) produced an explosion in the amount of genomic data generated, which resulted in the birth and early development of personalized medicine. However, the tools currently employed for the analysis of these data still require too much time and power.
Thus, to boost the research in this field, new bioinformatic tools are needed, which can efficiently handle the vast amount of genomic data, in order to keep up with the pace of NGS technologies.
In this scenario, the aim of this thesis is the design and the implementation of a memory-efficient, easy-to-use short sequence mapper, to be employed in various bioinformatic applications.
At the core of the proposed tool there is an efficient implementation of a succinct data structure, allowing to compress the genomic data while still providing efficient queries on them.
A comprehensive description of the data encoding scheme is presented in this work, together with the characterization of the proposed data structure in terms of memory utilization and execution time.
To improve the performances and the energy efficiency of the sequence mapping process, this thesis also proposes a custom hardware design, which leverages the compression capability of the proposed data structure to fully exploit the highly parallel architecture of Field Programmable Gate Arrays (FPGAs).
We employed such custom hardware architecture to develop BWaveR, a fast and power-efficient hybrid sequence mapper, which is made available through an intuitive web application that guarantees high usability and provides great user experience.
Finally, this work provides a validation of the developed tool, in order to prove the correctness and reliability of the results it produces.
Moreover, it presents an extensive evaluation of the performances of the proposed hybrid system, through a comparison with state-of-the-art equivalent software tools.
The experimental results show that the proposed hardware architecture is able to provide application speed-up while significantly reducing the energy consumption.
Thus, BWaveR constitues a valid solution for accelerating bioinformatic applications involving genomic sequence mapping, allowing users to benefit from hardware acceleration without any development effort or any knowledge of the underlying hardware architecture
A Novel Methodology for a Comprehensive Analysis of Genomic Sequence-to-Graph Alignment Tools
No full textGenome graphs have proved to be a more compact and efficient way of representing genetic inter- and intra-individual variability. Although they overcome the traditional sequence-based genome references in many use cases, analyzing genome graphs introduces new computational challenges. The workhorse of graph-based genome analysis is the sequence-to-graph alignment process, which consists of finding the path in the graph that better represents a query sequence. This search is highly computationally intensive, and different solutions have been proposed to solve it efficiently, either by adapting sequence-to-sequence strategies or exploiting novel graph-specific algorithms. However, comparing sequence-to-graph alignment tools is quite challenging because of the complexity and relative novelty of this task, and the resulting lack of standardization. Therefore, here we propose a methodology for a comprehensive and structured comparison of such tools. First, we define a set of KPIs for the qualitative analysis of an aligner's usability, accuracy, and performance. Then, we introduce the first open-source(1) benchmark suite for the quantitative analysis of multiple sequence-to-graph aligners. We test the proposed methodology on state-of-the-art tools, proving how it easily provides valuable insights about the compared aligners. Finally, we conclude the paper by drawing some guidelines to drive the improvement of this promising research field
Leveraging heterogeneous hardware acceleration from high-level programming languages : the case for biomedical informatics
No full textDOTTORATONegli ultimi anni, il campo dell’informatica biomedica ha visto una vera e propria esplosione in termini di volume e complessità dei dati generati. Ciò ha reso evidente la necessità di sviluppare approcci innovativi per accelerare le analisi computazionali. Le unità di elaborazione grafica (Graphics Processing Unit (GPU)) sono emerse come potenti acceleratori hardware, in grado di garantire un sostanziale aumento delle prestazioni in vari settori. Tuttavia, la loro adozione nell’ambito dell’informatica biomedica è stata limitata principalmente al dominio del deep learning, a causa della disponibilità di librerie che mascherano la computazione su GPU. Ciò è dovuto principalmente alla scarsa integrazione delle GPU con i linguaggi di programmazione di alto livello, come R o Python, comunemente utilizzati nel contesto biomedicale. Questa tesi risponde all’esigenza critica di estendere l’utilizzo delle GPU a questi linguaggi di alto livello nel contesto dell’informatica biomedica.
La prima parte della tesi presenta una serie di applicazioni che sfruttano le GPU per accelerare l’addestramento di modelli di deep learning per diversi compiti, in particolare la riproposizione di farmaci, l’individuazione di demenza e l’identificazione di tumori polmonari. Sfruttando le capacità di elaborazione parallela delle GPU, si ottengono riduzioni significative dei tempi di addestramento, facilitando così iterazioni più rapide, e migliorando il ritmo della ricerca e del processo decisionale in ambito clinico. Tuttavia, le applicazioni citate comprendono altre fasi di elaborazione ad alta intensità di calcolo che potrebbero beneficiare dell’accelerazione hardware eterogenea. Un ponte tra i linguaggi di alto livello e la programmazione su GPU è indispensabile per consentire a ricercatori e professionisti di sfruttare appieno il potenziale di tali architetture computazionali nelle applicazioni di informatica biomedica.
Il fulcro di questa tesi è la presentazione di un framework innovativo chiamato GrCUDA. Proposto inizialmente da NVIDIA e Oracle, GrCUDA funge da strato intermedio che consente di accedere facilmente alle risorse delle GPU da tutti i linguaggi di programmazione di alto livello supportati dall’ecosistema poliglotta GraalVM. Questa tesi introduce un nuovo scheduler asincrono multi-GPU per GrCUDA che facilita lo sviluppo di applicazioni multi-GPU, astraendo i dettagli di basso livello delle e fornendo un’interfaccia di alto livello efficiente e facile da usare. I risultati sperimentali dimostrano che lo scheduler proposto consente di raggiungere automaticamente delle prestazioni comparabili a quelle ottenute da un programmatore esperto, rendendo le computazioni multi-GPU più semplici da approcciare e minimizzando il compromesso in termini di performance. Ciò rende GrCUDA uno strumento ad altissimo potenziale, consentendo ai ricercatori nell’ambito dell’informatica biomedica di sfruttare le notevoli capacità di calcolo di molteplici GPU senza compromettere la facilità di programmazione e la flessibilità del linguaggio.
A dimostrazione delle potenzialità del framework GrCUDA, la parte finale della tesi presenta due applicazioni che ne sottolineano l’utilità nell’ambito biomedicale. La prima applicazione è GPJSON, un motore di elaborazione di file JavaScript Object Notation (JSON) accelerato su GPU, che esemplifica come GrCUDA possa migliorare le attività di parsing e manipolazione dei dati grezzi, prevalenti nell’informatica biomedica. La seconda applicazione consiste in un allineatore di sequenze nucleotidiche a grafi genomici, che dimostra come GrCUDA sia in grado di gestire complessi sistemi di elaborazione nell’ambito dell’analisi genomica.
In conclusione, questa tesi sottolinea l’importanza di esporre l’utilizzo di GPU nei linguaggi di programmazione di alto livello per affrontare le sfide computazionali dell’informatica biomedica. Migliorando il framework GrCUDA, questo lavoro fornisce una soluzione innovativa che consente a ricercatori e professionisti di sfruttare appieno il potenziale delle GPU nello sviluppo di applicazioni nel campo biomedicale. Attraverso applicazioni concrete e risultati empirici, questa tesi evidenzia l’impatto trasformativo dell’accelerazione su GPU sul panorama dell’informatica biomedica e, conseguentemente, della medicina di precisione.In recent years, the field of biomedical informatics has witnessed an explosion in data volume and complexity, demanding innovative approaches to accelerate computational tasks. Graphics Processing Units (GPUs) have emerged as potent hardware accelerators, driving substantial performance gains in various domains. However, their adoption within biomedical informatics has been mainly limited to the deep learning domain, due to the availability of libraries that mask the GPU computation. This is mainly due to the scarce integration of GPUs with high-level pro- programming languages, such as R or Python, commonly used in the biomedical context. This dissertation addresses the critical need to extend GPU utilization to such high-level languages in the context of biomedical informatics.
The first part of this thesis presents a series of applications that leverage GPUs to expedite the training of deep learning models for different tasks, namely drug repurposing, dementia detection, and lung cancer identification. By harnessing the parallel processing capabilities of GPUs, significant reductions in training times are achieved, thereby facilitating quicker iterations and enhancing the pace of research and clinical decision-making. Nonetheless, the aforementioned applications involve other compute-intensive processing steps that could benefit from heterogeneous hardware acceleration. A bridge between high-level languages and GPU programming is imperative to enable researchers and practitioners to exploit the full potential of GPU hardware in biomedical informatics applications.
To address such a need, the centerpiece of this dissertation presents an innovative framework to simplify GPU programming, named GrCUDA. Initially developed by NVIDIA and Oracle, GrCUDA serves as an intermediary layer that enables seamless access to GPU resources from the high-level programming languages supported by the polyglot GraalVM ecosystem. This thesis introduces a novel multi-GPU asynchronous scheduler for GrCUDA, which facilitates the development of multi-GPU applications by abstracting low-level GPU details and providing a high-level interface that is both efficient and user-friendly. Experimental results prove that the proposed scheduler transparently provides speedups comparable to what an expert programmer can achieve by hand, making multi-GPU computations easier to approach while minimizing performance compromises. Thus, the GrCUDA framework emerges as a crucial bridge, enabling biomedical informatics researchers to harness GPUs’ substantial computational capabilities without compromising programming ease and language flexibility.
Building upon the GrCUDA framework, the final part of the thesis showcases two applications that underscore its utility. The first application introduces GPJSON, a GPU-accelerated JavaScript Object Notation (JSON) processing engine, exemplifying how GrCUDA can enhance data parsing and manipulation tasks prevalent in biomedical informatics. The second application presents a sequence-to-graph aligner tailored for genomics ap- plications, demonstrating how GrCUDA can handle complex systems inherent to the domain.
In conclusion, this dissertation advocates for the integration of GPUs into high-level programming languages to address the computational challenges in biomedical informatics. By enhancing the GrCUDA framework, this work provides a novel solution that empowers researchers and practitioners to harness the full potential of GPUs while developing applications for critical tasks within the biomedical field. Through concrete applications and empirical results, this thesis underscores the transformative impact of GPU acceleration on the landscape of biomedical informatics and, consequently, of precision medicine.DIPARTIMENTO DI ELETTRONICA, INFORMAZIONE E BIOINGEGNERIAComputer Science and Engineering36MARTINENGHI, DAVIDEPIRODDI, LUIG
Complex Data Imputation by Auto-Encoders and Convolutional Neural Networks—A Case Study on Genome Gap-Filling
No full textMissing data imputation has been a hot topic in the past decade, and many state-of-the-art works have been presented to propose novel, interesting solutions that have been applied in a variety of fields. In the past decade, the successful results achieved by deep learning techniques have opened the way to their application for solving difficult problems where human skill is not able to provide a reliable solution. Not surprisingly, some deep learners, mainly exploiting encoder-decoder architectures, have also been designed and applied to the task of missing data imputation. However, most of the proposed imputation techniques have not been designed to tackle “complex data”, that is high dimensional data belonging to datasets with huge cardinality and describing complex problems. Precisely, they often need critical parameters to be manually set or exploit complex architecture and/or training phases that make their computational load impracticable. In this paper, after clustering the state-of-the-art imputation techniques into three broad categories, we briefly review the most representative methods and then describe our data imputation proposals, which exploit deep learning techniques specifically designed to handle complex data. Comparative tests on genome sequences show that our deep learning imputers outperform the state-of-the-art KNN-imputation method when filling gaps in human genome sequences
Bridging Research and Entrepreneurship: An Innovative Educational and Experiential Approach
No full textNECSTLab at Politecnico di Milano is a pioneering research laboratory that integrates cutting-edge academic research with entrepreneurial ventures. Its mission is to bridge the gap between research and real-world applications, encouraging students and researchers to consider the societal impact of their innovations. NECSTLab promotes an interdisciplinary approach, combining technical expertise with business acumen to drive innovation. The lab's strategy includes fostering an entrepreneurial mindset through courses that equip students with the tools to transform research into viable products or services. This paper introduces an innovative approach to address the challenges of transitioning academic research into market commercialization. By focusing on early-stage collaboration between researchers and industry, and incorporating market analysis, prototype development, and business model validation, this process supports the commercialization of research. The proposed pipeline has been implemented and validated within the NECSTLab environment, demonstrating its efficacy in fostering entrepreneurship and translating academic research into successful commercial ventures. This is exemplified by case studies showcasing the pipeline's effectiveness in transforming innovative research into market-ready solutions while fostering entrepreneurial initiatives and driving impactful innovation
Design and implementation of a user-friendly platform for graph based genome analysis
No full textLAUREA MAGISTRALELe NGS hanno portato a un aumento della quantità di dati genomici, permettendo nuovi tipi di studio che utilizzano materiale genetico da vari membri della stessa specie, famiglia o ambiente. Per fornire un processo di analisi più efficiente, nuove operazioni richiedono nuovi paradigmi informatici. Essendo utilizzabili per esprimere eterogeneità sia intra- che inter-individuale, le rappresentazioni basate su grafi dei dati genetici sono state recentemente suggerite come un’alternativa più efficace alle stringhe.Questo cambio di paradigma sembra in grado di consentire la scalabilità per la pangenomica, lo studio di numerosi genomi insieme. A causa della novità di questo approccio, pipeline standardizzate e consolidate per l’analisi dei grafi genomici faticano ancora ad emergere e il risultato è una realtà di lavoro e ricerca estremamente frammentata. Lo scopo del progetto descritto in questa tesi è stato quello di offrire una piattaforma per la costruzione, l’analisi e la visualizzazione di grafi genomici. La soluzione proposta è costituita da un’applicazione web che integra diversi strumenti al fine di consentire l’esecuzione di una pipeline di analisi del genoma su grafi.NGS technologies have led to an increase in the amount of genomic data generated, enabling new types of studies that use genetic material from various members of the same species, family, or environment. To provide a more efficient analysis process, new operations require new computing paradigms. Being usable for expressing both intra-individual and inter-individual heterogeneity, graph-based representations of genetic data have recently been suggested as a more efficient alternative to strings. This paradigm shift has the potential to enable the appropriate scalability of pangenomics, that is the study of numerous genomes together. Because of the novelty of this approach, standardized and established pipelines for the analysis of genomic graphs still struggle to emerge, and the result is a highly fragmented scenario of tools and research efforts. The purpose of the project described in this thesis is to provide a platform for the construction, analysis and visualization of genome graphs. The proposed solution consists of a web application that integrates several tools to enable the execution of a genome analysis pipeline on graphs in a fast, easy, and intuitive way
On the optimization of sequence alignment to cyclic genome graphs
No full textLAUREA MAGISTRALECon la diffusione delle tecnologie di sequenziamento di nuova generazione (NGS) si è verificato un incremento nella quantità di dati genomici generati che ha permesso una serie di nuovi tipi di studi, che coinvolgono materiale genetico proveniente da diversi individui all'interno della stessa specie, famiglia o ambiente.
Ciò richiede nuovi paradigmi computazionali per garantire un processo di analisi più intuitivo e rapido.
Recentemente, l'utilizzo di grafi per la rappresentazione dei dati genomici é stata proposta come un alternativa più efficiente e flessibile alle stringhe, perché sono adatti a rappresentare la variabilità intra-individuale e inter-individuale.
Poiché questo cambiamento di paradigma è attualmente in corso, l'allineamento delle reads ai grafi genomici è un contesto fertile per la ricerca, in quanto offre molte sfide in termini di miglioramento di precisione ed efficienza degli algoritmi di allineamento.
Pertanto, l'obiettivo di questo progetto è l'implementazione di un algoritmo di allineamento di sequenze a grafi basato sul metodo di ricerca del percorso più breve, presentato nell'articolo "On the Complexity of Sequence to Graph Alignment", il quale fornisce una descrizione teorica di un algoritmo che consente l'allineamento in tempo O(|V|+m|E|), laddove m indica la dimensione della query, mentre V e E indicano i set di vertici e archi del grafo genomico.
In questo lavoro, forniamo la prima implementazione completa e pronta all'uso di tale algoritmo, rispettanto gli standard per la visualizzazione dei risultati.
Per ottimizzare il tempo di calcolo è stata implementata un'euristica a banda adattiva.
La soluzione presenta due versioni parallelizzate su due architetture diverse (CPU e GPU) di cui sono stati analizzati vantaggi e svantaggi.
Per validare il lavoro svolto, sono stati eseguiti dei test sperimentali sul genoma virale del SARS-CoV-2 e su due zone del genoma umano. Da questi, si evince come la soluzione rispetti la complessità temporale teorica e quanto livello di accuratezza raggiunto sia elevato.
Infine sono proposte alcune idee per poter migliorare ulteriormente le performance di questa soluzione e per aumentarne le funzionalità.The spreading of NGS technologies has produced an explosion in the amount of genomic data generated enabling a series of new kinds of studies, involving genetic material from different individuals of the same species, family, or environment.
New kinds of studies require new computational paradigms to ensure a more intuitive and rapid analysis process.
Recently, graph-based representations of genomic data have been proposed as a more efficient and flexible alternative to strings, because they are suitable to represent intra-individual and inter-individual variability.
As this change of paradigm is currently taking place, the alignment of sequencing reads to genome graphs is a fertile context for research, offering lots of challenges in terms of accuracy and efficiency of the alignments.
Therefore, the goal of this project is the implementation of a sequence-to-graph alignment algorithm based on the shortest-path method, presented in the article "On the Complexity of Sequence to Graph Alignment''.
This article provides a theoretical description of an innovative algorithm that allows the alignment of genomic query sequences to genome graphs in O(|V|+m|E|) time, where m denotes the query size, and V and E denote, respectively, the vertices and edges sets of the graph.
This thesis work provides the first implementation of this algorithm in a complete and ready-to-use tool in compliance with the standard input and output file formats.
To optimize the execution time, an adaptive bandwidth heuristic is proposed.
Moreover, the parallelization of the algorithm on two different architectures (CPU and GPU) is investigated, to enhance the pros and cons of both in terms of execution time and memory footprint.
Experimental results on SARS-CoV-2 and human genomic data show that the proposed implementations respect the theoretical complexity of the algorithm, and they achieve maximum alignment accuracy while offering the opportunity to tune the algorithm behavior with custom scoring matrices.
Finally, this document discusses the next development steps required to optimize even further the performance of the proposed implementations, and enrich them with additional functionalities
A Graph Machine Learning approach to Automatic Dementia Detection
No full textDementia is a term used to refer to a wide range of diseases that cause a decline in cognitive abilities. This decline is severe enough to impair daily life and it is extremely complex to diagnose in its early stages. In recent years multiple Natural Language Processing solutions have been proposed to automatically detect dementia. One of the main approaches to this problem is based on extracting manually engineered features from a set of patients' conversations and feeding them to traditional Machine Learning models. These features can be divided into very different groups, and we can define specific relations that connect one feature to the other. Thus, we introduce a new way to approach the problem by organizing all the extracted features in a graph structure and using Graph Machine Learning to detect dementia. We validate our method using a well-established score regression task and a newly proposed multi-class classification task. This new task is based on the mapping between the Mini-Mental State Examination score and multiple dementia severity levels. Compared to traditional Machine Learning, our Graph Machine learning technique achieves a relative increase in performance between 2.9% and 8% for the regression task, and between 4.4% and 7.9% for the classification task
On the Automation of Radiomics-Based Identification and Characterization of NSCLC
No full textProper detection and accurate characterization of Non-Small Cell Lung Cancer (NSCLC) are an open challenge in the imaging field. Biomedical imaging is fundamental in lung cancer assessment and offers the possibility of calculating predictive biomarkers impacting patients' management. Within this context, radiomics, which consists of extracting quantitative features from digital images, shows encouraging results for clinical applications, but the sub-optimal standardization of the procedure and the lack of definitive results are still a concern in the field. For these reasons, this work proposes the design and development of LuCIFEx, a fully-automated pipeline for non-invasive in-vivo characterization of NSCLC, aiming to speed up the analysis process and enable an early diagnosis of the tumor.LuCIFEx pipeline relies on routinely acquired [18F]FDG-PET/CT images for the automatic segmentation of the cancer lesion, allowing the computation of accurate radiomic features, then employed for cancer characterization through Machine Learning algorithms. The proposed multi-stage segmentation process can identify the lesion with a mean accuracy of 94.2±5.0%. Finally, the proposed data analysis pipeline demonstrates the potential of PET/CT features for the automatic recognition of lung metastases and NSCLC histological subtypes, while highlighting the main current limitations of the radiomic approach
On the optimization of GWFA algorithm: enabling real-case applications supporting alignment backtracking
No full textThe Human Pangenome Reference Consortium (HPRC) proved that pangenome graphs represent a population's genetic variability more efficiently and accurately than linear references. Graphs can intrinsically encode variations as alternative paths inside a directed set of sequence nodes connected by edges. Despite their higher complexity, graph-based genome analysis pipelines are gaining significant interest, and the first sequence-to-graph aligners have already shown improvements in semi-global alignment. However, in pangenomics studies, the global alignment of long reads is fundamental for identifying structural variations and haplotype phasing. In this context, the Graph Wavefront Alignment (GWFA) algorithm emerged as the fastest strategy for aligning long reads to genomic graphs. However, the available GWFA implementation does not support alignment backtracking, a crucial feature in real-case studies. In this paper, we propose a new open-source1 implementation of the GWFA algorithm that computes and reports the complete traceback in the standard GAF format. Our work achieves a 20× speedup in execution time compared to the state-of-the-art tool GraphAligner and competitive memory usage
- …
