UniversitÓ degli Studi di Milano

Corso di laurea magistrale in Informatica
a.a. 2014/15

Bioinformatica  

Docenti: Matteo Re, e Giorgio Valentini 

Periodo di svolgimento: I semestre 2014/15
Orari:    Martedi 12.30-14.30  Mercoledý 13.00-15.00      
Aula: Auletta 6 del DI, via Comelico 39

INIZIO CORSO:  Martedi 30 Settembre ore 12.30 auletta 6

Course description (in english - pdf)

Obiettivi del corso:

L'obiettivo principale del corso consiste nel fornire strumenti metodologici per analizzare ed estrarre conoscenza biologica da dati biomolecolari complessi tramite metodi di apprendimento automatico. Il corso Ŕ per sua natura interdisciplinare ed aperto agli studenti di Informatica, Fisica, Matematica, Biologia, Biotecnologie e di altre discipline scientifiche.

Programma


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

I. Metodi di pattern matching.


1. Allineamento di biosequenze.
Biosequenze: DNA, RNA, proteine. Allineamento di sequenze: motivazione basata su ipotesi evolutiva. Allineamento algoritmico di sequenze: longest common subsequence e necessitÓ di utilizzo dei gap.
2. Allineamenti basati su programmazione dinamica: a) Allineamenti locali e Algoritmo di Smith e Waterman; schemi di scoring per sequenze nucleotidiche; b) Allineamenti globali e Algoritmo di Needleman-Wunsch. Matrici di sostituzione degli aminoacidi (PAM/BLOSUM): loro significato funzionale e loro costruzione. Algoritmo GOTOH (affine gaps).
3. Euristiche di allineamento. Dinamica di crescita delle banche dati di biosequenze. NecessitÓ di algoritmi  veloci per ricerca di biosequenze in grandi banche dati. Euristica FASTA (step by step). Euristica BLAST (step by step). Confronto tra FASTA e BLAST. Maggiore sensibilitÓ di BLAST. Confronto similitudini/differenze tra FASTA e BLAST. Descrizione della famiglia di  algoritmi BLAST: Blastn, Blastp, blastX e tblastX.
4. Evoluzione e filogenesi. Tree of life. Ipotesi orologio molecolare. Distanza tra biosequenze. Matrice di distanze. Allineamento multiplo. IntrattabilitÓ della ricerca di allineamento multiplo ottimale mediante programmazione dinamica. Allineamento progressivo con e senza albero guida. Algoritmo Clustal-W. Ruolo dell'albero guida nell'allineamento progressivo.
Costruzione di alberi filogenetici. Correzione delle distanze sulla base delle identitÓ di sequenza. Modelli per l'evoluzione di biosequenze (Kimura con 2 parametri). Algoritmo UPGMA.

II. Metodi di apprendimento automatico

A. Parte generale

1. Metodi di machine learning nelle diverse diverse aree della biologia computazionale
2. 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
3. Apprendimento supervisionato
- Look-up table e Nearest Neighbours.
- Approcci probabilistici e Teorema di Bayes; il problema della dimensionalitÓ e approccio Naive Bayes.
- Reti neurali:
(a) Percettrone lineare
(b) MLP e alg. backpropagation
(c) Ensemble di percettroni multiclasse per il supporto alla diagnostica biomolecolare
- SVM e loro applicazioni in biologia computazionale.


B. Metodi supervisionati, semi-supervisionati e non supervisionati in bioinformatica

1. Il problema della predizione supervisionata della funzione delle proteine (AFP - Automated Function Prediction)
(a) Formalizzazione della AFP come problema di classificazione gerarchico multiclasse e multietichetta
(b) Metodi basati su ensemble e reti bayesiane
(c) Metodi basati su ensemble gerarchici fondati sulle True Path Rule.

2. Inferenze semi-supervisonate 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: annotazione funzionale dei geni, ricerca di associazioni gene-malattia, riposizionamento terapeutico dei farmaci.
(c) Algoritmi basati su random walk e random walk con restart
(d) Algoritmi basati su kernel e kernelized score function
(e) Algoritmi basati su reti di Hopfield cost-sensitive.
(f) Tecnologie basate su memoria secondaria e implementazione vertex-centric di algoritmi network-based per il processing di reti biomolecolari di grandi dimensioni.

3. Ricerca non supervisionata di pattern in dati omici
- Algoritmi di clustering per l'analisi di dati omici: algoritmi k-means, fuzzy k-means, algoritmi gerarchici, self-organizing maps. Metodi di ensemble clustering.
- Analisi dell'affidabilita' dei cluster. Metodi basati sulle caratteristiche strutturali dei cluster. Metodi basati sulla stabilita'. Applicazioni alla ricerca di sottoclassi patologiche clinicamente rilevanti.

 

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.


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, 2007.

Materiale didattico 


Articoli

Link ad AnacletoLab - Laboratorio di Biologia Computazionale del Dipartimento di Informatica

Link a riviste di bioinformatica