Time and Space Efficient Data Structures For Computational Pangenomics

Computational pangenomics is an emerging research field in bioinformatics that comes from the idea of shifting away from the traditional concept of a linear reference genome, towards a representation that explicitly accounts for genetic variations across a large collection of individual genomes. This concept is known as the pangenome, that from a computational perspective, can be represented in different ways, for instance : a) as a (multi)set of binary sequences, i.e. a binary matrix, representing haplotypes and encoding the differences between a set of genomes and a reference genome, b) as the concatenation of all the genomes of the population, or c) as a node-labeled graph, where common substrings between genomes are merged into the same node label. In this Ph.D. thesis, we first address the former type of representation, i.e. the haplotype panel encoded as a set of binary sequences, which is typically indexed to support queries using the Positional Burrows–Wheeler Transform (PBWT). Inspired by recent advances in classical text indexing techniques, such as the well-known r-index, we have developed several data structures to efficiently build a run-length encoded PBWT (RLPBWT), allowing us to store the PBWT compactly while still supporting common string-to-matrix pattern-matching queries. This exploration also led to the development of the µ-PBWT, a variant of the RLPBWT that stores all the information necessary to address string-to-matrix pattern-matching problems efficiently, solving computational problems that currently require excessive space and time. Thanks to the µ-PBWT, we can index a haplotype panel using up to two orders of magnitude less memory than the original PBWT, enabling the analysis of large haplotype datasets. In this thesis, we will also describe how to use the µ-PBWT to solve a common biological problem, the genotype phasing problem, combinatorially in sublinear space. Moreover, we also highlight the advantages and limitations of using a combinatorial approach instead of common probabilistic approaches. We then focus on the pangenome graph, presenting gindex, a tool based on the Multidollar Burrows–Wheeler Transform that efficiently computes string-to-graph exact matches and scales better than state-of-the-art tools, up to human pangenomes. Despite being slower in queries, gindex supports arbitrary query lengths and addresses the main limitations of the most used pangenome graph indexes: high memory usage during indexing and limitation of query length, due to the underlying data structures. Finally, we address the biological problem of detecting and quantifying Alternative Splicing (AS) events using efficient graph-based models. After presenting ESGq, a non-pangenomic prototype, we introduce pantas, the first pangenome graph-based model for the detection and quantification of AS events. With pantas, we demonstrated that accounting for the genetic variability within the studied population improves the accuracy of AS event detection, showing that the use of pangenomes can effectively contribute to solving biological problems. Our results demonstrate that the use of a pangenome can enable new fundamental discoveries in biology and personalized medicine, showing great potential for Genome-Wide Association Studies (GWAS). Hence, given these computational results, we are confident that the development of pangenome-based tools will be essential in the near future for analyzing large-scale genomic data, enabling novel discoveries from both computational and biological perspectives.

La pangenomica computazionale è un campo di ricerca emergente della bioinformatica che nasce dall’idea di abbandonare il concetto tradizionale di genoma di riferimento lineare a favore di una rappresentazione che tenga conto delle variazioni genetiche presenti in un insieme di genomi. Questo concetto è noto come pangenoma e, da un punto di vista computazionale, può essere rappresentato in diversi modi, come: a) come (multi)insieme di sequenze binarie, ovvero una matrice binaria, che rappresenta aplotipi e codifica le differenze tra un insieme di genomi e un genoma di riferimento, b) come concatenazione di tutti i genomi della popolazione, oppure c) come grafo etichettato, in cui le sottostringhe comuni tra i genomi vengono unite nelle stesse etichette dei nodi. In questa tesi di dottorato, affrontiamo innanzitutto il primo tipo di rappresentazione, ovvero il pannello di aplotipi codificato come insieme di sequenze binarie, che viene tipicamente indicizzato per supportare le query utilizzando la Trasformata di Burrows-Wheeler Posizionale (PBWT). Ispirati dai recenti progressi nelle tecniche classiche di indicizzazione dei testi, come il noto r-index, abbiamo sviluppato diverse strutture dati per costruire in modo efficiente una run-length encoded PBWT (RLPBWT), memorizzando la PBWT in modo compatto, pur continuando a supportare le comuni query string-to-matrix. Questa ricerca ha portato anche allo sviluppo della µ-PBWT, una variante della RLPBWT che memorizza tutte le informazioni necessarie per affrontare in modo efficiente i problemi di pattern-matching string-to-matrix, risolvendo problemi computazionali che attualmente richiedono spazio e tempo eccessivi. Grazie alla µ-PBWT, possiamo indicizzare un pannello di aplotipi utilizzando fino a due ordini di grandezza in meno di memoria rispetto all’originale PBWT, consentendo l’analisi di grandi dataset di aplotipi. In questa tesi descriveremo anche come utilizzare la µ-PBWT per risolvere un comune problema biologico, quello del phasing di genotipi, in modo combinatorio in uno spazio sublineare. Inoltre, evidenzieremo anche i vantaggi e i limiti dell’utilizzo di un approccio combinatorio rispetto ai più comuni approcci probabilistici. Ci concentriamo poi sul grafo del pangenoma, presentando gindex, uno strumento basato sulla Trasformata di Burrows-Wheeler multidollaro che calcola in modo efficiente i match esatti tra stringhe e grafi e che scala meglio rispetto agli strumenti allo stato dell’arte, scalando su pangenomi umani. Nonostante sia più lento nelle query, gindex supporta query di lunghezza arbitraria e affronta le principali limitazioni degli indici per grafi più usati: l’elevato utilizzo di memoria durante l’indicizzazione e la limitazione della lunghezza delle query, causata dalle strutture dati sottostanti. Infine, affrontiamo il problema biologico dell’individuazione e della quantificazione degli eventi di splicing alternativo (AS) utilizzando modelli efficienti basati su grafi. Dopo aver presentato ESGq, un prototipo non pangenomico, introduciamo pantas, il primo modello basato su grafi del pangenoma per il rilevamento e la quantificazione degli eventi di AS. Con pantas, abbiamo dimostrato che tenere conto della variabilità genetica all’interno della popolazione studiata migliora l’accuratezza del rilevamento degli eventi di AS, mostrando che l’uso dei pangenomi può contribuire efficacemente alla risoluzione di problemi biologici. I nostri risultati dimostrano che l’uso del pangenoma può consentire nuove scoperte fondamentali nella biologia e nella medicina personalizzata, mostrando un grande potenziale per i Genome-Wide Association Studies. Pertanto, alla luce di questi risultati computazionali, siamo fiduciosi che lo sviluppo di strumenti basati sul pangenoma sarà essenziale nel prossimo futuro per l’analisi di dati genomici su larga scala, consentendo nuove scoperte sia dal punto di vista computazionale che biologico.