Topic outline

  • General

    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.

    Il libro "An Introduction to Bioinformatics Algorithms" di N. Jones, P. Pevzner viene usato esclusivamente come approfondimento per la parte di ricostruzione di filogenesi.

    Il libro "Theoretical Evolutionary Genetics" di J. Felsenstein viene usato esclusivamente come approfondimento per la parte di ricostruzione di filogenesi.

    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, 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, 5.2, 5.3, 5.4) (dispensa)  Suffix array e Suffix tree: relazioni. LCP (Gusfield 7.14).
    6. Calcolo della sottostringa comune più lunga di 2 stringhe (Gusfield 7.4). Suffix array: pattern matching (Gusfield 7.14.2). Controllo di versione (git).
    7. Implementazione di pattern matching su suffix array.
    8. Ricerca della sottostringa comune più lunga di k stringhe (Gusfield, 7.4): algoritmo e implementazione
    9. Allineamento globale di 2 sequenze. Needleman-Wunsch (Gusfield 11.2, 11.3, 11.4, 11.6(.
    10. Allineamento locale di 2 sequenze. Smith-Waterman (Gusfield 11.7)
    11. Allineamento globale come caso generale di distanza di edit e LCS. (Gusfield, 11.6, 11.6.[1-2],). Allineamento con banda (Gusfield 12.2.3, 12.2.4)
    12. Allineamento con gap (Gusfield 11.8)
    13. Implementare algoritmi di programmazione dinamica. Allineamento multiplo (Gusfield 14.1, 14.[5-6]).
    14. Sequenziamento: string graphs (Gusfield 16.14, 16.15, 16.16, 16.17.1, 16.17.2).
    15. Sequenziamento: grafi di de Brujin (Gusfield 16.18).
    16. Filogenesi basata su caratteri (Gusfield 17.3, Gusfield 17.6.1, Jones&Pevzner Capitolo 10)
    17. Filogenesi basata su distanze. Neighbor-joining.  (Gusfield 17.1, 17.2, 17.4)
    18. Modelli di evoluzione. Max likelihood. (Felsenstein X.2, X.8)
    19. Python, FFI, Cython.

    Risorse

    • Laboratorio con Python

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

      Luogo: LAB713 (edificio U7) per tutte le lezioni tranne quella del 13/12/2018 che si tiene in LAB531 (edificio U5)

      Inizio: giovedì 18 ottobre 2018.