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 da concordare con il docente. 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.

    Le note scritte del docente a lezione sono qui.

  • Algoritmi

    Le lezioni si tengono il Lunedì dalle 9.10 alle 11.00 e il Mercoledì dalle 10.30 alle 12.30.

    1. Pattern Matching. Algoritmo Bit-parallel per pattern matching esatto (Gusfield, 1-1.1, 4.1, 4.2.[1-2]). Cenni di Python.
    2. Richiamo linguaggio C.
    3. Karp-Rabin (Gusfield, 4.4): algoritmo e implementazione. Richiami shell Linux.. Make
    4. Implementazione Karp-Rabin. Shell Linux.
    5. Suffix array e Suffix tree: definizioni (Gusfield, 5, 5.[1-3], 7.14, 7.14.1) (dispensa) Controllo di versione (git).
    6. Suffix array e Suffix tree: relazioni. LCP. Calcolo della sottostringa comune più lunga di 2 stringhe. Suffix array: pattern matching
    7. Implementazione di pattern matching su suffix array.
    8. Ricerca della sottostringa comune più lunga di k stringhe (Gusfield, 7.4, 9.7): algoritmo e implementazione
    9. Allineamento di globale di 2 sequenze. Needleman-Wunsch.
    10. Allineamento globale come caso generale di distanza di edit e LCS. (Gusfield, 11.6, 11.6.[1-2], 14.1, 14.[5-6]). Allineamento con banda.
    11. Implementare algoritmi di programmazione dinamica
    12. Allineamento con gap
    13. Python, FFI, Cython.
    14. Allineamento locale di 2 sequenze. Smith-Waterman
    15. Sequenziamento: grafi di de Brujin
    16. Sequenziamento: string graphs.
    17. Applicazioni di suffix array
    18. Filogenesi basata su caratteri
    19. Filogenesi basata su distanze. Neighbor-joining. Max likelihood

    Risorse

    • Laboratorio con Python

      Giorno e orario: giovedì dalle 9,30 alle 12,30

      Luogo: LAB713 (edificio U7)

      Inizio: giovedì 18 ottobre 2018.