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

{{:matematica:asd:asd_23:pangraph.jpg?400|}}

**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:

<file>
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
</file>

In questo grafo \( G \), analizziamo i cammini possibili e verifichiamo se il pattern \( P = TTCA \) è presente in una delle sequenze ottenute.

{{:matematica:asd:asd_23:adj.jpg?400|}}


**Riferimenti**
  * 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]]
  * 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]]