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.

Obiettivi del Progetto

I. Lettura e Creazione del Grafo:

1. Leggere un file GFA e creare un grafo etichettato utilizzando liste di adiacenza.
2. Etichettare i nodi e gli archi del grafo in base alle informazioni fornite nel file GFA.

II. Analisi dei Cammini nel Grafo:

1. Considerare tutti i possibili cammini da una sorgente (grado d'ingresso a zero) a una destinazione (grado d'uscita a zero) senza materializzarli tutti.
2. Se ci sono più sorgenti o destinazioni, selezionarne una specifica per l'analisi.

III. Ricerca di Cammini con DFS:

1. Utilizzare una ricerca in profondità (DFS) per trovare tutti i cammini da una sorgente a una destinazione nel grafo.
2. Ignorare l'array booleano “visitato” poiché il grafo è aciclico e utilizzare un array \( S \) di char di appoggio.
3. 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:

1. Data una sequenza pattern \( P \), verificare se è contenuta in una delle sequenze generate durante la ricerca.
2. Utilizzare tecniche di rolling hash per calcolare l'hash delle porzioni della sequenza e confrontarle con l'hash del pattern \( P \).

V. Calcolo delle Frequenze dei K-mer:

1. Identificare la frequenza dei K-mer in un pangenomegraph \( G \).
2. Calcolare la frequenza di ogni K-mer e il numero delle sue occorrenze. Ad esempio, per \( P = ATA \), la frequenza può essere 2.

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.

Esempio di Analisi

Consideriamo un grafo con i seguenti nodi e archi rappresentati in formato GFA: ``` S1 0 514 S2 517 unused L1 S1 S2 GAT CAG TA GAA ``` In questo grafo, analizziamo i cammini possibili e verifichiamo se il pattern \( P = TTCA \) è presente in una delle sequenze ottenute.

Conclusioni

Questo progetto permette di comprendere e applicare tecniche avanzate di bioinformatica per l'analisi di variazioni genetiche su larga scala. La rappresentazione tramite pangenomegraph offre una visione dettagliata delle differenze genomiche e facilita l'identificazione di pattern specifici attraverso l'utilizzo di algoritmi efficienti come la DFS e il rolling hash.

Riferimenti - Documentazione del formato GFA - Algoritmi di ricerca in profondità (DFS) - Tecniche di rolling hash