On the optimization of sequence alignment to cyclic genome graphs

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.

Con 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à.