Attention,
toute proposition doit faire l’objet d’un résumé enregistré
avant le 28 mars 2003
directement sur le site web de l’ACI :
http://acimd.univ-lyon1.fr

Chaque dossier doit être 

-  déposé avant le 04 avril 2003 sur le site web de l’ACI:

http://acimd.univ-lyon1.fr

- envoyé par voie postale avec les signatures requises
avant le 11 avril 2003 
(cachet de la poste faisant foi)
à

Ministère délégué à la Recherche et aux Nouvelles Technologies
Direction de la Recherche
Cellule ACI
ACI Masses de données
1, rue Descartes
75231 Paris cedex 05

I - FICHE D’IDENTITE DU PROJET
 
Nom du Projet : (maximum 20 caractères)
GENOTO3D	
 
Titre du Projet : (maximum 3 lignes)
Apprentissage automatique appliqué à la prédiction de la structure tertiaire des protéines	
 
Type du Projet:
Projet de recherche	Projet de recherche multi-thématiques	Projet de recherche avec infrastructure	Autre	
	X			

Durée du projet : 36 mois

Description courte du Projet : (une demi-page  maximum)
L’exploitation fonctionnelle des informations provenant des grands programmes de séquençage des génomes passe nécessairement par la connaissance de la structure tridimensionnelle des protéines. Or, déterminer la structure tridimensionnelle des protéines expérimentalement est une tâche très lourde, qui peut s'avérer parfois impossible à réaliser. L'arrivée massive de données provenant des programmes de séquençage à grande échelle impose la nécessité de passer d’une approche biochimique à une approche bioinformatique, et offre en particulier une excellente opportunité de développer les méthodes de prédiction sur des séquences.

L’objet de ce projet est donc, dans le contexte de la prédiction de la structure tertiaire des protéines, de mettre en évidence des problèmes génériques difficiles et de proposer des méthodes susceptibles de faire progresser l’état de l’art dans le domaine. Pour ce faire, nous nous appuyons sur des approches relevant de l’apprentissage automatique, symbolique et numérique. Notre stratégie est du type «diviser pour régner», avec au final l’intégration des différents niveaux de prédiction au sein d’un seul modèle. Il est en effet possible d’aborder la tâche de manière progressive, au travers de problèmes connexes tels que la prédiction de la structure secondaire et l’identification des ponts disulfures et salins. Nous poursuivrons ainsi des recherches que nous avons déjà effectuées, ou que nous initions actuellement dans le cadre du groupe de travail « Apprentissage et séquences » de l’AS « Apprentissage et bioinformatique ». Actuellement, aucune méthode de prédiction ne met en œuvre une approche hiérarchique et modulaire de ce type, intégrant des systèmes aussi variés. La grande originalité de notre travail, consistera dans cette intégration des solutions apportées aux «sous-problèmes» de manière à atteindre effectivement l’objectif final, ce qui nous semble particulièrement caractéristique des problèmes d’analyse complexe rencontrés sur les grands ensembles de données. 

Les domaines de l’apprentissage que nous explorerons de manière privilégiée sont l’apprentissage statistique, à travers la conception et la mise en œuvre de machines à noyau et de réseaux de neurones récurrents, ainsi que la théorie des automates, avec en particulier l’inférence de  machines de reconnaissance probabilistes (automates probabilistes, HMMs,..). Leur mise en œuvre combinée devra en particulier permettre de prendre compte les dépendances à long terme, encore mal exploitées par les méthodes de prédiction classiques.
	
Les retombées attendues sont importantes, en effet des méthodes fines de prédiction de la structure tertiaire des protéines permettront une meilleure connaissance «mécanistique» des protéines. Ceci intéresse donc l’ensemble de la communauté biologique aussi bien académique qu’industrielle (en particulier l’industrie pharmaceutique). Du point de vue informatique, il est clair que les méthodes développées devraient donner naissance à des outils largement utiles à des domaines de traitement intensif de séquences comme le traitement de textes en langage naturel. Le domaine de l’apprentissage automatique a toujours fortement bénéficié de l’analyse systématique et approfondie d’applications spécifiques.	
 
Coordinateur du projet
Nom	Prénom	Laboratoire (sigle éventuel et nom complet)	
Guermeur
	Yann	LORIA Laboratoire lorrain de recherche en informatique et ses applications	

Organisme de rattachement financier pour le présent projet
 Université Henri Poincaré (UHP)	

Equipes ou laboratoires partenaires (nom complet et éventuellement sigle)
Modèles informatiques en biologie moléculaire (MODBIO), LORIA – UMR 7503, Nancy	
Laboratoire de BioInformatique et RMN structurales, IBCP - UMR 5086, Lyon	
Laboratoire d'Informatique Fondamentale (LIF), UMR 6166, Marseille	
Systèmes et modèles biologiques, bioinformatique et séquences (Symbiose), IRISA / INRIA Rennes	
Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM), UMR5506, Montpellier	
Mathématique Informatique et Génome, INRA, Jouy en Josas	

 II - PRESENTATION DETAILLEE DU PROJET

 

•	Identification du coordinateur et des autres partenaires du Projet :

A1- Coordinateur du Projet :
Un unique coordinateur doit être désigné par les partenaires.

M. ou Mme. Prénom Nom	Yann Guermeur	
Fonction5	Maître de conférences	
Laboratoire (Nom complet et sigle le cas échéant)5	Laboratoire lorrain de recherche en informatique et ses applications (LORIA)	
Adresse5
	LORIA, Campus scientifique, BP239, 54506 Vandoeuvre-lès-Nancy Cedex 	
Téléphone5	03 83 59 30 18	
Fax	03 83 41 30 79	
Mél5	Yann.Guermeur@loria.fr	

A2- Equipes ou laboratoires partenaires du Projet :

Identification de l’équipe ou du laboratoire
Equipe ou Laboratoire	MODBIO, LORIA	
Adresse	LORIA, Campus scientifique, BP239, 54506 Vandoeuvre-lès-Nancy Cedex	

Organisme de rattachement financier de l’équipe pour le présent projet
UHP	

Responsable du projet au sein de l’équipe ou du laboratoire
M. ou Mme. Prénom Nom	Yann Guermeur	
Fonction	Maître de conférences	
Téléphone	03 83 59 30 18	
Fax	03 83 41 30 79	
Mél	Yann.Guermeur@loria.fr	

Autres membres de l’équipe participant au projet
Nom	Prénom	Poste statutaire	% du temps de recherche 
consacré au projet 	
Eveillard
Doctorant (à recruter)	Damien
	Doctorant
Doctorant	30%
100%	

Références : 
Pour chaque (enseignant-)chercheur participant, liste de 3 à 5 publications, logiciels ou brevets les plus significatifs, en relation avec la thématique du projet.
- Guermeur, Y. (2002). Combining discriminant models with new multi-class SVMs. Pattern Analysis and Applications (PAA), Vol. 5, N°2, 168-179.
- Guermeur, Y., Geourjon, C., Gallinari, P. & Deléage, G. (1999). Improved performance in protein secondary structure prediction by inhomogeneous score combination. Bioinformatics, Vol. 15, N°5, 413-421.
- Guermeur, Y. & Paugam-Moisy, H. (1999). Théorie de l’apprentissage de Vapnik et SVM, Support Vector Machines. Apprentissage Automatique, Sebban, M. et Venturini, G. (Eds), Hermès, 109-138.	

A2- Equipes ou laboratoires partenaires du Projet :

Identification de l’équipe ou du laboratoire
Equipe ou Laboratoire	Bioinformatique et RMN structurales	
Adresse	IBCP, UMR 5086, 7 Passage du Vercors, 60 367 Lyon cedex 07	

Organisme de rattachement financier de l’équipe pour le présent projet
CNRS	

Responsable du projet au sein de l’équipe ou du laboratoire
M. ou Mme. Prénom Nom	Christophe Geourjon	
Fonction	Ingénieur de Recherche CNRS	
Téléphone	04 72 72 26 47	
Fax	04 72 72 26 04	
Mél	c.geourjon@ibcp.fr 	

Autres membres de l’équipe participant au projet
Nom	Prénom	Poste statutaire	% du temps de recherche 
consacré au projet 	
Jambon
A recruter	Martin
	Doctorant
Post-doc	30%
100%	

