Università degli Studi di Milano

Bioinformatica  

Docente: Giorgio Valentini 

Obiettivi del corso:

Programma

0. Introduzione ai metodi di apprendimento automatico

1. Tipologie di apprendimento, generalizzazione e valutazione delle capacità di 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
2. Apprendimento supervisionato
- Look-up table e Nearest Neighbours.
- Approcci probabilistici e Teorema di Bayes; il problema della dimensionalità e approccio Naive Bayes.
- Reti neurali: Percettrone lineare, Percettrone multistrato e algoritmo di backpropagation
- Support Vector Machines e metodi supervisionati basati su kernel
- Metodi di ensemble
2. Metodi di apprendimento non supervisionato.
Metodi di clustering: k-means, algoritmi di clustering gerarchico, metodi per il clustering di grafi.

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

0. Applicazione dei di metodi machine learning nelle diverse diverse aree della biologia computazionale

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 sulla kernelizzazione congiunta dello spazio di input  e di output
(c) Metodi basati su ensemble e reti bayesiane
(d) Ensemble gerarchici basati sulle True Path Rule.

2. Inferenze semi-supervisionate 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. Predizione di varianti genetiche associate a patologie mendeliane.
(a) Varianti genetiche a livello di singolo nucleotide (SNV) e tipologie di feature genomiche associabili a SNV. Malattie genetiche mendeliane e malattie genetiche complesse.
(b) Metodi si apprendimento automatico supervisionato per la predizione di SNV associabili a malattie genetiche mendeliane.

Prerequisiti:

Materiale didattico 

• E.S. Lander and M.S. Waterman A Mathematician's Introduction to Molecular Biology
  
• Introduction to Genetics (Wikipedia)
• A. Zien A Primer in Molecular Biology
• Learn by yourself: training courses for the analysis of biomolecular data at the European Bioinformatics Institute
  
• Structure of gene and regulation of the expression
• G. Ratsch Introduction to Machine Learning in Bioinformatics
• T. Jaakkola Lecture 1 from the MIT CSAIL machine learning course
• T. Jaakkola Lecture 2 from the MIT CSAIL machine learning course
• Apprendimento, generalizzazione e stima dell'errore di generalizzazione
• Algoritmi di apprendimento supervisionato. KNN, percettrone lineare ed algoritmo di discesa a gradiente.
• Algoritmo di backpropagation per multi-layer perceptron
• Support Vector Machines
• Protein and gene function prediction through machine learning
  
• Ensemble methods based on Bayesian networks for gene function prediction
  
• Hierarchical ensemble methods for tree-structured bio-ontologies
  
• Hierarchical ensemble methods for DAG-structured bio-ontologies
• Biological Networks
• Random Walk and Label propagation algorithms
• Kernelized score functions (RANKS) and their application to biomolecular network analysis
• Big network analysis
  
• M.Frasca COSNet: parametrized Hopfield networks for semi-supervised cost-sensitive learning of gene functions.
• M.Notaro Hierarchical Ensemble Methods for Structured Prediction with Applications in Computational Biology

    Bioinformatics theses available at AnacletoLab - CS Dept. of Milan

• 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.
• Robinson, P.N., Kohler, S., Bauer, S., Seelow, D., Horn, D., Mundlos, S.: The Human Phenotype Ontology: a tool for annotating and analyzing human hereditary disease. Am. J. Hum. Genet. 83, 610–615 (2008)
  
• Z. Barutcuoglu, R. Schapire and O. Troyanskaya, Hierarchical multi-label prediction of gene function, Bioinformatics, 22(7), pp. 830-836, 2006.
• Guan, Y., Myers, C., Hess, D., Barutcuoglu, Z., Caudy, A., and Troyanskaya, O. (2008). Predicting gene function in a hierarchical context with an ensemble of classifiers. Genome Biology, 9(S2)
• Obozinski, G., Lanckriet, G., Grant, C., M., J., and Noble, W. (2008). Consistent probabilistic output for protein function prediction. Genome Biology, 9(S6)
• 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
• G. Valentini, Hierarchical Ensemble Methods for Protein Function Prediction, ISRN
  Bioinformatics, vol. 2014 (2014)
• Rousu, J., Saunders, C., Szedmak, S., and Shawe-Taylor, J. (2006). Kernel-based learning of hierarchical multilabel classification models. Journal of Machine Learning Research, 7, 1601–1626.
• Schietgat, L., Vens, C., Struyf, J., Blockeel, H., and Dzeroski, S. (2010). Predicting gene function using hierarchical multilabel decision tree ensembles. BMC Bioinformatics, 11(2).
• Sokolov, A. and Ben-Hur, A. (2010). Hierarchical classification of Gene Ontology terms using the GOstruct method. Journal of Bioinformatics and Computational Biology, 8(2), 357–376
• Kahanda, I., Funk, C., Verspoor, K., Ben-Hur, A.: PHENOstruct: Prediction of human phenotype ontology terms using heterogeneous data sources. F1000Research 4, 259 (2015)
• Bengio, Y., Delalleau, O., and Le Roux, N. (2006). Label Propagation and Quadratic Criterion. In O. Chapelle, B. Scholkopf, and A. Zien, editors, Semi-Supervised Learning, pages 193–216. MIT Press.
• R. Sharan, I. Ulitsky and R. Shamir, Network-based prediction of protein function , Molecular Systems Biology 3:88, 2007.
• Mostafavi, S. and Morris, Q. (2010). Fast integration of heterogeneous data sources for predicting gene function with limited annotation. Bioinformatics, 26(14), 1759–1765.
• Mostafavi, S., Ray, D.,Warde-Farley, D., Grouios, C., and Morris, Q. (2008). GeneMANIA: a real-time multiple association network integration algorithm for predicting gene function. Genome Biology, 9(S4)
• 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
• G. Valentini, A. Paccanaro, H. Caniza, A. Romero, M. Re, An extensive analysis of
  disease-gene associations using network integration and fast kernel-based gene
  prioritization methods, Artificial Intelligence in Medicine, Volume 61, Issue 2, pages
  63-78, June 2014
• M. Re, and G. Valentini, Network-based Drug Ranking and Repositioning with
  respect to DrugBank Therapeutic Categories, IEEE ACM Transactions on
  Computational Biology and Bioinformatics 10(6), pp. 1359-1371, Nov-Dec 2013, IEEE link
• G. Valentini, G. Armano, M. Frasca, J. Lin, M. Mesiti and M. Re RANKS: a flexible
  tool for node label ranking and classification in biological networks, Bioinformatics,
  32(18), 2016, Oxford University press link
• M. Frasca, A. Bertoni, G. Valentini UNIPred: Unbalance-aware Network Integration and Prediction of protein functions,  Journal of Computational Biology, 22(12): 1057-1074, 2015. doi:10.1089/cmb.2014.0110
• M. Mesiti, M. Re and G. Valentini, 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
  
• 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

Link a riviste di bioinformatica