Strumenti Utente

Strumenti Sito


matematica:asd:asd_18:progetto_18

Progetto di ASD, anno accademico 2018/19

Questo progetto sostituisce l'esame scritto del corso o il seminario, e non necessita la presentazione del mini-progetto.

Il progetto utilizza un file di input contenente stringhe di lunghezza prefissata k, che rappresentano i k-meri ottenuti dalle “read” dell'High Throughput Sequencing (HTS) su sequenze di DNA. Tali k-meri definiscono un grafo di de Bruijn come descritto nei lucidi del corso: lucidi .

Il progetto richiede di:

  • Scaricare uno dei file di input, dove k=99: 10^5 read, 10^6 read, 10^7 read (fonte:https://github.com/felipelouza/egap/tree/master/dataset).
  • Costruire il corrispondente grafo di de Bruijn (per fare una prova utilizzare questi read con k=9: small read).
  • Progettare delle opportune strutture dei dati per rispondere alle seguenti operazioni di ricerca (dove la terza utilizza la seconda), per una stringa P di lunghezza arbitraria m > k:
    1. stabilire se P appare come sequenza di caratteri che occorrono lungo uno dei cammini del grafo;
    2. trovare il più lungo prefisso di P che soddisfa la condizione della 1;
    3. eseguire la 1 dove P può avere un errore: uno dei suoi simboli non corrisponde, ma gli altri sì (es. trova anche AGCC o ATCT specificando P = ATCC perché differiscono in un solo simbolo che non corrisponde).
matematica/asd/asd_18/progetto_18.txt · Ultima modifica: 30/05/2019 alle 13:22 (4 settimane fa) da Roberto Grossi