Références : 
Pour chaque (enseignant-)chercheur participant, liste de 3 à 5 publications, logiciels ou brevets les plus significatifs, en relation avec la thématique du projet.
- Guermeur, Y., Geourjon, C., Gallinari, P. & Deléage, G. (1999). Improved performance in protein secondary structure prediction by inhomogeneous score combination. Bioinformatics, 15, 413-421.
- Geourjon, C., Combet, C., Blanchet, C. & Deléage, G. (2001). Identification of related proteins with weak sequence identity using secondary structure information. Protein science, 10, 788-797
- Combet, C., Jambon, M., Deléage, G. & Geourjon, C. (2002). Geno3D: Automatic comparative molecular modelling of protein. Bioinformatics, 18, 213-214
- Jambon, M., Imberty, A., Deléage, G. & Geourjon, C. (2003). A new bioinformatic approach to detect common 3D sites in protein structures. Proteins, Structure function and genetics, sous presse
- Errami, M., Geourjon, C. & Deléage, G. (2003). Conservation of amino acids into multiple alignments involved in pairwise interactions in three-dimensionnal protein structures. Journal of Bioinformatics and Computational Biology, sous presse	

A2- Equipes ou laboratoires partenaires du Projet :

Identification de l’équipe ou du laboratoire
Equipe ou Laboratoire	LIF, équipe BDA	
Adresse	Centre de Mathématiques et d'Informatique (CMI) 
Technopôle de Château Gombert, 39, rue F. Joliot Curie 
13453 MARSEILLE CEDEX 13 FRANCE	

Organisme de rattachement financier de l’équipe pour le présent projet
CNRS	

Responsable du projet au sein de l’équipe ou du laboratoire
M. 	François DENIS	
Fonction	Professeur	
Téléphone	04 91 11 36 05	
Fax	04 91 11 36 02	
Mél	fdenis@cmi.univ-mrs.fr 	

Autres membres de l’équipe participant au projet
Nom	Prénom	Poste statutaire	% du temps de recherche 
consacré au projet 	
Capponi
Esposito	Cécile
Yann
	Maître de conférences
Doctorant	20%
30%	

