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 e modelli
probabilistici.
Algoritmi di programmazione dinamica per l'allineamento di
sequenze. Costruzione di alberi filogenetici. Catene di Markov,
Hidden Markov Models e loro applicazioni in biologia
computazionale. Banche dati biologiche e browser genomici.
II. Metodi di apprendimento
automatico
A. Parte generale
1. Applicazione dei metodi di machine learning nelle
diverse diverse aree della biologia computazionale
2. Un esempio introduttivo: supporto alla diagnostica medica.
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 biomolecolare
- SVM e loro applicazioni in biologia computazionale.
5. Apprendimento non supervisionato
- 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.
B. Alcuni problemi rilevanti in bioinformatica
1. Il problema della predizione automatica della funzione
delle proteine (AFP - Automated Function Prediction)
(a) Formalizzazione della AFP 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: 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) Apprendimento basato su kernel in reti di grandi dimensioni - algoritmi basati sull'utilizzo della memoria secondaria
(f) 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.
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
- 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.
- M. Re, M. Mesiti and G. Valentini, A
Fast Ranking Algorithm for Predicting Gene Functions in
Biomolecular Networks, IEEE ACM Transactions on
Computational Biology and Bioinformatics 9(6) pp. 1812-1818,
2012. IEEE
link
- M. Mesiti, M. Re and G. Valentini, A
Think globally and solve locally: secondary memory-based network learning for automated multi-species
function prediction , GigaScience, 3 (2014), p. 5 doi: 10.1186/2047-217X-3-5
gigascience
link
- Kyrola A, Blelloch G, Guestrin C., A
GraphChi: large-scale graph computation on just a PC.
In Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation . CA, USA: Hollywood, CA, USA, OSDI’12: USENIX Association Berkeley; 2012:31–46.
OSDI12
link
Link
ad AnacletoLab - Laboratorio di Biologia Computazionale del
Dipartimento di Informatica
|