Codice insegnamento

4S004550

Crediti

12

Coordinatore

Zsuzsanna Liptak

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

Moodle Seminari 0

L'insegnamento è organizzato come segue:

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
------------------------
1. 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. 2. 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". 3. 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. 4. Misure di distanza tra sequenza biologiche: (i) edit distance, (ii) LCS-distance, (iii) q-gram distance, (iv) possibilmente ulteriori distanze. 5. Introduzione di strutture dati per sequenze genomiche: (i) cenni di suffix tree e suffix array, (ii) qualche applicazione.
------------------------
MM: Bioinformatics algorithms
------------------------
1. Confronto di coppie di sequenze: (i) Allineamento di coppie di sequenze (globale, locale); (ii) varianti: allineamento ottimale in spazio lineare, allineamento semiglobale, affine gap penalties; (iii) similarità vs. distanza; (iv) allineamento di coppie di sequenze in pratica: dotplot, BLAST, matrici di punteggio 2. Allineamento di sequenze multiple: (i) Soluzione esatta DP; (ii) Riduzione dello spazio di ricerca con il metodo Carillo-Lipman; (iii) approssimazioni, euristiche 3. RNA secondary structure prediction 4. Riconstruzione filogenetica: (i) dati di tipo distanza: alberi ultrametrici e UPGMA; (ii) dati di tipo distanza: alberi additivi e Neighbor Joining; (iii) dati di tipo carattere: Filogenetica perfetta (PP); (iv) dati di tipo carattere: Small Parsimony (Fitch' algorithm); (v) dati di tipo carattere: euristiche per Large Parsimony

Bibliografia

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. Per il superamento dell'esame è necessario sostenere una prova scritta con quesiti aperti e/o a risposta multipla. Tali esercizi verificano le conoscenze relative all'analisi di algoritmi e alle soluzioni di problemi classici analizzati durante il corso e la capacità dello studente di modellare un nuovo problema e progettare e descrivere una soluzione algoritmica. Se si consegue un risultato superiore a 25 nella prova scritta è necessario sostenere un colloquio orale. 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
------------------------
Per il superamento dell'esame è necessario sostenere una prova scritta. Se si consegue un risultato superiore a 25 nella prova scritta è necessario sostenere un colloquio 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 nella prova scritta, e dimostrare padronanza delle conoscenze acquisite. Il voto finale per l'intero esame di "Fundamental Algorithms for Bioinformatics" è dato dalla media aritmetica dei voti conseguiti nei due moduli. 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.