| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| matematica:asd:asd_23:progetto_21 [18/05/2024 alle 03:05 (10 mesi fa)] – Roberto Grossi | matematica:asd:asd_23:progetto_21 [03/10/2024 alle 13:11 (5 mesi fa)] (versione attuale) – Roberto Grossi |
|---|
| ====== Progetto di ASD 2023/2024: Creazione e analisi di un Pangenome Graph ====== | ====== Progetto a.a. 2023/2024: Creazione e analisi di un Pangenome Graph ====== |
| |
| Il progetto riguarda la costruzione e l'analisi di un pangenome graph, che permette di rappresentare e analizzare variazioni genetiche all'interno di un insieme di genomi in bioinformatica. Utilizzando il formato //GFA (Graphical Fragment Assembly)//, ci proponiamo di leggere file GFA e creare un grafo etichettato, nonché di eseguire diverse operazioni su di esso. | Il progetto riguarda la costruzione e l'analisi di un pangenome graph, che permette di rappresentare e analizzare variazioni genetiche all'interno di un insieme di genomi in bioinformatica. Utilizzando il formato //GFA (Graphical Fragment Assembly)//, il progetto richiede di leggere file GFA e creare un grafo etichettato, nonché di eseguire diverse operazioni su di esso. |
| |
| {{:matematica:asd:asd_23:pangraph.jpg?400|}} | {{:matematica:asd:asd_23:pangraph.jpg?400|}} |
| |
| I. **Lettura e Creazione del Grafo:** | I. **Lettura e Creazione del Grafo:** |
| * Leggere un file GFA e creare un grafo etichettato e orientato, utilizzando le liste di adiacenza (vector in C++). | * Leggere un file GFA e creare un grafo \(G\) etichettato e orientato, utilizzando le liste di adiacenza (vector in C++). |
| * Etichettare i nodi e gli archi del grafo in base alle informazioni fornite nel file GFA. | * Etichettare i nodi e gli archi di \(G\) in base alle informazioni fornite nel file GFA. |
| |
| II. **Analisi dei Cammini nel Grafo:** | II. **Analisi del Grafo:** |
| * Considerare tutti i possibili cammini da una sorgente (grado d'ingresso a zero) a una destinazione (grado d'uscita a zero) senza materializzarli tutti. | * Verificare se il grafo \(G\) sia ciclico: in tal caso effettuare una visita DFS e rimuovere gli archi all'indietro (//back edge//) in modo che \(G\) diventi un DAG (directed acyclic graph). |
| * Se ci sono più sorgenti o destinazioni, selezionarne una specifica per l'analisi. | * Considerare una sorgente \(s\) (grado d'ingresso a zero) a una destinazione \(t \) (grado d'uscita a zero). Se ci sono più sorgenti o destinazioni, selezionarne una specifica per l'analisi. |
| |
| III. **Ricerca di Cammini con DFS:** | III. **Ricerca di Pattern sui Cammini del DAG:** |
| * Utilizzare una ricerca in profondità (DFS) per trovare tutti i cammini da una sorgente a una destinazione nel grafo. | * Eseguire una ricerca in profondità (DFS) nel DAG \(G\) a partire dalla sorgente \(s\) per trovare tutti i cammini che partono da \(s\) e arrivano in \(t\). |
| * Ignorare l'array booleano "visitato" poiché il grafo è aciclico e utilizzare un array \( S \) di char di appoggio. | * Attenzione che il numero di tali cammini può essere esponenziale, per cui verificare questo solo su un DAG piccolo. |
| * Modificare la visita ricorsiva \( DFS(u) \) vista a lezione, in modo da aggiungere e rimuovere la stringa del nodo \( u \) quando rispettivamente \( u \) viene visitato per la prima volta e quando la visita in \( u \) termina. (Nota: quando \( u \) è nodo di destinazione, quindi con grado di uscita pari a zero, la sequenza corrispondente al cammino dalla sorgente si trova in \( S \).) | * Ignorare l'array booleano "visitato" poiché il grafo è aciclico e usare un array \( S \) di caratteri di appoggio: modificare la visita ricorsiva DFS vista a lezione, in modo da aggiungere e rimuovere la stringa del nodo corrente \( u \) nella DFS quando, rispettivamente, \( u \) viene visitato per la prima volta e quando la visita in \( u \) termina. (Nota: quando \( u = t\), la sequenza corrispondente al cammino attuale da \(s \) a \(t\) si trova in \( S \).) |
| | * Data una sequenza pattern \( P \) di lunghezza \( K \), verificare se è contenuta in una delle sequenze generate come sopra. In tal caso, \( P \) è chiamata //K-mer//. |
| IV. **Verifica di Pattern nella Sequenza:** | |
| * Data una sequenza pattern \( P \) di lunghezza \( K \), verificare se è contenuta in una delle sequenze generate durante la ricerca. In tal caso, \( P \) è chiamata //K-mer//. | |
| * Utilizzare tecniche di rolling hash per calcolare l'hash delle porzioni di lunghezza \( K \) nella sequenza (hash visto a lezione) e confrontarle con l'hash del pattern \( P \). | * Utilizzare tecniche di rolling hash per calcolare l'hash delle porzioni di lunghezza \( K \) nella sequenza (hash visto a lezione) e confrontarle con l'hash del pattern \( P \). |
| |
| V. **Calcolo delle Frequenze dei K-mer:** | V. **Facoltativo: Calcolo delle Frequenze dei K-mer:** |
| * Identificare la frequenza dei K-mer in un pangenome graph \( G \). | * Calcolare la frequenza di ogni K-mer in un pangenome graph \( G \), definita come il numero delle sue occorrenze. Ad esempio, per \( P = ATA \), la frequenza è 2. |
| * Calcolare la frequenza di ogni K-mer e il numero delle sue occorrenze. Ad esempio, per \( P = ATA \), la frequenza può essere 2. | |
| * Riportare i 10 K-mer più frequenti in \( G \). | * Riportare i 10 K-mer più frequenti in \( G \). |
| |
| |
| **Riferimenti** | **Riferimenti** |
| * Spiegazioni dettagliate del progetto: canale Teams di questo insegnamento | * Spiegazioni video dettagliate del progetto: [[https://unipiit.sharepoint.com/:v:/s/a__td_61736/EbOY8rWsbG1AgXMigKfIyVMBvcy5_yO8rCcymObkiSGCwA?e=gdjDou&nav=eyJyZWZlcnJhbEluZm8iOnsicmVmZXJyYWxBcHAiOiJTdHJlYW1XZWJBcHAiLCJyZWZlcnJhbFZpZXciOiJTaGFyZURpYWxvZy1MaW5rIiwicmVmZXJyYWxBcHBQbGF0Zm9ybSI6IldlYiIsInJlZmVycmFsTW9kZSI6InZpZXcifX0%3D| video su canale teams]] |
| * Documentazione del formato GFA: [[http://gfa-spec.github.io/GFA-spec/GFA1.html]] | * Documentazione del formato GFA: [[http://gfa-spec.github.io/GFA-spec/GFA1.html]] |
| * Data set: [[https://github.com/jltsiren/gbwt-rs/blob/main/test-data/example.gfa|example.gfa]], [[https://s3-us-west-2.amazonaws.com/human-pangenomics/pangenomes/freeze/freeze1/pggb/chroms/chrY.hprc-v1.0-pggb.gfa.gz|chrX.gfa]], [[https://s3-us-west-2.amazonaws.com/human-pangenomics/pangenomes/freeze/freeze1/pggb/chroms/chrX.hprc-v1.0-pggb.gfa.gz|chrX.gfa]] | * Data set: [[https://github.com/jltsiren/gbwt-rs/blob/main/test-data/example.gfa|example.gfa]], [[https://github.com/pangenome/odgi/blob/master/test/DRB1-3123_unsorted.gfa|drb1.gfa]], [[https://s3-us-west-2.amazonaws.com/human-pangenomics/pangenomes/freeze/freeze1/pggb/chroms/chrY.hprc-v1.0-pggb.gfa.gz|chrY.gfa]], [[https://s3-us-west-2.amazonaws.com/human-pangenomics/pangenomes/freeze/freeze1/pggb/chroms/chrX.hprc-v1.0-pggb.gfa.gz|chrX.gfa]] |
| |
