Indice degli argomenti

  • Introduzione

    Nel corso verranno introdotti i principali problemi in bioinformatica, insieme con alcuni algoritmi per risolvere tali problemi. Inoltre verranno presentate alcune modalità di gestione di dati biologici, quali i principali formati di file e database. Nel corso vengono trattati sia argomenti algoritmici che di programmazione oltre che, in misura minore, di database.

    Nel corso viene data grande attenzione alla capacità di sviluppare programmi per la risoluzione di problemi bioinformatici. Pertanto vengono trattate le tematiche di interfacciamento con le banche dati genomiche pubbliche e le metodologie adottate dalla comunità open source (git e GitHub).

    Il linguaggio di programmazione utilizzato in laboratorio è Python. Alcune lezioni sono dedicate allo studio di programmi scritti in C utilizzati in Bioinformatica.

    L’obiettivo complessivo del corso è permettere allo studente di comprendere un problema di natura bioinformatica, e di risolverlo utilizzando sia le competenze di metodologie algoritmiche che le pratiche di programmazione scientifica trattate nel corso.

    Modalità di esame

    L’esame è composto da uno scritto e da un progetto individuale. Il progetto contribuisce il 75% del voto finale, ma è necessario raggiungere la sufficienza in entrambe le parti dell’esami.

    Il progetto prevede di sviluppare un programma in C o Python su un tema concordato con il docente. Può essere svolto individualmente o in piccoli gruppi (max 3 persone).

    Lo scritto riguarda la parte su algoritmi e consiste in 3 domande.

    Materiale didattico

    Il libro di testo seguito per quasi tutte le lezioni è “Algorithms on Strings, Trees and Sequences”, di Daniel Gusfield, Cambridge Univ. Press. La biblioteca tiene alcune copie del libro di testo, anche come ebook.

    Propedeuticità

    Algoritmi e strutture dati. Linguaggi di programmazione.

    Risorse online

    Viene usato Github per gestire i programmi che vengono sviluppati o analizzati, che si troveranno nel progetto programmi. Le slide sono nel repo lezioni.

  • Algoritmi

    1. Pattern Matching. Algoritmo Bit-parallel per pattern matching esatto (Gusfield, 1-1.1, 4.1, 4.2.[1-2])
    2. Richiamo linguaggio C
    3. Karp-Rabin (Gusfield, 4.4)
    4. Suffix array e Suffix tree: definizioni (Gusfield, 5, 5.[1-3], 7.14, 7.14.1) (dispensa)
    5. Suffix array e Suffix tree: relazioni. LCP. Calcolo della sottostringa comune più lunga di 2 stringhe.
    6. Suffix array: pattern matching
    7. Ricerca della sottostringa comune più lunga di k stringhe (Gusfield, 7.4, 9.7)
    8. Allineamento di globale di 2 sequenze. Needleman-Wunsch. Allineamento globale come caso generale di distanza di edit e LCS. (Gusfield, 11.6, 11.6.[1-2], 14.1, 14.[5-6])
    9. Allineamento con gap
    10. Allineamento locale di 2 sequenze. Smith-Waterman
    11. Sequenziamento e grafi di de Brujin
    12. Applicazioni di suffix array
    13. Filogenesi basata su caratteri
    14. Filogenesi basata su distanze

    Risorse

    • Argomenti del laboratorio con Python

      Il laboratorio inizia martedì 3 ottobre 2017

      1. Modellizzazione del dato (sequenza e gene), cenni di sequenziamento e formati standard (EMBL, FASTA), banche dati genomiche
      2. Annotazione di un gene e formato standard GTF. Esercizio di manipolazione di file GTF
      3. Qualità del dato di sequenziamento e formato standard FASTQ. Esercizio di manipolazione di file FASTQ
      4. Formato standard SAM/BAM (Sequence Alignment Format) per memorizzare allineamenti. Esercizio di manipolazione di file SAM
      5. Esercizio su un tipico workflow di Bioinformatica
    • C

      1. Unix shell (bash). Controllo di versione (git e github)
      2. Implementazione Karp-Rabin
      3. Implementazione Suffix array:costruzione
      4. Implementazione Suffix array: pattern matching (1)
      5. Implementazione calcolo della sottostringa comune più lunga
      6. Implementazione Smith-Waterman
      7. Allineamento con banda
      8. Implementazione Allineamento con gap
      9. Interfacciamento Python/C
    • Organizzazione lezioni

      Settimana Lunedì Martedì Giovedì
      1 Pattern Matching. Algoritmo Bit-parallel per pattern matching esatto
      Python: funzioni, array, dizionar, moduli
      2 Unix shell (bash). Controllo di versione (git e github).
      Linguaggio Python: esercizi introduttivi (3/10/2017, 11,30-14,30 in LAB716)
      Richiamo linguaggio C. Make
      3 Karp-Rabin Linguaggio Python: esercizi introduttivi (10/10/2017, 11,30-14,30 in LAB716)
      Implementazione Karp-Rabin
      4 Suffix array e Suffix tree: definizioni Modellizzazione del dato: DNA, RNA e gene
      (17/10/2017, 12,30-14,30 in LAB716)
      Suffix array e Suffix tree: relazioni. LCP. Calcolo della sottostringa comune più lunga di 2 stringhe.
      5 Suffix array: pattern matching
      Manipolazione di un file in formato EMBL tramite espressioni regolari in Python (parte I)
      (24/10/2017, 12,30-14,30 in LAB716)
      Implementazione Suffix array: pattern matching
      6 Allineamento di globale di 2 sequenze. Needleman-Wunsch. Allineamento globale come caso generale di distanza di edit e LCS
      (31/10/2017 - laboratorio sospeso)
      Allineamento locale di 2 sequenze. Smith-Waterman
      7 Allineamento con gap
      Manipolazione di un file in formato EMBL tramite espressioni regolari in Python (parte II)
      (7/11/2017, 12,30-14,30 in LAB716)
      Interfacciamento Python/C. Librerie in C e Python
      (pausa)
      8 Allineamento con banda
      Manipolazione in Python di un file in formato standard GTF - parte I (21/11/2017, 11,30-14,30 in LAB716)
      Implementazione Needleman-Wunsch.
      9  Filogenesi su caratteri (3 ore)

      (28/11/2017 - laboratorio sospeso)
      Filogenesi su distanze
      10 Neighbor-Joining. Max likelihood
      Manipolazione in Python di un file in formato standard GTF - parte II (5/12/2017, 11,30-14,30 in LAB716)

      11 Ricerca della sottostringa comune più lunga di k stringhe
       (12/12/2017, 11,30-14,30 in LAB717) Assemblaggio genoma (string graph)
      12 Implementazione calcolo della sottostringa comune più lunga
      (19/12/2017, 11,30-14,30 in LAB717) Assemblaggio genoma (de Bruijn graph)
      (vacanze di Natale)
      13