Toward efficient and accurate sequence-to-graph alignment: the AlDente approach

High-throughput sequencing has transformed genomics, producing data at population, clinical, and environmental scale. To analyze such diversity without the distortions of a single linear reference, genome graphs model alternative alleles and structural variation directly. In this setting, sequence-to-graph alignment (S2GA) is pivotal but difficult: the graph’s combinatorics inflate the search space, so accuracy, runtime, and memory must be balanced with care. This thesis introduces AlDente, a multithreaded S2GA aligner that builds on three heuristics originally proposed in POASTA—A* for exact, goal-directed extension; depth-first search (DFS) to rapidly enumerate candidate paths; and superbubble pruning to avoid redundant traversal in locally acyclic regions. AlDente augments this foundation with X-drop termination to abandon unpromising branches early and an adaptive bandwidth policy that focuses dynamic programming where it most influences the score. The implementation emphasizes cache efficiency and thread-local memory to sustain parallel throughput. Under a standardized evaluation across multiple graphs and both short- and long-read regimes, AlDente delivers higher alignment accuracy on several datasets while preserving competitive runtime and memory usage; on short reads it markedly reduces wall-clock time and scales effectively across many CPU threads. These results show that combining POASTA’s A*, DFS, and superbubble pruning with X-drop and adaptive banding yields an exact yet practical approach to S2GA. The thesis closes with avenues for improvement, including seed-and-extend integration, topology-aware chaining, and GPU acceleration of banded extension.

Il sequenziamento ad alta processività ha rivoluzionato la genomica, generando dati a scala di popolazione, clinica e ambientale. Per analizzare questa diversità senza i limiti di un riferimento lineare unico, i grafi genomici modellano direttamente alleli alternativi e varianti strutturali. In tale contesto, l’allineamento sequenza–grafo (S2GA) è centrale ma impegnativo: la complessità combinatoria del grafo amplia lo spazio di ricerca, imponendo un delicato equilibrio tra accuratezza, tempo di esecuzione e memoria. Questa tesi presenta AlDente, un allineatore S2GA multithread che si fonda su tre euristiche introdotte in POASTA: A* per un’estensione esatta e guidata all’obiettivo; ricerca in profondità (DFS) per enumerare rapidamente i cammini candidati; e pruning dei superbubble per evitare esplorazioni ridondanti in regioni localmente acicliche. AlDente integra inoltre lo X-drop per interrompere precocemente rami poco promettenti e una larghezza di banda adattiva che concentra la programmazione dinamica dove il punteggio viene maggiormente influenzato. L’implementazione privilegia efficienza di cache e memoria locale al thread per sostenere l’esecuzione parallela. In una valutazione standardizzata su più grafi e su letture corte e lunghe, AlDente ottiene un’accuratezza di allineamento superiore in diversi dataset mantenendo tempi e memoria competitivi; sulle letture corte riduce sensibilmente il tempo al risultato e scala efficacemente su molti thread CPU. I risultati dimostrano che la combinazione di A*, DFS e pruning dei superbubble di POASTA con X-drop e banding adattivo offre un approccio esatto ma pratico a S2GA. La tesi si conclude delineando sviluppi futuri quali integrazione seed-and-extend, chaining consapevole della topologia e accelerazione GPU dell’estensione bandita.