Seeding basato su paradigma pigeonhole per allineamento su grafi pangenomici

Marco Santambrogio (marco DOT santambrogio AT polimi DOT it)

Beatrice Branchini (beatrice DOT branchini AT polimi DOT it)

Mirko Coggi (mirko DOT coggi AT polimi DOT it)

Pangenomics, Sequence Alignment, Graph-Based Seeding, Pangenome Graphs, Pigeonhole Principle, Structural Variation, Bioinformatics Algorithms

quantum computing, MATLAB

La crescente disponibilità di dati genomici e l’adozione di rappresentazioni pangenomiche creano nuove sfide per il mapping e l’allineamento delle sequenze. I metodi di seeding tradizionali, progettati per riferimenti lineari, mostrano limiti significativi quando applicati a grafi pangenomici complessi: sensibilità ridotta, problemi di scalabilità e difficoltà nella gestione delle varianti strutturali. Questo progetto propone l’implementazione di un seeder per grafi pangenomici basato sul paradigma del pigeonhole. L’obiettivo è migliorare sensibilità ed efficienza nell’allineamento delle sequenze. L’approccio divide le sequenze in segmenti che, anche in presenza di un numero massimo di errori, garantiscono almeno un match esatto tra query e riferimento. Il seeder sarà integrato con GINTONIC, un tool che effettua il seeding direttamente su grafo pangenomico, permettendo di operare nativamente su rappresentazioni genomiche complesse e varianti strutturali.

.