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), il progetto richiede di leggere file GFA e creare un grafo etichettato, nonché di eseguire diverse operazioni su di esso.
Obiettivi del Progetto
I. Lettura e Creazione del Grafo:
- 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 di \(G\) in base alle informazioni fornite nel file GFA.
II. Analisi del Grafo:
- 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).
- 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 Pattern sui Cammini del DAG:
- 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\).
- Attenzione che il numero di tali cammini può essere esponenziale, per cui verificare questo solo su un DAG piccolo.
- 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.
- Volendo, 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. Facoltativo: Calcolo delle Frequenze dei K-mer:
- 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.
- Riportare i 10 K-mer più frequenti in \( G \).
Struttura del GFA
Il formato GFA permette di rappresentare graficamente l'assemblaggio di frammenti genomici. Ogni linea nel file GFA ha un campo specifico:
- H (Header): La prima linea che indica il tipo di formato.
- S (Segment): Linee che descrivono segmenti di DNA.
- L (Link): Linee che descrivono collegamenti tra segmenti.
- P (Path): Linee che descrivono cammini attraverso segmenti.
- L (Walk): Linee che descrivono cammini attraverso segmenti non sovrapposti.
Utilizzare solo S per i nodi e L per gli archi.
Esempio di Analisi
Consideriamo un grafo con i seguenti nodi e archi rappresentati in formato GFA:
H VN:Z:1.0 S s11 GAT S s12 T S s13 A S s14 CAG S unused GAA S s15 A S s16 T S s17 TA L s11 + s12 + * L s11 + s13 + * L s12 + s14 + * L s13 + s14 + * L s14 + s15 + * L s14 + s16 + * L s15 + s17 + * L s16 + s17 + * P A s11+,s12+,s14+,s15+,s17+ *,*,*,* W sample 1 A 0 10 >s11>s12>s14>s15>s17 W sample 2 A 0 10 >s11>s13>s14>s16>s17
In questo grafo \( G \), analizziamo i cammini possibili e verifichiamo se il pattern \( P = TTCA \) è presente in una delle sequenze ottenute.
Riferimenti
- Spiegazioni video dettagliate del progetto: video su canale teams
- Documentazione del formato GFA: http://gfa-spec.github.io/GFA-spec/GFA1.html