Studiare
In questa sezione è possibile reperire le informazioni riguardanti l'organizzazione pratica del corso, lo svolgimento delle attività didattiche, le opportunità formative e i contatti utili durante tutto il percorso di studi, fino al conseguimento del titolo finale.
Tipologia di Attività formativa D e F
Offerta formativa da definire
Fundamental algorithms for bioinformatics (2019/2020)
Codice insegnamento
4S004550
Crediti
12
Lingua di erogazione
Inglese
Offerto anche nei corsi:
- Algorithms for computational biology del corso Laurea magistrale in Molecular and medical biotechnology [LM-9]
Settore Scientifico Disciplinare (SSD)
INF/01 - INFORMATICA
L'insegnamento è organizzato come segue:
Algorithm design
Bioinformatics algorithms
Obiettivi formativi
Il corso permetterà agli studenti di acquisire un bagaglio di strumenti analitici avanzati alla base delle soluzioni algoritmiche di problemi fondamentali in bioinformatica. Conoscenza e capacità di comprensione Fornire le conoscenze e le competenze necessarie per l'analisi e la progettazione di soluzioni algoritmiche a problemi fondamentali in bioinformatica. Conoscenze applicate e capacità di comprensione Capacità di progettare soluzioni algoritmiche per problemi tipici di bionformatica e biologia computazionale, quali l'analisi di sequenze omiche. Autonomia di giudizio Capacità di individuare le componenti strutturali critiche e quindi gli approcci più idonei nel trattamento di problemi complessi di bioinformatica. Abilità comunicative Capacità di descrivere con l'adeguata precisione e chiarezza un problema bioinformatico, la sua modellizzazione e la soluzione associata sia ad interlocutori esperti che in contesti meno specialistici e multidisciplinari. Capacità di apprendere Capacità di ampliare le proprie conoscenze in ambito bioinformatico anche in maniera autonoma, utilizzando le nozioni apprese per leggere comprendere ed eventualmente rielaborare autonomamente articoli e testi scientifici di livello avanzato.
Programma
------------------------
MM: Algorithm design
------------------------
Concetti di base di analisi degli algoritmi e complessità: ricapitolazione di algoritmi per la visita di grafi; problemi di cammini minimi; alberi minimi ricoprenti; elementi di teoria della complessità computazionale e NP-completezza. Modelli di "Genome Rearrangement": (i) algoritmi di approssimazione per modelli basati su inversioni (permutazioni senza segno); (ii) il modello DCJ; (iii) algoritmi di approssimazione per la "Synteny Distance". Modelli per"Physical Map": (i) il problema degli uni consecutivi in una matrice (C1P); (ii) approssimazione per il problema della minimizzazione dei gap basato su TSP metrico (relazioni con il problema del ciclo Hamiltoniano e limiti di approssimabilità di TSP; 2-approssimazione per il TSP metrico). Modelli per DNA assembly: (i) Il problema della superstringa più corta (SCS), relazioni con il problema del max-cost TSP, approssimazione della massimia compressione mediante matching pesato in grafi bipartiti; (ii) Assembly mediate cicli Euleriani; algoritmi efficienti per costruire cicli e cammini Euleriani. Modelli per contig assembly: gap-filling basato su min-cost flow (reti di flusso e scomposizione del flusso in cammini disgiunti); min-cost circulation; applicazioni di min-cost circulation per SCS (max/min matching in grafi bipartiti); Modelli teorico informazionali per il confronto di sequenze : elementi di teoria dell'informazione e compressione dati; LZ-parsing; universal compression distance per clustering e confronto di sequenze
------------------------
MM: Bioinformatics algorithms
------------------------
Il seguente è un sommario dei principali argomenti trattati in questo modulo. Gli argomenti tra parentesi possono variare. * Introduzione Parte I: Confronto di coppie di sequenze * Allineamento di coppie di sequenze * Distanze tra stringhe (* RNA secondary structure prediction) * Allineamento di coppie di sequence in pratica: BLAST, matrici di punteggio Parte II: Allineamento di sequenze multiple * Soluzione esatta DP (* Riduzione dello spazio di ricerca con il metodo Carillo-Lipman) * approssimazioni, euristiche Parte III: Riconstruzione filogenetica * dati di tipo distanza: UPGMA, NJ * dati di tipo carattere: Filogenetica perfetta (PP) (* dati di tipo carattere: Large Parsimony, Small Parsimony) Parte IV: Algoritmi per "sequence assembly" (* Shotgun sequencing: SCS) * Sequencing by Hybridization e NGS: grafi di de Bruijn, tour euleriani
Bibliografia
| Attività | Autore | Titolo | Casa editrice | Anno | ISBN | Note |
|---|---|---|---|---|---|---|
| Algorithm design | J. Kleinberg, É. Tardos | Algorithm Design (Edizione 1) | Addison Wesley | 2006 | 978-0321295354 | |
| Algorithm design | H.J. Böckenhauer, D. Bongartz | Algorithmic Aspects of Bioinformatics | Springer | 2007 | ||
| Algorithm design | Neil C. Jones, Pavel A. Pevzner | An introduction to bioinformatics algorithms (Edizione 1) | MIT Press | 2004 | 0-262-10106-8 | |
| Algorithm design | V. Mäkinen, D. Belazzougui, F. Cunial, and A.I. Tomescu | Genome Scale Algorithm Design (Edizione 1) | Cambridge University Press | 2015 | ISBN 978-1-107-07853-6 | |
| Algorithm design | J.C. Setubal, J. Meidanis | Introduction to Computational Biology | Pws Pub Co | 1997 | ||
| Bioinformatics algorithms | H.J. Böckenhauer, D. Bongartz | Algorithmic Aspects of Bioinformatics | Springer | 2007 | ||
| Bioinformatics algorithms | Enno Ohlebusch | Bioinformatics Algorithms | 2013 | 978-3-00-041316-2 | ||
| Bioinformatics algorithms | Veli Mäkinen, Djamal Belazzougui, Fabio Cunial and Alexandru I. Tomescu | Genome-Scale Algorithm Design | CUP | 2015 | 978-1-107-07853-6 | |
| Bioinformatics algorithms | Joao Setubal and Joao Meidanis | Introduction to Computational Biology | 1997 |
Modalità d'esame
------------------------
MM: Algorithm design
------------------------
L'esame è volto ad accertare che gli studenti abbiano acquisito padronanza delle tecniche fondamentali per l'analisi e la progettazione di algoritmi e che conoscano il loro utilizzo per la soluzione di alcuni problemi computazionali classici in bioinformatica. L'esame consiste in una prova scritta con quesiti aperti. Tipicamente la prova include alcuni esercizi obbligatori ed altri esercizi a scelta. Gli esercizi obbligatori verificano le conoscenze relative all'analisi di algoritmi e alle soluzioni di problemi classici analizzati durante il corso; gli esercizi a scelta verificano la capacità dello studente di modellare un nuovo problema e progettare e descrivere una soluzione algoritmica. Al voto finale per il modulo Algorithm Design concorre la soluzione di esercizi periodici assegnati durante il corso. Il voto finale per l'intero esame di "Fundamental Algorithms for Bioinformatics" è dato dalla media aritmetica dei voti conseguiti nei due moduli
------------------------
MM: Bioinformatics algorithms
------------------------
Una prova scritta, seguita da una orale. Il superamento della prova scritta è prerequisito necessario al sostenimento dell'orale. La prova scritta include domande teoriche (problemi visti a lezione; analisi di algoritmi visti a lezione; proprietà matematiche di tali problemi e algoritmi; quali algoritmi esistono per un dato problema, etc), ed applicazione di algoritmi a problemi concreti (calcolo di un allineamento mediante l'algoritmo DP, etc). Nel colloquio orale, gli studenti dovranno anche dettagliare le soluzioni presentate per la prova scritta, e dimostrare padronanza delle conoscenze acquisite. Gli studenti del Masters in Molecular e medical biotechnology sostengono una prova con quesiti differenti. Non sono previsti esami diversi per studenti frequentanti e no.
