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ì
      1Pattern Matching. Algoritmo Bit-parallel per pattern matching esatto
      Python: funzioni, array, dizionar, moduli
      2Unix 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
      3Karp-Rabin Linguaggio Python: esercizi introduttivi (10/10/2017, 11,30-14,30 in LAB716)
      Implementazione Karp-Rabin
      4Suffix array e Suffix tree: definizioni (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.
      5Suffix array: pattern matching
      (24/10/2017, 12,30-14,30 in LAB716)
      Implementazione Suffix array: pattern matching
      6Allineamento di globale di 2 sequenze. Needleman-Wunsch. Allineamento globale come caso generale di distanza di edit e LCS

      Implementazione Needleman-Wunsch. Cenni SAM/BAM
      7Allineamento locale di 2 sequenze. Smith-Waterman
      (7/11/2017, 12,30-14,30 in LAB716)
      Interfacciamento Python/C. Librerie in C e Python
      (pausa)
      8Allineamento con gap
      (21/11/2017, 11,30-14,30 in LAB716)
      Allineamento con banda
      9Ricerca della sottostringa comune più lunga di k stringhe

      (28/11/2017, 12,30-14,30 in LAB716)
      Implementazione calcolo della sottostringa comune più lunga
      10Filogenesi su caratteri
      (5/12/2017, 11,30-14,30 in LAB716)

      11Filogenesi su distanze
       (12/12/2017, 12,30-14,30 in LAB716)Assemblaggio genoma (string graph)
      12Applicazioni suffix array/tree
      (19/12/2017, 12,30-14,30 in LAB716)Assemblaggio genoma (de Bruijn graph)
      (vacanze di Natale)
      13Cenni di argomenti evoluti