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)
- J.Thompson, D. Higgins, T. Gibson, CLUSTAL
W:
improving the sensitivity of progressive multiple sequence
alignment through sequence weighting, position-specific gap
penalties and weight matrix choice, Nucleic
Acids Research, 22(22), 4673-4680, 1994.
- G.Pavesi, G.Mauri and G.Pesole, In
silico
representation and discovery of transcription factor binding
sites, Briefings in
Bioinformatics, 5(3), 2004.
- P. Larranaga et al. Machine
learning
in bioinformatics, Briefings in Bioinformatics 7(1):86-112, 2006
- Javed Khan et al., Classification
and
diagnostic prediction of cancers using gene expression
profiling and artificial neural networks, Nature Medicine 7,
673 - 679, 2001.
- Andreas Ruepp et al, The
FunCat,
a functional annotation scheme for systematic classification
of proteins from whole genomes, Nucleic
Acid
Research
32(18):5539-5545, 2004.
- M Ashburner et al., Gene
Ontology:
tool for the unification of biology, Nature
Genetics 25, 25 - 29 2000.
- M. Brown, et al., Knowledge-base
analysis
of microarray gene expression data by using Support
Vector
Machines, PNAS, vol.97(1), pp.
262-267, 2000
- T. S. Furey, N. Cristianini, N. Duffy, D.
W. Bednarski, M. Schummer, and D. Haussler Support
vector
machine classification and validation of cancer tissue samples
using microarray expression data Bioinformatics,
Oct 2000; 16: 906 - 914.
- P. Pavlidis, J. Weston , J. Cai and W.S. Noble, Learning
gene
functional classification from multiple data, J.
Comput. Biol., vol.9, pp.401-411, 2002
- G.R.G. Lanckriet, T. De Bie, N. Cristianini, M.I. Jordan and
W.S. Noble, A
statistical framework for genomic data fusion, Bioinformatics, vol.20, pp.
2626-2635, 2004.
- Z. Barutcuoglu, R. Schapire and O. Troyanskaya, Hierarchical
multi-label
prediction of gene function, Bioinformatics,
22(7), pp. 830-836, 2006.
- S. C. Madeira , A. L. Oliveira, Biclustering
Algorithms
for Biological Data Analysis: A Survey, IEEE
ACM Trans. on Bioinformatics and Computational Biology,
1(1), 2004.
- A.Bertoni, G.Valentini, Model
order
selection
for
biomolecular
data clustering, BMC
Bioinformatics, vol.8, Suppl.3, 2007.
- B. Langmead, C. Trapnell, M. Pop
and S. L. Salzberg Ultrafast
and
memory-efficient alignment of short DNA sequences to the
human genome, Genome
Biology, 10:R25, 2009
- M. Re, G. Valentini,
Simple ensemble methods are competitive with state-of-the-art
data integration methods for gene function prediction,
Journal of Machine Learning
Research, W&C Proceedings,, vol.8: Machine Learning
in Systems Biology, pp. 98-111, 2010
- G. Valentini, True
Path Rule hierarchical ensembles for genome-wide gene function
prediction, IEEE ACM
Transactions on Computational Biology and Bioinformatics,
vol.8 n.3 pp. 832-847, 2011. IEEE
CS
Digital library
- N. Cesa-Bianchi, M. Re, G. Valentini, Synergy
of multi-label hierarchical ensembles, data fusion, and
cost-sensitive methods for gene functional inference, Machine Learning,
vol.88(1), pp. 209-241, 2012, on-line available on Springer
link
- R. Sharan, I. Ulitsky and R. Shamir,
Network-based prediction of protein function , Molecular
Systems Biology 3:88, 2007.
|