Algorithms for analyzing genetic variability from Next-Generation Sequencing data

DNA contains the genetic information that is essential for the correct development of any organism. Being able to investigate DNA is of utmost importance for analyzing the reasons behind diseases and for improving the quality of life. Development of DNA sequencing technologies has revolutionized the way this kind of investigation is performed. Due to the huge amount of sequencing data available, nowadays computer science plays a key role in their analysis. Luckily, in many applications, the biological information contained in a DNA molecule can be represented as a string in which each character represents a nucleotide. Strings are a well-known and well-studied notion in computer science and therefore it is possible to exploit the huge literature related to storing and processing strings for improving the analysis of DNA. Within this context, this thesis focuses on two specific problems arising from the analysis of sequencing data: the study of transcript variability due to alternative splicing and the investigation of genetic variability among different individuals due to small variations such as Single Nucleotide Polymorphisms and indels. Regarding both these problems, we investigate two novel computational approaches by devising original strategies and we prove their efficacy by comparing them with the most used state-of-the-art approaches. In both these areas, our focus is on the development of bioinformatics tools that combine accurate algorithms with efficient data structures. The first problem we tackle is the detection of alternative splicing events from RNA-Seq data. Alternative splicing plays an important role in many different life aspects, from the correct evolution of an individual to the development of diseases. Differently from current techniques that rely on the reconstruction of transcripts or on the spliced alignment of RNA-Seq reads against a reference genome, we investigate an alternative algorithmic approach that exploits the novel notion of alignment against a splicing graph. We implemented such an approach in a tool, called ASGAL, that aligns a RNA-Seq sample against the splicing graph of a gene and then detects the alternative splicing events supported by the sample by comparing the alignments with the gene annotation. ASGAL is the first tool that aligns reads against a splicing graph and that is able to detect novel alternative splicing events even when only a single transcript per gene is supported by the sample. The results of our experiments show the usefulness of aligning reads against a splicing graph and prove the ability of the proposed approach in detecting alternative splicing events. The second problem we tackle is the genotyping of a set of known Single Nucleotide Polymorphisms and indels from sequencing data. An in-depth analysis of these variants allows to understand genetic variability among different individuals of a population and their genetic risks factors for diseases. Standard pipelines for variant discovery and genotyping include read alignment, a computationally expensive procedure that is too time consuming for typical clinical applications. When variant discovery is not desired, it is possible to avoid read alignment by genotyping only the set of known variants that are already established to be of medical relevance. To solve this problem, we devised a novel alignment-free algorithmic approach and we implemented it in a bioinformatic tool, called MALVA. MALVA is the first alignment-free approach that is able to genotype SNPs, indels, and multi-allelic variants. Thanks to its alignment-free strategy, MALVA requires one order of magnitude less time than alignment-based pipelines to genotype a donor individual while achieving similar accuracy. Remarkably, on indels it provides even better results than the most widely adopted approaches.

Il DNA contiene l'informazione genetica che è essenziale per il corretto sviluppo di qualsiasi organismo. Essere in grado di analizzare il DNA risulta indispensabile per comprendere le cause di malattie e tumori e per migliorare la qualità delle nostre vite. Lo sviluppo delle tecniche di sequenziamento del DNA ha rivoluzionato il modo in cui queste analisi sono eseguite. A causa dell'immensa quantità di dati biologici disponibili, oggigiorno l'informatica gioca un ruolo fondamentale nella loro analisi. Fortunatamente in molte applicazioni l'informazione biologica contenuta in una molecola di DNA può essere rappresentata come una stringa nella quale ogni carattere rappresenta un nucleotide. Il concetto di stringa è molto studiato in informatica ed è possibile sfruttare l'estesa letteratura relativa alla memorizzazione e all'analisi di stringhe per migliorare lo studio del DNA. In questo contesto, questa tesi si focalizza su due problemi che emergono dall'analisi di dati di sequenziamento: lo studio della variabilità trascrittomica dovuta allo splicing alternativo e l'analisi della variabilità genetica dovuta a variazioni genetiche quali Single Nucleotide Polymorphisms e indels. Riguardo entrambi i problemi, investighiamo due originali approcci computazionali e ne dimostriamo l'efficacia confrontandoli con i tools più utilizzati nel relativo stato dell'arte. Il nostro obiettivo è lo sviluppo di tool bioinformatici che combinano algoritmi accurati con strutture dati efficienti. Il primo problema che affrontiamo è l'identificazione di eventi di splicing alternativo a partire da dati RNA-Seq. Lo splicing alternativo gioca un ruolo fondamentale in molti aspetti della vita, dal corretto sviluppo di un individuo al sorgere di malattie. Diversamente dagli approcci proposti in letteratura che si basano sulla quantificazione di trascritti o sull'allineamento spliced contro un genoma di riferimento, proponiamo un approccio algoritmico alternativo che sfrutta l'originale concetto di allineamento a un grafo di splicing. Abbiamo implementato il nostro approccio nel tool ASGAL che allinea un sample di RNA-Seq contro il grafo di splicing di un gene e identifica gli eventi di splicing alternativo supportati dal sample andando a confrontare questi ultimi con l'annotazione del gene. ASGAL è il primo tool che allinea RNA-Seq reads a un grafo di splicing e che è in grado di identificare eventi novel di splicing anche quando un singolo trascritto per gene è supportato dal sample in input. I risultati della nostra sperimentazione dimostrano l'utilità di allineare a un grafo di splicing e la capacità del nostro tool nell'identificare eventi di splicing alternativo. Il secondo problema che affrontiamo è la genotipizzazione di un insieme di varianti note (SNPs e indels) a partire da dati di sequenziamento. Un'approfondita analisi di queste variazioni è indispensabile per comprendere la variabilità genetica fra gli individui di una popolazione e il loro fattore di rischio genetico. Gli approcci proposti in letteratura per identificare e genotipizzare varianti includono l'allineamento delle reads, una procedura che risulta computazionalmente troppo onerosa per le tipiche applicazioni cliniche. Quando non si è interessati alla scoperta di nuove varianti, è possibile evitare lo step di allineamento andando a genotipizzare solo un insieme di varianti già note e per le quali è stata già dimostrata una certa rilevanza medica. Per risolvere questo problema, abbiamo ideato un nuovo approccio alignment-free e lo abbiamo implementato nel tool MALVA. MALVA è il primo approccio alignment-free che è in grado di genotipizzare SNPs, indels e varianti multi-alleliche. Grazie alla strategia alignment-free, MALVA è molto più veloce degli approcci basati sull'allineamento, esibendo comunque un'accuratezza simile. Inoltre, rispetto agli approcci più utilizzati in letteratura, MALVA risulta molto più accurato nella genotipizzazione degli indels.