Références : 
Pour chaque (enseignant-)chercheur participant, liste de 3 à 5 publications, logiciels ou brevets les plus significatifs, en relation avec la thématique du projet.
- François Denis, Yann Esposito (2003), Residual languages and probabilistic automata, to appear in the proceedings of ICALP03.
- F. Denis, O. Gascuel (2003), On the Consistency of the Minimum Evolution Principle of Phylogenetic Inference, Discrete Applied Mathematics, 127 (1), 63-77, 2003.
- Yann Esposito, Aurélien Lemay, François Denis, Pierre Dupont (2002), Learning probabilistic residual finite state automata, ICGI'2002, LNAI 2484, 77-91, 2002. . 
- F. Denis, A. Lemay, A. Terlutte, Learning Regular Languages using RFSA, in Proceedings of the 12th International Conference on Algorithmic Learning Theory (ALT'01),  LNAI 2225, 348-363, 2001. Version longue à paraître dans TCS.
- F. Denis, A. Lemay, A. Terlutte (2000), Learning regular languages using non deterministic finite automata, ICGI'2000. 
- J. Chabalier, G. Fichant, C. Capponi (2003), La classification récursive dans AROM application à l'identification des systèmes biologiques. Revue L'Objet, RTSI 9:167-181, Editions Hermès, Paris.
- C. Capponi, J. Chabalier, Y. Quentin, G. Fichant (2001), A Knowledge Base for Biological Integrated Systems in IEEE Intelligent Systems, Special Issue: Intelligent Systems inBiology, 16(6):52-61.	

A2- Equipes ou laboratoires partenaires du Projet :

Identification de l’équipe ou du laboratoire
Equipe ou Laboratoire	IRISA / INRIA Rennes, projet Symbiose	
Adresse	Campus de Beaulieu, 35042 Rennes cedex	

Organisme de rattachement financier de l’équipe pour le présent projet
INRIA	

Responsable du projet au sein de l’équipe ou du laboratoire
M. 	Jacques NICOLAS	
Fonction	CR INRIA	
Téléphone	02 99 84 73 12	
Fax	02 99 84 71 71	
Mél	Jacques.Nicolas@irisa.fr 	

Autres membres de l’équipe participant au projet
Nom	Prénom	Poste statutaire	% du temps de recherche 
consacré au projet 	
Coste
Andonov
Jacquemin
Leroux
Mescam
A recruter	François
Rumen
Ingrid 
Aurélien
Yoann	CR INRIA
Prof. en détachement INRIA
Doctorante
Doctorant
Doctorant
Doctorant	30%
30%
100%
50%
75%
100%	

Références : 
Pour chaque (enseignant-)chercheur participant, liste de 3 à 5 publications, logiciels ou brevets les plus significatifs, en relation avec la thématique du projet.
- Cooperative metaheuristics for exploring proteomic data, R. Gras, D. Hernandez, P. Hernandez, N. Zangger, Y. Mescam, J. Frey, O. Martin, J. Nicolas,  R. D. Appel, AI Review Special Issue on Life Sciences, à paraître 2003.
- Solving protein threading problem in parallel, N. Yanev and R. Andonov, HiCOMB’03, high Performance Computational Biology, in conjunction with the International Parallel and distributed Processing Symposium, 2003, april, Nice, France
- Efficient ambiguity detection in C-NFA, a step toward inference of non deterministic automata , F. Coste, D.Fredouille, ICGI 2000, Grammatical inference: algorithms and applications, Lisbonne , 25-38 , september , 2000
- Apprentissage d'automates classifieurs en inférence grammaticale, F.Coste, Ph.Thesis, IRISA/Université de Rennes 1, 27 janvier 2000
- A symbolic-numeric approach to find patterns in genomes : Application to the translation initiation sites of E. coli  C. Delamarche, P. Guerdoux-Jamet, R. Gras et Jacques Nicolas, Biochimie, 81, Elsevier, 1999
- Inference of finite automata: reducing the search space with an ordering of pairs of states, F.Coste, J.Nicolas, 10th European Conference on Machine Learning (ECML'98), Chemnitz, Germany, 1998	

A2- Equipes ou laboratoires partenaires du Projet :

Identification de l’équipe ou du laboratoire
Equipe ou Laboratoire	LIRMM / Equipe MAB	
Adresse	161, rue Ada 
34392 MONTPELLIER Cedex 5	

Organisme de rattachement financier de l’équipe pour le présent projet
INRIA	

Responsable du projet au sein de l’équipe ou du laboratoire
M. 	Laurent BREHELIN	
Fonction	CR2 CNRS	
Téléphone	04 67 41 86 71	
Fax	04 67 41 85 00	
Mél	Brehelin@lirmm.fr	

Autres membres de l’équipe participant au projet
Nom	Prénom	Poste statutaire	% du temps de recherche 
consacré au projet 	

Gascuel
Duprat	
Olivier
Elodie	
DR CNRS
Doctorante	
20,00%
20,00%

Références : 
Pour chaque (enseignant-)chercheur participant, liste de 3 à 5 publications, logiciels ou brevets les plus significatifs, en relation avec la thématique du projet.
- Bréhélin, L., Gascuel, O., et Caraux, G. (2001). Hidden Markov models with patterns to learn boolean vector sequences and application to the built-in self-test for integrated circuits. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23(9), pages 997-1008.
- Bréhélin, L. (2001). Modèles de Markov cachés et apprentissage par fusions d'états : algorithmes, applications, utilisations pour le test de circuits intégrés. PhD thesis, Université Montpellier II, LIRMM.
-Bréhélin, L. et Gascuel, O. (2000). Le temps, l'espace et l'évolutif en sciences du traitement de l'information, chapitre "Modèles de Markov cachés et apprentissage de séquences", pages 407-421. Cépadues - éditions, H. Prade, R. Jeansoulin et C. Garbay.
Desper, R. et Gascuel, O. (2002) Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle. Journal of Computational Biology 19(5), 687-705, 2002.
- Gascuel O. et al. (groupe SYMENU) (1998) Twelve numerical, symbolic and hybrid supervised classification methods. 
International Journal of Pattern Recognition and Artificial Intelligence 12(5), 517-572.	

A2- Equipes ou laboratoires partenaires du Projet :

Identification de l’équipe ou du laboratoire
Equipe ou Laboratoire	Mathématique Informatique et Génome, INRA	
Adresse	Centre de Recherche de Jouy, Domaine de Vilvert,78352 Jouy-en-Josas cedex 	

Organisme de rattachement financier de l’équipe pour le présent projet
INRA	

Responsable du projet au sein de l’équipe ou du laboratoire
M. 	Jean-François Gibrat	
Fonction	DR INRA	
Téléphone	01 34 65 28 97	
Fax	01 34 65 29 01 	
Mél	gibrat@jouy.inra.fr	

Autres membres de l’équipe participant au projet
Nom	Prénom	Poste statutaire	% du temps de recherche 
consacré au projet 	
Martin
Hennequet
X (en cours de recrutement)
A recruter	Juliette
Christelle
	Doctorante
Ingénieur d’étude
CR2
CDD	100%
20%
75%
100%	

Références : 
Pour chaque (enseignant-)chercheur participant, liste de 3 à 5 publications, logiciels ou brevets les plus significatifs, en relation avec la thématique du projet.
- Gibrat, J.-F. and Marin, A. (2003). Stratégies permettant d'assigner une fonction in silico aux séquences protéiques issues de projets de génomiques. In Dynamique du génome végétal, (J.-F. Maurot-Gaudry and J.-F. Briat, ed.). Editions-INRA.  Sous presse.
- Cazalis, R., Aussenac, T., Rhazi, L., Marin, A. and Gibrat, J.-F. (2003).  Homology modeling and molecular dynamics simulations of the N-terminal domain of wheat high molecular weight glutenin subunit 10. Protein Sci. 12 34-43.
- Marin, A., Pothier, J., Zimmerman, K. and Gibrat, J.-F.  (2002).  FROST: a filter based fold recognition method. Proteins: Struct. Funct. Genet. 49 493-509.
- Marin, A., Pothier, J., Zimmermann, K. and Gibrat, J.-F. (2002). Protein threading statistics: An attempt to assess the significance of a fold assignment to a sequence. In Protein structure prediction: Bioinformatics approach, (I. F. Tsigelny, ed.), chapter 9, 227-262. International University Line, La Jolla, CA.
- Gibrat, J.-F. and Marin, A. (2002). In silico functional analysis. BIOforum International Edition Internationale. 6 2-3.	

B - Description du projet
 
B1 – Objectifs et contexte :
On précisera, en particulier, les verrous scientifiques et technologiques à dépasser, l’état de l’art ainsi que les projets concurrents ou similaires connus dans le contexte national et international, en particulier ceux auxquels les équipes du projet participent.

Ce projet rassemble des équipes impliquées dans :
-	la bioinformatique structurale des protéines. Ces laboratoires apportent en particulier la connaissance du domaine, les bases de données, une expertise forte et reconnue 
-	l’apprentissage automatique, recouvrant dans leur ensemble une large partie des techniques et méthodes de cette discipline. 

Objectif et contexte biologique :
Les projets de séquençage de génomes produisent des masses énormes de données hétérogènes. Le processus d'annotation de ces génomes consiste, à partir de ces données brutes, à inférer des connaissances sur la biologie des organismes considérés. Le but ultime des biologistes est donc de comprendre comment le génome permet d'expliquer les propriétés biologiques de l'organisme (le phénotype) en explorant tous les niveaux intermédiaires : cellule, tissus, organes, physiologie. 
Ce travail d'annotation nécessite l'intégration de données et résultats provenant de différentes sources  : 
- des expériences à grande échelle comme des expériences de transcriptome, de   protéome, etc. ; 
-  des données issues des bases de données biologiques qu'elles soient génériques ou spécifiques ; 
-  de l'exploitation (automatique ou non) de la littérature biologique existante (fouille de texte) ; 
-  des méthodes d'analyse in silico.
 Cette dernière source de données et de résultats est particulièrement importante. Les méthodes d'analyse de la bioinformatique jouent un rôle central dans l'exploitation des données génomiques. Dans ce projet de recherche nous nous focaliserons sur un point important, à savoir : comment passe-t-on de la séquence en acides aminés d'une protéine (qui est facilement déduite une fois que l'on connaît le gène correspondant) à sa fonction?
La fonction d'une protéine dépend d'une manière étroite de sa structure tridimensionnelle (3D). Il est donc nécessaire de connaître la structure 3D d’une protéine pour comprendre sa fonction au niveau moléculaire. Expérimentalement on sait que la structure 3D (et donc la fonction) dépend uniquement de la séquence en acides aminés. Comprendre comment la séquence en acides aminés spécifie une structure 3D particulière est un des grands problèmes non encore résolu de la biologie moléculaire. 
La connaissance de cette structure 3D est très lourde à obtenir expérimentalement, parfois même impossible d’où la nécessité de développer des méthodes de prédiction.
Notre objectif est de proposer aux biologistes une solution globale à ce problème. Par ailleurs, afin que les méthodes développées au cours de ce projet soient facilement disponibles elles seront mises à disposition via les serveurs web NPS@ (analyse de séquences de protéine, http://npsa-pbil.ibcp.fr) et Geno3D (modélisation moléculaire, http://geno3d-pbil.ibcp.fr) . Ces serveurs développés à l’IBCP par l’équipe BioInformatique et RMN structurales (équipe impliquée dans ce projet) sont déjà largement utilisés et reconnus par la communauté des biologistes (en 2002 ils ont reçu en moyenne 2 523 requêtes quotidiennes par la communauté internationale : 30% USA, 25% Europe hors France, 20% France et 25% reste du monde).

Objectif et contexte informatique :
Les méthodes développées par l'apprentissage automatique constituent un complément indispensable des méthodes traditionnelles des statistiques. Leur force réside d'une part dans la très grande diversité et originalité des dispositifs qui ont été inventés pour faire de l'inférence (réseaux de neurones, machines à vecteurs support, algorithmes d'inférence grammaticale, etc) et, d'autre part, dans le fait que ces dispositifs peuvent être appliqués à des données séquentielles, un type d'objet plus classique en informatique qu'en statistique. La participation à ce projet de chercheurs ayant une bonne expérience dans l'inférence à partir de données séquentielles, et ce par des méthodes couvrant un large spectre des méthodes utilisées en apprentissage, constitue un atout important. Parmi les verrous scientifiques et les problèmes connexes que ce projet permettra d'attaquer, on peut signaler : 1. l'élaboration de méthodes d'inférence à partir de données séquentielles permettant de tenir compte de dépendances à distance ; 2. l’adaptation d’algorithmes d’apprentissage automatique aux données séquentielles ; 3. l'intégration de plusieurs méthodes concurrentes d'apprentissage automatique.

Certaines des approches que nous souhaitons développer dans ce projet (en particulier pour les machines à vecteurs de support) sont très consommatrices de ressources cpu. Par ailleurs, ce projet se situe dans un contexte de génomique c’est-à-dire dans un contexte de flux de données (séquence de protéine) important. Il est donc opportun de souligner que 3 des équipes de ce projet sont elles-mêmes impliquées dans les projets de grilles de calcul pour la biologie (Laboratoire Bioinformatique et RMN structurales (IBCP) projets GPS@ de DataGRID et GriPPS de l’ACI GRID, IRISA et MIG projet GENOGRID de l’ACI GRID). 

B2 – Description du projet : (5 à 10 pages)
Entre autres, le caractère innovant du projet (concepts, technologies, expériences …) devra être explicité et la valeur ajoutée des coopérations entre les différentes équipes sera discutée.

Un concept clé de la biologie est la  notion d'homologie. Deux gènes ou protéines sont homologues si ils (elles) sont le résultat d'un processus d'évolution divergente à partir d'un ancêtre commun. Cette propriété d'homologie joue un rôle central lors de l'annotation de nouveaux génomes car deux protéines homologues ont bien souvent conservé des fonctions voisines. Le principe fondamental de l'analyse fonctionnelle in silico (l'attribution d'une fonction à une séquence protéique) est donc le suivant : si l'on peut établir une relation d'homologie entre une protéine inconnue, issue d'un projet de séquençage, et une protéine des banques de données dont on connaît la fonction, il est alors possible de transférer cette fonction, sous certaines conditions, à la protéine inconnue. 

Il existe deux façons de mettre en évidence une relation d'homologie entre deux protéines. La première consiste à s'intéresser à la ressemblance des séquences en acides aminés. Les protéines homologues dérivant d'un ancêtre commun, il arrive bien souvent qu'il en reste des traces évidentes au niveau des séquences des protéines <<descendantes>>. Les techniques qui permettent de mettre en évidence une relation d'homologie dans ce cas (pour fixer les idées quand il y a plus de 30% de résidus conservés dans les séquences), telle que BLAST ou FASTA font maintenant partie des outils standard de tous les biologistes moléculaires. Dans un tel cas il n'est pas nécessaire de passer par l'intermédiaire de la structure 3D si l'on s'intéresse uniquement à la fonction d'un point de vue général. Si l'on désire étudier la fonction d'un point de vue moléculaire, par exemple pour concevoir un inhibiteur d'un enzyme d'un pathogène, et si la structure 3D de la protéine homologue est connue, il est relativement aisé de bâtir un modèle de la structure 3D par des techniques de modélisation comparative (ou modélisation par homologie). Toutes les techniques mentionnées ci-dessus sont maintenant bien au point et le biologiste se trouve dans un cas relativement facile à traiter.

Ce n'est malheureusement pas toujours le cas. L'ancêtre commun peut être très ancien et les séquences peuvent avoir divergé au point que les méthodes décrites précédemment ne sont plus capables de mettre en évidence une relation d'homologie. Dans ce cas, on utilise une autre propriété des protéines homologues, à savoir que leurs structures 3D sont, globalement, toujours bien conservées. Les techniques qui se fondent sur cette propriété sont appelées méthodes de reconnaissance de repliements (le repliement est ici synonyme de structure 3D). On utilise la structure 3D pour remonter à la fonction de la protéine. Ce sont des méthodes qui sont en cours de développement depuis une dizaine d'années et qui commencent graduellement à arriver à maturité, bien que de nombreux problèmes techniques restent à résoudre comme nous allons le voir par la suite. Le biologiste se trouve alors en face d'un problème assez difficile à résoudre qui nécessite encore une expertise certaine pour exploiter pleinement les résultats.
Les deux cas décrits précédemment utilisent des connaissances sur les fonctions et les structures 3D de protéines stockées dans les bases de données. Le cas le plus difficile à traiter pour les biologistes concerne les protéines pour lesquelles on ne connaît pas de protéine homologue et qui ont vraisemblablement une structure 3D jamais encore observée. Il faut alors essayer de prédire cette structure à partir de la séquence en acides aminés (modélisation de novo). C'est une tâche très difficile qui a déjoué  tous les efforts des biologistes au cours des 40 dernières années (la première structure de protéine date de 1959). Depuis 3-4 ans il semble cependant qu'une solution à ce problème puisse être envisagée (voir les conclusions des compétitions CASP4 et CASP5). Cette perspective d'une solution au problème de modélisation de novo est due en partie à l'accroissement constant du nombre de structures 3D résolues par des techniques expérimentales (diffraction des rayons X et Résonance Magnétique Nucléaire), à l'amélioration continue de la puissance de calcul disponible et à l'apparition de nouvelles techniques algorithmiques puissantes pour s'attaquer à ce problème.

La proposition que nous soumettons ici a pour but, d'une part, de tenter de résoudre les problèmes techniques qui brident encore le développement des méthodes de reconnaissance de repliements et d'autre part, de proposer un certain nombre d'angles d'attaque originaux au problème de la modélisation de novo, fondés sur des techniques informatiques émergentes.

Deux approches pour prédire la structure 3D d’une protéine :

Prédiction par threading :
Le principe des méthodes de reconnaissance de repliements est d'aligner directement la séquence de la protéine inconnue sur un jeu de structures 3D afin d'estimer la compatibilité éventuelle de cette séquence avec une de ces structures. Ces méthodes sont donc fondées sur 4 composants : 
-	une bibliothèque de structures 3D représentatives des protéines connues 
-	une fonction de score empirique mesurant l'adéquation séquence/structure 3D 
-	un algorithme permettant d'obtenir l'alignement optimal de la séquence sur la structure 3D 
-	une analyse statistique des résultats bruts pour en évaluer la significativité
Les verrous scientifiques et techniques à dépasser concernent les 3 derniers points décrits ci-dessus. La fonction de score mentionnée précédemment est, en fait, constituée pour des raisons d'efficacité d'un certain nombre de fonctions indépendantes fondées sur des propriétés physico-chimiques différentes. Dans la méthode FROST développée dans l'unité MIG, ces différentes fonctions apparaissent sous la forme de filtres indépendants fournissant chacun un résultat. Une manière de combiner ces résultats est d'utiliser des techniques de réseau de neurones (Jones 1999) mais nous envisageons plutôt d'utiliser des techniques de machines à vecteurs support (SVM). Il s'agit de classer les paires séquences/structures 3D en une classe correspondant aux paires <<correctes>> où la séquence correspond bien à la structure 3D et une classe correspondant aux paires <<incorrectes>> où la séquence n'a rien à voir avec la structure 3D sur la base des différents résultats obtenus avec les filtres.
Certaines des fonctions de score utilisées font intervenir des termes impliquant des paires d'acides aminés dans la séquence. Avec ce type de fonction <<non locale>>, il est impossible d'utiliser des méthodes dérivées des techniques de programmation dynamique qui sont massivement utilisées dans le domaine de l'analyse de séquences. De fait il a été démontré que le problème de l'alignement d'une séquence sur une structure 3D est NP-complet si on l'envisage dans toute sa généralité. Ce problème d'alignement constitue donc un goulot d'étranglement sévère pour les méthodes de reconnaissance de repliements au vu de la masse de données importante à traiter. C'est d'ailleurs une des raisons pour laquelle FROST a été l'un des premiers logiciels porté sur la grille de calcul GENOGRID. Cependant, des travaux préliminaires de R. Andonov (U. de Valenciennes et IRISA Rennes) et N. Yanev (U. de Sofia) en utilisant différentes formulations basées sur la programmation entière mixte (Mixed Integer Programming) tendent à montrer que des instances réelles du problème peuvent être résolues par des algorithmes polynomiaux (Programmation Linéaire) dans la plupart des cas (logiciel CIPLEX).  De plus, comparé aux méthodes classiques de <<branch & bound>>, cet algorithme semble très performant. Nous désirons donc explorer plus en détails cette piste et étendre cette étude en comparant ses performances à celles d'une méthode de <<branch & bound>> classiquement utilisée dans ce domaine (Lathrop & Smith, 1996), à une nouvelle méthode de <<branch & bound>> développée dans l'unité, ainsi qu’à diverses méthodes heuristiques. 
Les méthodes de reconnaissance de repliements pour une fonction de score particulière fournissent un score (optimal) qui mesure l'adéquation entre la séquence et la structure 3D considérée. Il est donc nécessaire d'évaluer la significativité statistique de ce score. Est-il très rare de voir apparaître un tel score ? On peut alors penser que l'adéquation entre la séquence et la structure est réelle. Au contraire, s'il est très facile d'obtenir un score égal ou supérieur au score observé il est très vraisemblable que l'alignement soit fortuit et que la séquence n'ait pas de relation paticulière avec la structure 3D considérée. Cette étude de la significativité du score est cruciale pour pouvoir utiliser les méthodes de reconnaissance de repliements en pratique. Pour le moment la significativité du score est estimée empiriquement : on calcule des distributions de scores pour toutes les structures 3D utilisées. Inutile de dire que ce calcul s'ajoutant au problème précédent d'obtention de l'alignement optimal d'une séquence sur une structure impose des charges de calcul très lourdes.

Nous avons commencé à explorer une piste permettant de calculer théoriquement la distribution des scores à partir des caractéristiques du problème : fonction de score utilisée, structure 3D considérée, etc.. Ce travail est encore très préliminaire et nécessite des efforts de développement important pour être exploitable en pratique. 

Prédiction de novo :
Pendant très longtemps, la prédiction de la structure 3D à partir de la séquence en acides aminés a été un problème considéré comme insoluble. Pour la première fois lors de la compétition CASP4 en 2000 (Critical Assessment of techniques for Protein Structure Prediction), des progrès notables ont été enregistrés. Cette tendance s'est confirmée et accélérée lors de CASP5 en 2002. Il semblerait que le champ soit enfin mûr pour que l'on puisse envisager des avancées décisives. Pour le moment ce domaine de recherche est largement dominé par une seule équipe : celle de D. Baker à l'Université de Washington à Seattle qui a effectué la percée conceptuelle lors de CASP4.  D'autres équipes, américaines pour la plupart, sont en train d'essayer de combler le retard. Il est donc très important de se positionner dans ce domaine pendant qu'il en est encore temps.

Les techniques initiales de prédiction de la structure 3D à partir de la séquence en acides aminés visaient à reproduire le phénomène physico-chimique réel. On construisait un modèle plus ou moins détaillé de la molécule, on décrivait les interactions entre atomes par des modèles physiques et on recherchait le minimum d'énergie libre du système par des techniques de la physique statistique comme la dynamique moléculaire ou des simulations de Monte Carlo.
Cette approche s'est heurtée à différents problèmes, le plus formidable, et sans doute totalement rédhibitoire, étant que l'espace conformationnel à explorer est bien trop vaste pour les ordinateurs actuels et à venir. 
Le groupe de Baker a contourné ce problème fondamental en faisant remarquer que la structure 3D d'une protéine est atteinte en maintenant la plupart des structures locales dans un état énergétiquement favorable, c'est-à-dire que la chaîne polypeptidique localement adopte une conformation stable et que le repliement global qui est responsable de la structure 3D ne perturbe que modérément cet ordre local. Il se trouve que l'on connaît maintenant suffisamment de structures 3D pour disposer d'au moins un exemplaire de toutes les structures locales adoptées par des fragments de séquence dans les protéines. Baker et ses collègues ont donc proposé une stratégie en 3 points pour s'attaquer au problème de la modélisation de novo : 
-	extraire des bases de données des fragments pertinents correspondant à la structure locale adoptée par des parties de la séquence en acides aminés.
-	assembler ces fragments en différentes structures 3D plausibles au moyen d'une fonction empirique (knowledge-based) décrivant les principales propriétés des structures.
-	parmi toutes les structures 3D générées ainsi identifier celle qui est la plus proche de la structure réelle.
Tous ces points font encore l'objet d'une recherche intensive visant à trouver des améliorations (en particulier le dernier point est pour le moment encore très loin d'avoir une solution satisfaisante dans tous les cas). 

Deux problèmes connexes :

La prédiction de la structure 3D des protéines est donc un problème particulièrement difficile et nous envisageons de l'attaquer en nous concentrant sur deux problèmes intermédiaires.

Prédiction des ponts disulfures et des ponts salins

La première approche que nous avons choisie consiste à prédire les ponts disulfures (liaison covalente entre 2 cystéines) et les ponts salins (liaison non covalente entre 2 acides aminés de charge opposée) dans les protéines à partir de la séquence. En effet, du fait du repliement tertiaire, des acides aminés séquentiellement éloignés peuvent se retrouver proches dans l’espace. Aussi, la capacité de prédire à partir de la séquence les acides aminés en interaction 3D permet de « contraindre » le repliement, ceci pouvant par exemple permettre de reconnaître le repliement concerné. Des travaux ont déjà été réalisés sur les ponts disulfures en cherchant à prédire si les cystéines sont impliquées dans un pont disulfure (Fariselli et al., 1999, Fiser et Simon, 2000, Frasconi et al., 2002). Par contre très peu de travaux tentent de prédire les paires de résidus impliqués. Or c’est cette prédiction qui apporterait véritablement de l’information tridimensionnelle. Au niveau des ponts salins (beaucoup plus fréquents que les ponts disulfures) il n’existe à notre connaissance pas de travaux ayant un objectif prédictif. Cette approche est celle qui a été initiée au sein du groupe de travail « Apprentissage et séquence » de l’AS 80 du département STIC.

Améliorer la qualité des prédictions de la structure secondaire des protéines.

La deuxième approche consiste à améliorer la qualité des prédictions de la structure secondaire des protéines. En effet, une protéine est organisée en éléments de structure secondaire appelés hélice a et brin b. De très nombreux travaux ont porté sur la prédiction de ces éléments (Rost et Sander, 1993, Geourjon et Deléage, 1995, King et Sternberg, 1996, Guermeur et al., 1999, Kloczkowski et al., 2002, Pollastri et al., 2002). A ce jour la qualité que l’on peut espérer (prédiction selon 3 états structuraux) est de l’ordre de 75%.

Ces angles d’attaques sont complémentaires et peuvent être utilisés en combinaison afin d’identifier le repliement d’une protéine à partir de sa séquence. Par ailleurs, ces approches peuvent être utiles aussi bien pour la prédiction par threading que pour la prédiction de novo.

Méthodes et stratégies envisagées en apprentissage automatique

Les méthodes connexionnistes ont déjà connu d’importants succès en bioinformatique, particulièrement pour les problèmes de traitement de séquences. Elles se trouvent ainsi au cœur de certains des systèmes les plus performants pour l’identification des zones codantes de l’ADN, des régions inter ORF, ou la prédiction de structures (ARN, protéines…). Cependant, les architectures standard, particulièrement les perceptrons multi-couches, ont montré leurs limites dans la prise en compte des interactions à distance. Pour pallier cette insuffisance, des systèmes intégrant des réseaux récurrents ont été développés, qui ont permis une avancée significative dans certains domaines, en particulier en prédiction de la structure secondaire des protéines (méthode SSpro, Pollastri et al., 2002). Cependant, ces systèmes n’ont pas entièrement résolu les problèmes de prédiction de structures des protéines, et celui de la structure tertiaire demeure aujourd’hui encore largement ouvert.

Une extension aux SVM des Hidden Neural Networks

Une première approche informatique de ces problématiques concerne les modèles de Markov cachés. Ces modèles sont très largement utilisés dans l’analyse de séquences en bioinformatique pour représenter un modèle de protéine (Grate et al.). Ils servent en particulier d’éléments de base aux approches type “profile” et à certaines approches d’homologie éloignée dans lesquelles le score2 obtenu par la protéine sur un modèle représente en quelque sorte la probabilité d’appartenir au type de protéine représenté par le modèle de Markov caché. Ainsi, améliorer ces modèles peut avoir comme conséquences d’améliorer de nombreuses techniques d’homologie éloignée. De telles améliorations ont été étudiées par différents chercheurs. Celle qui nous intéresse plus particulièrement est celle de Krogh et Riis qui ont défini un modèle de Markov caché à base de réseaux de neurones. Ce modèle appelé Hidden Neural Network utilise des réseaux de neurones pour calculer les probabilités de transition du modèle. Les résultats expérimentaux sont très bons sur des problèmes de reconnaissance vocale. Nous nous proposons d’analyser ce modèle dans le cadre de la bioinformatique et de l’étendre en remplaçant les réseaux de neurones par des machines à vecteurs de support dont les performances sont en général aussi bonnes voire meilleures que les réseaux de neurones classiques. Ce travail ne représente pas une extension directe compte tenu de l’algorithme d’apprentissage des machines à vecteurs de support qui est très différent de celui des réseaux de neurones.

Machines à noyau

L’un des progrès les plus significatifs de la théorie statistique de l’apprentissage effectués ces dernières années est la spécification du principe inductif de minimisation structurelle du risque (Vapnik, 1982). Ce principe est à la base de toute une famille de machines à noyau, parmi lesquelles on compte en particulier les machines à vecteurs support (SVM). Ces machines prennent actuellement une place importante en bioinformatique, où elles tendent à remplacer les systèmes connexionnistes usuels (Furey et al. 2000, Zien et al., 2000). Elles présentent en effet deux avantages importants. D’une part, les  moyens qu’elles procurent pour contrôler les performances en généralisation permettent d’éviter le sur-apprentissage si souvent rencontré en pratique. D’autre part, le choix du noyau permet d’incorporer de manière explicite de l’information sur le problème traité. Il y a quelques années, David Haussler et Tommi Jaakkola (Jaakkola et Haussler, 1998, Haussler, 1999), ainsi que Chris Watkins (Watkins, 1999) ont introduit de nouvelles méthodes pour construire des noyaux opérant sur des structures discrètes telles que les séquences et les graphes. Actuellement, une grande partie des efforts de la communauté porte ainsi sur la conception et la mise en œuvre de noyaux dédiés aux données séquentielles (Jaakkola et al. 1999, Vert, 2002). Depuis plusieurs années, l’équipe MODBIO a développé la théorie et la programmation des SVM multi-classes (Guermeur et al. 2000, Guermeur, 2002). Nous diffusons ainsi des logiciels capables de traiter de grandes bases de séquences biologiques, pour la prédiction de la structure secondaire, l’identification des séquences inter ORF, des petits ARN… Dans le cadre de ce projet, nous entendons utiliser plus particulièrement ces machines pour prédire simultanément la structure secondaire et les ponts. Cela nous conduira à spécifier de nouveaux noyaux dédiés aux séquences. Les problèmes d’apprentissage sous-jacents sont multiples. Le plus fondamental est sans doute celui du lien entre modélisation et pouvoir discriminant. Ce problème est bien illustré par l’exemple suivant. Le meilleur noyau actuellement disponible pour les séquences biologiques est calculé par la procédure « avant » associée à un type de HMM particulier nommé P-HMM (Durbin et al., 1998). Il apparaît clairement comme le mieux à même de prendre en compte les principaux phénomènes de l’évolution, comme les substitutions ou les insertions/délétions. Cependant, il n’est pas encore exploitable par des machines à noyau, ceci pour deux raisons. D’une part, son temps de calcul est prohibitif ; d’autre part, son pouvoir discriminant, avant tout post-traitement, est faible. Il produit en effet une matrice de Gram quasi-diagonale, ce qui revient à considérer que tous les exemples d’apprentissage sont orthogonaux.

Inférence de HMM et d'automates probabilistes

Les automates probabilistes (PA) sont des objets formels permettant de modéliser des distributions de probabilités définies sur des ensembles de mots, appelées aussi langages stochastiques.  Ils sont composés d'une structure qui est un automate fini (NFA) et d'un ensemble de paramètres associés aux états et aux transitions représentant la probabilité pour un état d'être initial ou terminal, ou la probabilité qu'une transition soit empruntée. Les automates probabilistes ont la même expressivité que les Modèles de Markov Cachés (HMM) et peuvent donc être utilisés dans les mêmes conditions, en particulier en bio-informatique.  Le problème consistant à inférer un automate probabiliste (structure et paramètres) à partir de données séquentielles est encore un sujet de recherche largement ouvert. Dans la plupart des applications des automates probabilistes ou des HMMs, soit la connaissance du domaine permet de choisir une structure a priori (cf le modèle standard pour l'analyse des séquences biologiques), soit l'on part d'un automate possédant une structure de graphe complet. On se doute qu'il y a sans doute mieux à faire et certains travaux ont confirmé cette intuition : rechercher des structures à partir des données est souvent préférable à poser des structures a priori. Si la structure recherchée est un automate déterministe, des algorithmes ont déjà été proposés donnant des résultats encourageants. Ces résultats ne sont pour l'instant pas confirmés en génomique, ces algorithmes restant relativement frustres au niveau de l'apprentissage de la structure elle-même, ce qui laisse ouvert un vaste champ de recherche pour améliorer leurs performances. Une autre piste à explorer consiste à augmenter le pouvoir d'expressivité des modèles appris. En effet, et contrairement au cas non probabiliste, les automates déterministes probabilistes ont une expressivité très inférieure à celle des automates probabilistes dans leur ensemble. Un premier axe de recherche est donc le développement de solutions algorithmiques pour l'inférence de structures d'automates non déterministes. Nous avons déjà mené certains travaux dans ce sens, notamment sur l'apprentissage de la structure de HMMs via des algorithmes par fusions d'états (Bréhélin 2001). Ces travaux préliminaires nécessitent d'être étendus et adaptés aux spécificités des séquences protéiques. Les retombées de ces travaux seraient immédiates, puisqu'elles permettraient d'améliorer sensiblement les actuels systèmes de reconnaissance de protéines basés sur des automates à structure fixée, tels que les HMMs profils. Un autre axe de recherche possible, pour lequel une thèse est en cours (I. Jacquemin) est de déplacer la phase d’apprentissage du modèle lui-même au contrôle de l’expressivité de ce modèle, via l’utilisation de langages de contrôle. Ainsi, on ne s’intéresse plus directement à l’inférence du système de règles de la grammaire mais à l’inférence du langage des suites de règles permises dans l’utilisation de la grammaire. Ceci permet de grimper dans la hiérarchie de Chomsky tout en conservant un langage de contrôle régulier. 

Le traitement des interactions distantes

D'un autre côté, il est clair que des relations à longue distance interviennent dans la structure des protéines. Ces relations ne peuvent être prises en compte de manière satisfaisante par les automates classiques, même non déterministes. Des modèles plus complexes doivent donc être définis, qui puissent générer des langages plus riches. Or, il est bien connu que l'extension de l'expressivité d'un langage s'accompagne généralement d'une augmentation drastique du temps de calcul nécessaire à son traitement et à son apprentissage. Cette extension doit donc être effectuée précautionneusement, en essayant de trouver un bon compromis entre expressivité et temps de calcul. Une première approche pour cela est l'utilisation de modèles mixtes (tels que les HMMs couplés à des SVMs) décrite plus haut. Une autre approche est d'essayer d'étendre directement la classe des automates pour obtenir une nouvelle classe plus expressive. Nous travaillons sur une telle classe, les automates probabilistes à états résiduels (PRFA), dont l'expressivité est nettement plus importante que celle des automates stochastiques à structure déterministe, et pour lesquels des algorithmes d'apprentissage sont en cours d'élaboration (Esposito et al. 2002, Denis et al. 2003). Ces automates et ces algorithmes sont de très bons candidats comme outils pour les objectifs du présent projet.

Bibliographie :
J.U. Bowie, R. L¨uthy & D. Eisenberg. (1991) A method to Identify Protein Sequences That Fold into a Known Three dimensional Struture. Science,.253, 1306-1310

L. Bréhélin (2001). Modèles de Markov cachés et apprentissage par fusions d'états : algorithmes, applications, utilisations pour le test de circuits intégrés. PhD thesis, Université Montpellier II, LIRMM.

F. Denis & Y. Esposito (2003), Residual languages and probabilistic automata, to appear in the proceedings of ICALP03.

R. Durbin, S. Eddy, A. Krogh & G. Mitchison (1998). Biological Sequence Analysis: Probabilistic models of proteins and nucleic acids. Cambridge University Press.

Y. Esposito, A. Lemay, F. Denis & P. Dupont (2002), Learning Probabilistic Residual Finite State Automata, ICGI'2002, LNAI 2484, 77-91, 2002. 

P. Fariselli, P. Riccobelli & R. Casadio .(1999) The role of evolutionary information in predicting the disulfide bonding state of cysteines in proteins. Proteins, 36 , 340-346

A. Fiser & I. Simon. (V) Predicting the oxidation state of cysteines by multiple sequence alignment. Bioinformatics, 16 , 251-256

P. Frasconi, A. Passerini & A. Vullo. (2002) A two-stage SVM architecture for predicting the disulfide bonding state of cysteines  Actes de NNSP'02

T.S. Furey, N. Cristianini, N. Duffy, D.W. Bednarski , M. Schummer and D. Haussler (2000). Support vector machine classification and validation of cancer tissue samples using microarray expression data. Bioinformatics, 16, 906-914.

C. Geourjon, & G. Deléage. (1995) SOPMA : significant improvements in protein secondary structure prediction by consensus prediction from multiple alignments. Comput Appl Biosci. 6, 681-684

Y. Guermeur (2002). Combining discriminant models with new multi-class SVMs. Pattern Analysis and Applications, 5, 168-179.

Y. Guermeur, A. Elisseeff & H. Paugam-Moisy (2000). A new multi-class SVM based on a uniform convergence result. IJCNN’00, IV, 183-188.

Y. Guermeur, C. Geourjon, P. Gallinari & G. Deléage (1999). Improved performance in protein secondary structure prediction by inhomogeneous score combination. Bioinformatics, 15, 413-421

L. Grate, R. Hughey, K. Karpus et K. Sj¨olander. Tutorial - Stochastic Modeling Techniques: Understanding and using hidden Markov models. Available at http://www.cse.ucsc.edu/research/compbio/ 

D. Haussler (1999). Convolution Kernels on Discrete Structures. Rapport de recherche UCSD-CRL-99-10.

T.S. Jaakola & D. Haussler (1998). Exploiting generative models in discriminative classifiers. Actes de NIPS’11.

T. Jaakola and M. Diekhans and D. Haussler (1999). Using the Fisher kernel method to detect remote protein homologies. ISMB’99, 149-158.

DT Jones. (1999) GenTHREADER: an efficient and reliable protein fold recognition method for genomic sequences. J Mol Biol, 287, 797-815.

R.D. King & M.J. Sternberg. (1996) Identification and application of the concepts important for accurate and reliable protein secondary structure prediction. Protein Sci. 5, 2298-2310

A. Kloczkowski, KL Ting, RL Jernigan & J Garnier. (2002) Combining the GOR V algorithm with evolutionary information for protein secondary structure prediction from amino acid sequence.
Proteins. 49, 154-66

RH Lathrop & Smith. (1996) Global optimum protein threading with gapped alignment and empirical pair score functions.  J Mol Biol, 255, 641-65.

A. Krogh & S.K. Riis. (2000) Hidden Neural Networks.To appear in Neural Computation

A. Marin, J. Pothier, K. Zimmermann & JF Gibrat.( 2002) FROST: a filter-based fold recognition method. Proteins. 49, 493-509

G. Pollastri, D. Przybylski, B. Rost & P. Baldi. (2002) Improving the prediction of protein secondary structure in three and eight classes using recurrent neural networks and profiles. Proteins, 47, 228-235

B. Rost et S. O’Donoghue. (1997) Sisyphus and protein structure prediction. Bioinformatics,.13, 345-356

B. Rost & C. Sander. (1993) Prediction of protein secondary structure at better than 70% accuracy  J Mol Biol. 232, 584-599

KT Simons, C Kooperberg, E Huang & D. Baker. (1997) Assembly of protein tertiary structures from fragments with similar local sequences using simulated annealing and Bayesian scoring functions. J Mol Biol, 268, 209-25.

V.N. Vapnik. (1982) Estimation of Dependences Based on Empirical Data. Springer-Verlag, N.Y.

J.-P. Vert (2002). A tree kernel to analyze phylogenetic profiles. ISMB’02, S276-S284.

C. Watkins (1999) Dynamic Alignment Kernels. Rapport de recherche CSD-TR-98-11.

B3 – Résultats attendus : 
On détaillera l’échéancier des résultats et réalisations intermédiaires et finaux attendus. On précisera les risques scientifiques qui seront pris. On discutera de l’impact potentiel de ce projet sur les scènes européenne et internationale.

Les retombées attendues sont importantes, aussi bien en biologie qu’en apprentissage automatique. Des méthodes fines de prédiction de la structure tertiaire des protéines peuvent permettre une meilleure connaissance «mécanistique» des protéines et ceci intéresse l’ensemble de la communauté biologique aussi bien académique qu’industrielle (en particulier l’industrie pharmaceutique). En effet, aujourd’hui l’objectif est d’analyser au niveau moléculaire les phénomènes biologiques. Dans ce contexte la connaissance de la structure tertiaire des protéines, même sous une forme prédite, joue un rôle capital. En pratique, ces travaux peuvent permettre la mise au point de molécules thérapeutiques.

En apprentissage automatique, ce projet donnera l'occasion de confronter des méthodes algorithmiques et des savoirs-faire sur un problème particulièrement difficile. On en attend une meilleure compréhension des techniques à mettre en oeuvre pour traiter des données séquentielles contenant des informations corrélées et distantes, la conception de nouveaux algorithmes  adaptés aux données séquentielles (ou l'adaptation d'algorithmes essentiellement développés dans d'autres contextes, comme les SVM), des exemples de combinaison d'algorithmes conduisant à des améliorations des performances. Le développement intégré de systèmes hybrides, incorporant des approches aussi diverses, et appliqués à un problème de cette taille, est un défi qui n’a pas encore été relevé.

La bioinformatique est un domaine dans lequel de nombreux problèmes restent ouverts. La prédiction de la structure tertiaire des protéines en est un exemple. Les interactions entre informaticiens, statisticiens, bioinformaticiens et biologistes sont indispensables. Un de nos objectifs est qu’au delà de ce projet pluridisciplinaire des collaborations durables s’installent entre ces communautés.

B4 – Summary (in English) : (1 to 2 pages)
Le Conseil Scientifique pourra solliciter des experts non francophones auxquels sera envoyé l’ensemble des documents. Le présent résumé, entièrement rédigé en anglais, visera à fournir une présentation synthétique de l’ensemble du projet.

The functional exploitation of the data provided by the large programs of genome sequencing requires the knowledge of the tridimensional structure of proteins. However, deriving the 3D structure of proteins experimentally is a tough task, which can prove unfeasible. The massive arrival of data generated by the large scale sequencing programs requires to switch from a biochemical approach to a bioinformatic approach. This provides us with an excellent opportunity to develop new methods devoted to prediction on sequences.

The goal of this project is thus, in the context of protein tertiary structure prediction, to highlight hard generic problems and to propose methods improving over state-of-the-art ones in the field. To that end, we use approaches from machine learning, both numerical and symbolic. Our strategy is of the “devide-and-conquer”, with the ultimate goal to integrate the different prediction levels in a single model. Indeed, it is possible to tackle the task in a progressive way throughout connex problems such as protein secondary structure prediction, the prediction of disulphide and salt bridges. We will thus carry on with researchs we have already performed, or we are currently initiating in the framework of the working group “Learning and sequences” of the AS “Learning and bioinformatics”. Currently, no prediction method implements such kind of modular and hierarchical approach, integrating so different systems. The main originality of our work will consist in integrating solutions appropriate for the subproblems so as to achieve the ultimate goal, which appears highly characteristic of the complex analytical problems met on large sets of data.

The fields of machine learning we will focus on are statistical learning, throughout the design and implementation of kernel machines and recurrent neural networks, as well as the theory of automata, and more specifically the inference of machines of probabilistic recognition (probabilistic automata, HMMs, etc.). Their combined implementation should specifically make it possible to take into account the long-term dependences, still badly exploited by the classical prediction methods.

The expected fallouts are significant, since precise methods of tertiary structure prediction should provide an improved “mechanistic” knowledge of the proteins. This should thus be of interest for the biological community at large, the academic as the industrial one (and specifically the pharmaceutical industry). As for computer science, it is obvious that the methods developed should give birth to tools vastly useful for domains of intensive sequence processing such as the processing of texts in natural language. Machine learning has always taken benefits from the systematic and deep study of specific applications (one of the most recent examples is the one of zip codes,  which led to the emergence of kernel machines).

C – Moyens financiers et humains demandés par chaque équipe

Comme indiqué dans les tableaux ci-dessous, on distinguera
- les financements via le Fonds National pour la Science qui peuvent inclure
* du fonctionnement 
* de l’équipement
* des mois de personnel temporaire (CDD) pour un montant ne pouvant excéder 50% du financement total attribué. La durée du ou des contrat(s) prévus, qui ne peuvent excéder 24 mois chacun, sera précisée.
	- les moyens demandés aux organismes de recherche qui peuvent inclure
* des postes de post-doc 
* des demandes de délégation ou détachement pour des enseignants-chercheurs
* des accueils de chercheurs étrangers
- les demandes d’allocations de recherche

Les diverses possibilités concernant l’attribution de moyens pour recruter ou accueillir des personnels seront globalement très limitées pour l’ensemble des ACI. Leurs demandes devront donc être particulièrement justifiées. Si les bénéficiaires de ces demandes sont connus ou pressentis, les CV correspondants  seront  joints à la présente demande.

Dans le cas des moyens alloués par les organismes, il n’est pas nécessaire de préciser à quel organisme (CNRS ou INRIA) ces moyens seront demandés, sauf cas particulier à expliciter. Ces moyens seront en effet répartis globalement au niveau de l’ACI, en tenant compte bien sûr des règles et contraintes propres à chaque organisme.

On présentera une justification scientifique des moyens demandés pour chacune des équipes impliquées dans le projet.

C1 - Demandes effectuées dans le cadre de l’ACI pour le présent projet :

Nom de l’équipe ou du laboratoire : MODBIO-LORIA

Moyens demandés dans le cadre de la présente ACI (en K€ TTC) :

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement	 5		 	 5	
Fonctionnement (dont CDD décrits ci-dessous)	 10	 10	 10	 30	
Total / année	 15	10	10	35	

Dépenses de personnels (CDD) :
Nature de l’emploi (post-doc, ingénieur, assistant-ingénieur,…)		
Durée de l’emploi (en mois)		
Coût total de l’emploi		

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 
	 	 	 	
Nombre d’accueils en délégations ou détachements	1 (Y. Guermeur)				

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 1	 	 	 	

Justifications scientifiques de l’ensemble des demandes :
L’équipe MODBIO travaille depuis plusieurs années sur la conception et la mise en œuvre de machines à noyaux. Sa principale contribution dans le domaine concerne les SVM multi-classes. Dans le cadre de ce projet, nous souhaitons développer des machines aux performances accrues, dont les noyaux soient dédiés aux différentes tâches de traitement de séquences étudiées. Ceci suppose de concentrer des efforts importants sur deux axes centraux. Le premier est la résolution efficace des problèmes de programmation mathématique auxquels se réduit l’apprentissage. Cette question, déjà largement étudiée dans le cas de la discrimination bi-classe, demeure entièrement ouverte dans le cas de la discrimination multi-classe. Le second est la conception et la programmation des noyaux. Ici, la principale difficulté réside dans l’obtention d’un compromis entre qualité de la modélisation et temps de calculs. Nous souhaitons recruter un doctorant dont le sujet de thèse porte sur ces aspects. Les financements d’équipement et de fonctionnement demandés doivent principalement lui fournir les moyens de son travail, notamment l’achat de licences de logiciels d’optimisation.

C2 - Autres soutiens financiers apportés au projet :
On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

Le LORIA participe au Génopole Strasbourg-Alsace-Lorraine et au PRST Intelligence Ligicielle, dans le cadre du CPER Lorraine. L’équipe MODBIO participe aux AS CNRS « Apprentissage et Bioinformatique » et « Machines à vecteurs support et méthodes à noyau ».

C1 - Demandes effectuées dans le cadre de l’ACI pour le présent projet :

Nom de l’équipe ou du laboratoire : Bioinformatique et RMN structurales (IBCP)

Moyens demandés dans le cadre de la présente ACI (en K€ TTC) : 100 K€

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement	10			10	
Fonctionnement (dont CDD décrits ci-dessous)	50	30	5	85	
Total / année	60	30	5	95	

Dépenses de personnels (CDD) :
Nature de l’emploi (post-doc, ingénieur, assistant-ingénieur,…)	 1 post-doc	
Durée de l’emploi (en mois)	 18 mois	
Coût total de l’emploi	 60 K€	

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils en délégations ou détachements					

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 	 	 	 	

Justifications scientifiques de l’ensemble des demandes :

Le laboratoire de « Bioinformatique et RMN structurales » possède une expertise forte dans le domaine de la structure des protéines (y compris au niveau détermination expérimentale par RMN), dans le domaine de la bioinformatique structurale des protéines. Il est par ailleurs impliqués dans les projets de grilles de calcul pour la biologie. A ce jour il ne possède pas de compétence forte au niveau des problèmes d’apprentissage. Aussi pour la réussite de ce projet et afin que les collaborations avec les laboratoires d’informatiques soient optimal nous souhaitons recruter un post-doc sur ce projet. Le rôle de ce post-doc est important car il sera véritablement à l’interface avec les autres partenaires.
Grâce aux contacts de Yann Guermeur nous sommes en relation avec Gianluca Pollastri actuellement en post-doc aux USA, dans le laboratoire de Pierre Baldi (Irvine, Californie). Les travaux de ce laboratoire portent sur la prédiction de la structure des protéines. Le CV de Gianluca Pollastri est joint à ce dossier.

C2 - Autres soutiens financiers apportés au projet :
On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

Le laboratoire est impliqué dans différents projets (ACI-GRID, Projets Européens DataGRID et HCV, Projet Genoplante, Genopole Rhône-Alpes) qui lui permettent d’avoir en interne des ressources informatiques significatives (en particulier ferme de PC sous Linux) qui pourront être utilisées dans le cadre ce projet. 

C1 - Demandes effectuées dans le cadre de l’ACI pour le présent projet :

Nom de l’équipe ou du laboratoire : Laboratoire d'Informatique Fondamentale de Marseille (LIF), équipe BDA.

Moyens demandés dans le cadre de la présente ACI (en K€ TTC) : 35 K€

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement	5	5	5	15	
Fonctionnement (dont CDD décrits ci-dessous)	10	5	5	20	
Total / année	15	10	10	35	

Dépenses de personnels (CDD) :
Nature de l’emploi (post-doc, ingénieur, assistant-ingénieur,…)		
Durée de l’emploi (en mois)	 	
Coût total de l’emploi	 	

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils en délégations ou détachements					

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 	 	 	 	

Justifications scientifiques de l’ensemble des demandes :
François Denis et Yann Esposito travaillent à l'élaboration, au développement, à l'expérimentation et à l'application d'algorithmes d'inférence grammaticale. Ces algorithmes sont des gros consommateurs de ressources et il est indispensable qu'ils puissent être testés sur des machines possédant de fortes capacités de mémoire et de calcul.

C2 - Autres soutiens financiers apportés au projet :
On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

Le laboratoire est impliqué dans divers projets européens et propose d'autres projets d'ACI dans le cadre de l'appel d'offre « Masses de données ». On peut envisager que certaines ressources informatiques puissent être mises en commun. 

C1 - Demandes effectuées dans le cadre de l’ACI pour le présent projet :

Nom de l’équipe ou du laboratoire : IRISA /INRIA Rennes, Projet Symbiose.

Moyens demandés dans le cadre de la présente ACI (en K€ TTC) : 35 K€

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement	 5		 	  5	
 Fonctionnement (dont CDD décrits ci-dessous)	 10	 10	 10	 30	
 Total / année	 15	10	10	35	

Dépenses de personnels (CDD) :
Nature de l’emploi (post-doc, ingénieur, assistant-ingénieur,…)	 	
Durée de l’emploi (en mois)		
Coût total de l’emploi		

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois)		 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 1 (N. Yanev, 3 mois)	 	 	 	
Nombre d’accueils en délégations ou détachements					

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 1	 	 	 	

Justifications scientifiques de l’ensemble des demandes :
L’équipe a acquis une expertise solide en apprentissage d'automates déterministes et non déterministes, et poursuit des travaux sur ce thème en attaquant les problèmes originaux soulevés par les séquences biologiques ( prise en compte d’un alphabet structuré, apprentissage de grammaires algébriques, prédiction d’interactions longue distance). Cependant, nous nous sommes uniquement concentrés sur le problème de l’apprentissage de la structure de l’automate, et pas de la distribution de probabilités associée, qui seule permettra d’obtenir la robustesse des prédictions. Pour développer cet aspect de l'apprentissage d'automates probabilistes, nous envisageons le recrutement d'un doctorant chargé d'étudier plus particulièrement le calcul  a posteriori des probabilités associés aux états et aux transitions puis de développer un  paramètrage associé aux états et aux transitions a priori, ainsi que l'utilisation de cette nouvelle information au cours de l'apprentissage pour guider le choix de la structure..

C2 - Autres soutiens financiers apportés au projet :
On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

C1 - Demandes effectuées dans le cadre de l’ACI pour le présent projet :

Nom de l’équipe ou du laboratoire : MAB- LIRMM.

Moyens demandés dans le cadre de la présente ACI (en K€ TTC) : 27 K€

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement	3	3	3	9	
 Fonctionnement (dont CDD décrits ci-dessous)	6	6	6	18	
 Total / année	9	9	9	27	

Dépenses de personnels (CDD) :
Nature de l’emploi (post-doc, ingénieur, assistant-ingénieur,…)	 	
Durée de l’emploi (en mois)		
Coût total de l’emploi		

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois)		 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils en délégations ou détachements					

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 	 	 	 	

