Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_23:progetto_21 [19/05/2024 alle 13:54 (18 mesi fa)] – Roberto Grossi
+++ matematica:asd:asd_23:progetto_21 [03/10/2024 alle 13:11 (13 mesi fa)] (versione attuale) – Roberto Grossi
@@ Linea 8: / Linea 8: @@
 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:**
-   * Eseguire 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\).
-   * Ignorando l'array booleano "visitato" poiché il grafo è aciclico, usare un array \( S \) di caratteri 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 \).
-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 \).