Accelerazione dell’allineamento di sequenze a grafi genomici su GPU

Marco Santambrogio (marco DOT santambrogio AT polimi DOT it)

Referente del progetto

CUDA, GPU, Grafi, Genomica

Nell’analisi genomica, molte sequenze lineari della stessa specie possono essere integrate in un grafo diretto, noto come grafo pangenomico, il quale risulta particolarmente utile per studiare le variazioni genomiche. Una sfida fondamentale in questo contesto è l’allineamento sequenza-grafo, un processo che confronta una nuova sequenza con tutti i possibili percorsi nel grafo per identificare il percorso ottimale con la distanza minima. Tuttavia, a causa dell’enorme quantità di dati coinvolti, questa procedura è estremamente onerosa dal punto di vista computazionale, creando un collo di bottiglia nelle pipeline di analisi genomica. Mentre sono stati sviluppati algoritmi efficienti per accelerare l’allineamento sequenza-grafo, acceleratori hardware, come le GPU, sono diventati essenziali per raggiungere le prestazioni richieste e mitigare le limitazioni computazionali. Questo progetto mira a sviluppare il primo allineatore sequenza-grafo accelerato su GPU utilizzando un approccio Partial Order Alignment con euristica a banda fissa.