Justifications scientifiques de l’ensemble des demandes :
9 K€ seront employés pour l'achat du matériel informatique  indispensable au traitement des importantes séquences biologiques qui intéressent le projet. Les 18 K€ de fonctionnement seront essentiellement employés pour la prise en charge des missions.

C2 - Autres soutiens financiers apportés au projet :
On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

C1 - Demandes effectuées dans le cadre de l’ACI pour le présent projet :

Nom de l’équipe ou du laboratoire : Mathématique Informatique et Génome, INRA.

Moyens demandés dans le cadre de la présente ACI (en K€ TTC) : 80 K€

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement			 		
 Fonctionnement (dont CDD décrits ci-dessous)		20	40	60	
 Total / année		20	40	60	

Dépenses de personnels (CDD) :
Nature de l’emploi (post-doc, ingénieur, assistant-ingénieur,…)	 1 post-doc	
Durée de l’emploi (en mois)	18 mois	
Coût total de l’emploi	60 K€	

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois)		 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 	 	 	 	
Nombre d’accueils en délégations ou détachements					

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 	 	 	 	

Justifications scientifiques de l’ensemble des demandes :
Notre demande de personnel concerne un ingénieur d'étude spécialisé dans les développements logiciels. Les algorithmes développés par les chercheurs doivent être mis à la disposition des biologistes pour être vraiment utiles. Dans notre unité, les logiciels sont intégrés dans une suite de programmes permettant l'annotation semi-automatique des données génomiques. Cela demande donc un effort soutenu de développement et de maintenance logicielle. Cet ingénieur ne sera recruté que la seconde année après que les premiers développements aient été testés et validés par les scientifiques. 

