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
- 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
|