Topic outline
-
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 50% 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). In alternativa è possibile svolgere tre esercizi durante il corso, con scadenze fissate e non derogabili. Gli esercizi saranno 2 su Python e 1 su C: in quest'ultimo caso, se gli esercizi sono svolti correttamente e secondo le richieste, il voto del progetto è 30/30.
Lo scritto riguarda la parte su algoritmi e consiste in 4 domande, ma bisogna rispondere a 3 delle 4 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 e di sequenziamento.
Il libro "Theoretical Evolutionary Genetics" di J. Felsenstein viene usato esclusivamente come approfondimento per la parte di ricostruzione di filogenesi. A similar book is Poplation and Quantitative Genetics by Graham Coop.
Slide e programmi sono nel repo https://github.com/bioinformatica-corso/lezioni
Per quanto riguarda la parte su Python, viene usato il Jupyter notebook. Viene consigliata l'installazione di python e del notebook tramite conda.
Come shell di linux viene introdotto bash. Per chi ha Linux o Mac non è necessario installare altri programmi. A chi ha Windows si consiglia WSL.
Propedeuticità
Algoritmi e strutture dati. Linguaggi di programmazione.
Calendario
- Le lezioni su argomenti algoritmici si tengono il Lunedì dalle 14.30 alle 17.30 e il Mercoledì dalle 8.30 alle 10.30. Le lezioni a distanza saranno via zoom, seguendo il link
- Le lezioni su Python si tengono il Martedì dalle 10.30 alle 13.30
Risorse
Chat del corso. Viene usata per tutte le discussioni inerenti il corso.-
AssignmentEsame 23/02/2021 Assignment
-
Si richiede di scrivere un validatore del formato GTF (Gene Transfer Format) che prenda in input un file in formato GTF che annota un set di geni ed effettui la validazione del file rispetto alla specifica del formato.
Il validatore deve produrre in output un report con le violazioni presenti, specificando per ognuna di esse il record che la contiene (posizione all'interno del file in input) e tutte le informazioni che si ritengono necessarie per descriverla e correggerla.
Il validatore può essere prodotto sia come script che come Jupyter Notebook, e deve essere adeguatamente commentato. Si richiede inoltre un documento che elenchi e descriva brevemente le violazioni che sono state considerate. Per ogni violazione considerata, includere un file con tale violazione.
Il validatore deve essere caricato in un repository GitHub di cui va consegnato il linkTermine di consegna: 30 novembre.
-
Si richiede di scrivere un convertitore da FASTQ a FASTA che prenda in input un file di reads in formato FASTQ e produca in formato FASTA i soli reads che hanno le seguenti caratteristiche: (1) non sono più corti di una soglia L1 e non sono più lunghi di una soglia L2, (2) la qualità minima delle basi supera una soglia Q1, (3) contengono una sottoregione con qualità minima Q2 (maggiore di Q1) che è lunga almeno P% della lunghezza del read.
Viene richiesto l'uso di Biopython per leggere i reads dal file FASTQ in input e per stampare (in standard output o su file) i reads in formato FASTA.
L1, L2 (> L1), Q1, Q2 (> Q1) e P devono essere parametri in input.
Per ognuno dei reads in output, l'header FASTA deve contenere le seguenti informazioni: (1) identificatore, (2) lunghezza, (3) qualità minima delle basi, (4) start ed end della sottoregione con qualità minima Q2, (5) qualità media della sottoregione con qualità minima Q2
Il convertitore può essere prodotto sia come script che come Jupyter Notebook, deve essere adeguatamente commentato e deve essere caricato in un repository GitHub di cui va consegnato il link
Termine di consegna: 7 gennaio 2021. -
Assignment
Partendo dal programma che calcola la LCS con banda, scrivere un programma C che calcola l'allineamento globale ottimo di due sequenze in una banda (quindi scrivendo una variante dell'algoritmo di Smith-Waterman). Deve essere previsto un meccanismo per leggere le due sequenze da allineare (va bene sia leggerle da file che da standard input).
Come matrice di score, usare BLOSUM62 dove l'asterisco è il simbolo che denota un indel. Per semplicità, la matrice può essere scritta in un file sorgente (.h o .c).
L'output consiste in una rappresentazione testuale dell'allineamento delle due sequenze e il valore di score totale. Ogni rappresentazione testuale che che sia ragionevolmente intuitiva (ad esempio ogni sequenza su ogni riga, incolonnate opportunamente e con un simbolo diverso per dire se due caratteri sono uguali, diversi o presentano un indel) è accettabile.
La consegna è il link al repo pubblico (ad esempio su github).
-
ForumAvvisi dei docenti agli studenti. Per ricevere gli avvisi è necessario essere iscritti al corso.
-
Kaltura Video Resource
-
Kaltura Video Resource
-
Kaltura Video Resource
-
Kaltura Video Resource
- Le lezioni su argomenti algoritmici si tengono il Lunedì dalle 14.30 alle 17.30 e il Mercoledì dalle 8.30 alle 10.30. Le lezioni a distanza saranno via zoom, seguendo il link
-
- Algoritmo Bit-parallel per pattern matching esatto. (Gusfield 1.1, 4.1, 4.2.[1-2])
- Karp-Rabin: algoritmo e implementazione. (Gusfield 4.4)
-
- Definizioni. Array LCP. Passaggio da Suffix tree a suffix array e viceversa. Calcolo della sottostringa comune più lunga di 2 stringhe. (Gusfield 5, 5.1, 5.2, 5.3, 5.4, 7.4. dispensa)
- Pattern matching su suffix array. Algoritmo e implementazione (Gusfield 7.14)
- Ricerca della sottostringa comune più lunga di k stringhe: algoritmo e prima implementazione (Gusfield 7.4)
- Range minimum query. Implementazione sottostringa comune più lunga di k stringhe.
-
- Allineamento globale di 2 sequenze. Relazione con distanza di edit. Algoritmo di Needleman-Wunsch. (Gusfield 11.2, 11.3, 11.4, 11.6)
- Allineamento locale di 2 sequenze. Smith-Waterman (Gusfield 11.7)
- Allineamento con banda. Allineamento con gap. (Gusfield 12.2.3, 12.2.4, 11.8)
- Implementare algoritmi di programmazione dinamica.
- Allineamento multiplo. (Gusfield 14.1, 14.[5-6])
-
- Filogenesi basata su caratteri (Gusfield 17.3, 17.6.1. Jones&Pevzner Capitolo 10)
- Filogenesi basata su distanze. UPGMA e Neighbor-joining. (Gusfield 17.1 17.2 17.4)
- Modelli di evoluzione. Max likelihood. (Felsenstein X.2, X.8)
-
- grafi di de Brujin (Gusfield 16.18)
- grafi di stringhe (Gusfield 16.14, 16.15, 16.16, 16.17.1, 16.17.2)
-
- Genotipi e Aplotipi: singolo individuo.
- Genotipi e Aplotipi: pedigree.
-
Giorno e orario: martedì dalle 10:30 alle 13:30
Il laboratorio è terminato il 1° dicembre
-
- Richiami shell Linux. Make (1 lezione) comandi
- Controllo di versione (git). software carpentry
- Interfacciare Python e C: FFI, Cython.
- Richiami shell Linux. Make (1 lezione) comandi