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)