C2 - Autres soutiens financiers apportés au projet :
On mentionnera les autres actions relatives au projet dans lesquelles l’équipe ou le laboratoire est engagé (projets européens, RNRT, RNTL, autres ACI, …).

L’équipe est impliquée dans plusieurs contrats : un contrat RNTL (Extraplodocs), deux contrats européens (Bacell Network, Express Fingerprints) ainsi que dans divers contrats IMPG.

D - Récapitulatif global des demandes du projet :

Financements via le Fonds National de la Science :

	2003	2004	2005	Total 	
Equipement	28	8	8	44	
Fonctionnement (dont CDD décrits ci-dessous)	86	81	76	243	
Total / année	114	89	84	287	

Dépenses de personnels (CDD) :
Nombre d’emplois	2	
Durée cumulative des emplois (en mois)	36	
Coût total des emplois	120	

Financements via les organismes de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre de post-docs (préciser pour chaque demande la durée en mois) 		 	 	 	
Nombre d’accueils de chercheurs étrangers (préciser pour chaque demande la durée en mois)	 1 (3 mois)	 	 	 	
Nombre d’accueils en délégations ou détachements	1 (Y. Guermeur)				

Allocations de recherche :

	2003-2004	2004-2005	2005-2006	Total 	
Nombre d’allocations de recherche débutant en :	 2	 	 	 	

E - Engagement du coordinateur du projet :

La présente page ne sera remplie que dans la version sous forme papier.

Je soussigné, Yann Guermeur, coordinateur du projet GENOTO3D, m’engage dans l’hypothèse où le présent projet serait retenu à :
- fournir un rapport d’évaluation à mi-parcours permettant au Conseil Scientifique d’apprécier l’avancement des travaux et la coopération des équipes participantes. 
- un rapport à la fin de l’exécution du projet.
- maintenir régulièrement une page web résumant l’ensemble des activités du projet. 

Signature du coordinateur du projet :		

Visa du Directeur du Laboratoire ou de l’Unité de Recherche auquel appartient le coordinateur du projet: