Méthodes à Noyau en Bio-Informatique

Jean-Philippe Vert, Ecole des Mines de Paris

Master recherche spécialité "Mathématiques Appliquées",
parcours M2 Mathématiques, Vision et Apprentissage (ENS Cachan), 2e semestre, 2004/2005

M2 Probabilités et Applications (Paris 6), 2e semestre, 2004/2005
M2 Modélisation Aléatoire (Paris 7), 2e semestre, 2004/2005

Résultats examen (M2 MVA)

Résultats examen (M2 Paris 6 et Paris 7)

Propositions thèses

• Bioinformatics team, University of Leuven (Y. Moreau)
• Max Planck Research School for Computational Biology and Scientific Computing, Berlin (deadline : 1/4/05)
• Bioinformatics et Machine learning, University of California at Irvine (P. Baldi)

Programme

• M2 MVA, Cachan (20 heures)
• M2 Probabilités et applications, Paris 6 (12 heures)

Slides

1. Resume du cours (pdf)
2. Introduction a la biologie moleculaire et a la bio-informatique (pdf)
3. Noyaux definis positifs (pdf)
4. Methodes a noyaux (pdf)
5. Noyaux pour séquences (pdf)
6. Noyaux marginalisés (pdf)
7. Noyaux sur graphes (pdf)

Demonstration SVM

• demo_dea.m, le script matlab

Description

Les méthodes à noyaux recouvrent un ensemble d'algorithmes pour l'analyse statistique de données, caractérisées par l'utilisation d'une fonction (appelée "noyau") permettant de mesurer la similarité entre les objets à analyser. En imaginant des fonctions noyaux pour des objets non vectoriels, tels des séquences, des graphes, des permutations ou des points sur des variétés différentielles, il est possibles d'appliquer à ces objets des méthodes puissantes d'analyse statistiques habituellement réservées à des données vectorielles, telles l'analyse en composantes principales, l'analyse de corrélations canoniques, ou les Support Vector Machines pour la classification et la régression.

La bio-informatique vise à analyser des masses de données biologiques pour en extraire de l'information pertinente. Ces données sont typiquements des séquences (d'ADN, d'acides aminés, etc...), des graphes, des structures tridimensionnelles de molécules, ou des arbres phylogénétiques. A partir de problèmes réels, nous montrerons comment des noyaux peuvent être construits pour ces différents types d'objets, nous étudierons différentes méthodes à noyaux et leur lien avec la théorie de la régularisation, et nous approfondirons l'étude de l'espace des fonctions noyaux lui-même. Les exemples réels qui motiveront ce cours seront notamment:

• la prédiction de la fonction, localisation et structure des protéines
• l'intégration de données hétérogènes en bio-informatique
• le criblage virtuel de molécules dans la recherche pharmaceutique

Projet obligatoire (M2 MVA)

Références:

• B. Schölkopf, K. Tsuda et J.-P. Vert, "Kernel methods in computational biology", MIT Press, 2004.
  [ps.gz,pdf]

• JP Vert, K. Tsuda, B. Schölkopf, "A primer on kernel methods", 2004
  [ps.gz,pdf]
  (une sorte de petit poly pour ce cours)
• A Zien, "A primer on molecular biology", 2004
  [ps.gz,pdf]
  (une introduction à la biologie, cf le premier cours)
• W Noble, "Support vector machines in computational biology", 2004
  [ps.gz,pdf]
  (une review des applications des SVM en bio-informatique)

• B. Schölkopf et A. Smola, "Learning with kernels", MIT Press, 2002.
• V. Vapnik, "Statistical Learning Theory", Wiley, 1998.
• C. Berg, J.P.R. Christensen et P. Ressel, "Harmonic analysis on semi-groups", Springer, 1994.

• N. Aronszajn, "Theory of reproducing kernels", Transactions of the American Mathematical Society, 68:337-404, 1950
  [pdf]
  (l'article qui introduit les RKHS)
• F Cucker et S. Smale, "On the mathematical foundations of learning", Bulletin of the AMS, 39(1):1-49, 2001
  [ps.gz,pdf]
  (une introduction à l'apprentissage, le chapitre 3 parle des noyaux de Mercer et RKHS)

• C Leslie, R Kuang, E Eskin , "Inexact matching string kernels for protein classification", 2004 (to appear)
  [ps.gz,pdf]
  (Un noyau pour séquences)
• JP Vert, H Saigo, T Akutsu , "Local alignment kernels for biological sequences", 2004 (to appear)
  [ps.gz,pdf]
  (Un noyau pour séquences)
• T. Jaakkola, M. Diekhans, and D. Haussler , "A discrimitive framework for detecting remote protein homologies", Journal of Computational Biology, Vol. 7 No. 1,2 pp. 95-114, (2000)
  [ps.gz,pdf]
  (Le noyau de Fisher pour séquences)
• R Karchin, K Karplus, D Haussler, "Classifying G-protein coupled receptors with support vector machines", Bioinformatics 18(1):147-159 (2002)
  [pdf,original pdf]
  (Une application du noyau de Fisher)
• T Kin, K Tsuda, K Asai, "Marginalized kernels for RNA sequence data analysis", Genome Informatics 13:112-122 (2002)
  [pdf,original pdf]
  (Un noyau pour ARN)
• H Kashima, K Tsuda, A Inokuchi , "Kernels for graphs", 2004 (to appear)
  [ps.gz,pdf]
  (Un noyau pour graphes, appliqué à des molécules)
• JP Vert , "A tree kernel to analyze phylogenetic profiles", Bioinformatics 18:S276-S284 (2002)
  [ps.gz,pdf]
  (Un noyau pour arbres phylogénétiques)
• R Kondor, JP Vert , "Diffusion kernels", 2004 (to appear)
  [ps.gz,pdf]
  (Un noyau sur un graphe, appliqué à des réseaux de protéines)
• Y Guermeur, A Lifchitz, R Vert , "A kernel for protein secondary structure prediction", 2004 (to appear)
  [ps.gz,pdf]
  (Un noyau sur un graphe, appliqué à des réseaux de protéines)
• A Zien et al. , "Engineering support vector machine kernels that recognize translation initiation sites", BioInformatics, 16(9):799-807, 2000
  [pdf,pdf original]
  (Un noyau spécifique pour reconnaitre les TIS)
• Paul Pavlidis, Jason Weston, Jinsong Cai and William Noble Grundy, "Gene functional classification from heterogeneous data", Proceedings of RECOMB 2001
  [pdf,original pdf]
  (Kernel CCA pour intégrer des données hétérogènes en bio-informatique)
• Y Yamanishi, JP Vert, M Kanehisa , "Heterogeneous data comparison and gene selection with kernel canonical correlation analysis", 2004 (to appear)
  [ps.gz,pdf]
  (Kernel CCA pour intégrer des données hétérogènes en bio-informatique)
• G Lanckriet, N Cristianini, M Jordan, W Noble , "Kernel-based integration of genomic data using semidefinite programming", 2004 (to appear)
  [ps.gz,pdf]
  (Combiner des noyaux différents par SDP)
• T Kin, T Kato, K Tsuda , "Protein classification via kernel matrix completion", 2004 (to appear)
  [ps.gz,pdf]
  (Estimer des valeurs manquantes dans des matrices de Gram)
• B Krishnapuram, L Carin, A Hartemink , "Gene expression analysis: joint gene selection and classifier design", 2004 (to appear)
  [ps.gz,pdf]
  (Classification de données de puces à ADN et sélection de gènes importants)