Docente
Marco Santambrogio (marco DOT santambrogio AT polimi DOT it)
Referente del progetto
Mirko Coggi (mirko DOT coggi AT polimi DOT it)
Keyword (max 3 separate da virgola)
Grafi, Genomica, Seeding, Benchmarking
Descrizione (max 500 caratteri)
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. Per ottimizzare la computazione di questo task sono state introdotte diverse tecniche di Seed&Extend che utilizzano una sorta di ancore nel grafo (chiamate seed) che, se trovano corrispondenza nelle nuove sequenze, aiutano a ridurre lo spazio di ricerca, limitando l’allineamento della sequenza ad una porzione del grafo originale. Tuttavia le tecniche di seeding proposte sono molto variegate e sfruttano strategie diverse che possono influenzare il risultato dell’allineamento finale. L’obbiettivo del progetto è quindi quello di studiare le peculiarità di ogni strategia, estrapolare le diverse implementazioni dai tool che le supportano e creare una benchmark suite che valuti le strategie su molteplici dataset, evidenziando punti di forza e debolezza.