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 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.

II. Analisi dei Cammini nel 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.
• Se ci sono più sorgenti o destinazioni, selezionarne una specifica per l'analisi.

III. Ricerca di Cammini con DFS:

• Eseguire una ricerca in profondità (DFS) per trovare tutti i cammini da una sorgente a una destinazione nel grafo.
• Ignorando l'array booleano “visitato” poiché il grafo è aciclico, usare un array \( S \) di caratteri di appoggio.
• 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 \).)

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 \).

V. Calcolo delle Frequenze dei K-mer:

• Identificare la frequenza dei K-mer in un pangenome graph \( G \).
• 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 \).

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
• Data set: example.gfa, drb1.gfa, chrY.gfa, chrX.gfa