Universitą degli Studi di Milano

Corso di laurea magistrale in Informatica
a.a. 2012/13

Bioinformatica  

Docenti: Giulio Pavesi (I modulo),  Giorgio Valentini (II modulo) e Matteo Re

Periodo di svolgimento: I semestre 2012/13
Orari:    Martedi 12.30-14.30      Mercoledi 13.30-15.30
Aula: Auletta 6 del DSI, via Comelico 39

Obiettivi del corso:

Introduzione alla bioinformatica. Applicazione di metodi di pattern matching, metodi di apprendimento automatico e modelli probabilistici all'analisi di dati biomolecolari.

Programma


0. Introduzione.
Cenni di biologia molecolare, tipologie di problemi computazionali e tipologie di dati in bioinformatica. Basi di dati genomiche e proteomiche.

1. Metodi di pattern matching e modelli probabilistici.
- Misurare l'evoluzione: distanza di Hamming e distanza di edit normale e pesata. Allineamento di sequenze e programmazione dinamica
- Allineamento di sequenze: complessitą e soluzioni euristiche. Allineamenti progressivi. Profili di allinemento.
- Allineamenti veloci ed euristici. Strutture di indicizzazione di testi e sequenze. Alberi di suffissi.
- Cenni di probabilitą e statistica applicati all'analisi di sequenze. Entropia, entropia relativa ed information content.  Test di significativitą: z-score. Chi-quadro.
- Analisi del DNA non codificante. Modelli probabilistici di ordine superiore. Hidden Markov Models. Grammatiche context-free.
2. Metodi di apprendimento automatico
A. Parte generale
1. I problemi della bioinformatica: applicazione dei metodi di machine learning  diverse aree della biologia computazionale
2. Un esempio introduttivo: Supporto alla diagnostica in medicina. Look-up table e Nearest Neighbours. Approcci probabilistici e Teorema di Bayes; il problema della dimensionalitą e approccio Naive Bayes. Dalla stima della densitą di probabilitą alla stima diretta della funzione discriminante.
3. Tipologie di apprendimento, generalizzazione e valutazione dell'apprendimento
  (a) Apprendimento Supervisionato, non supervisonato e semi-supervisionato
  (b) Apprendimento, over and underfitting, generalizzazione.
  (c) Metodi sperimentali per la stima dell'errore di generalizzazione
4. Apprendimento supervisionato 
   - Reti neurali
       (a) Percettrone lineare
       (b) MLP e alg. backpropagation
       (c) Ensemble di percettroni multiclasse per il supporto alla diagnostica
   - SVM  e loro applicazioni in biologia computazionale.
B. Alcuni problemi rilevanti in bioinformatica
1. Il problema della predizione delle funzioni geniche (GFP)
   (a) Formalizzazione della GFP come problema di classificazione gerarchico multiclasse e multietichetta
   (b) L'approccio di Princeton basato su ensemble e reti bayesiane
   (c) L'approccio basato su ensemble gerarchici fondati sulle True Path Rule
2. Inferenze in reti biomolecolari
   (a) Modellazione di reti biomolecari come grafi
   (b) Principali tipologie di problemi di biologia computazionale modellabili come problemi di ranking di nodi su grafi: GFP, gene prioritization, drug repositioning
   (c) Algoritmi basati su random walk e random walk con restart
   (d) Algoritmi basati su kernel e kernelized score functions
   (e) Algoritmi basati su reti di Hopfield cost-sensitive.


Prerequisiti:

Nozioni elementari di analisi matematica e statistica.
Corsi consigliati: Metodi Statistici per l'Apprendimento e Sistemi intelligenti

Modalitą d' esame:

I. Implementazione ed applicazione di un algoritmo per l'analisi di dati bio-molecolari, oppure discussione orale di letteratura scientifica, relativa ad un argomento trattato durante il corso.
II. Discussione orale sugli argomenti trattati durante il corso.
La letteratura scientifica da discutere e la data dell'esame dell'esame devono essere concordate con i docenti.


Bibliografia

D. Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge Press, 1997.

G. Yona  Introduction to Computational Proteomics Chapman & Hall/CRC, 2011.

C. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.

B. Scholkopf, K. Tsuda and J.P. Vert Kernel Methods in Computational Biology, MIT Press, 2004.


Materiale didattico 

I modulo:

II modulo:


Articoli (da aggiornare)

Link a riviste di bioinformatica