Les deux premières collaborations relatives à ce premier axe de recherche sont de nature plus biologique (modèles et applications) alors que les trois dernières concernent des travaux initialement d'algorithmique « pure » (les applications éventuelles devant venir dans un deuxième temps uniquement). Le dernier, bien que ne traitant pas exactement de l'extraction de motifs au sens usuel, fait référence à un problème qui est lié à la présence de répétitions dans une séquence et dont la résolution pourra éventuellement aider à faire face à certaines difficultés plus propres à l'inférence de motifs.
Identification des sites impliqués dans la promotion de la transcription et de la traduction chez les procaryotes : Une collaboration est en cours depuis Août 1997 avec A. Vanet actuellement à l'Institut de Biologie Physico-Chimique de Paris et A. Labigne de l'Institut Pasteur en ce qui concerne l'identification de certains sites liés à la promotion de la transcription chez Helicobacter pylori [26]. Elle doit se poursuivre par la recherche d'autres sites chez Helicobacter pylori ainsi que celle de ces sites chez d'autres bactéries, en particulier Escherichia coli et Bacillus subtilis.
Prédiction de gènes chez les eucaryotes : Il demeure de nombreux problèmes à résoudre dans le domaine de la prédiction de gènes qui, d'une certaine façon, peuvent fortement dépendre d'une bonne compréhension et résolution du problème de la reconnaissance de signaux. Deux collaborations abordent ce sujet.
Extraction de motifs simples et structurés dans plusieurs séquences : Les collaborations précédentes doivent également conduire, soit à étendre des approches déjà bien formalisées [15] [18] [23] de manière à les rendre encore plus souples et efficaces, soit à développer de nouveaux modèles mathématiques mieux adaptés aux connaissances même incomplètes que l'on possède à l'heure actuelle des processus biologiques tels la transcription et l'épissage. Ce travail doit se poursuivre, entre autres, dans le cadre d'un projet CAPES/COFECUB entre la France (Institut Gaspard Monge de l'Université de Marne-la-Vallée et Laboratoire d'Informatique de l'Université de Rouen, 12 personnes) et le Brésil (Instituto de Matemática e Estatística de l'Université de São Paulo et Instituto de Computação de l'Université de Campinas, 10 personnes). Ce projet a été déposé à la fin Juillet 1998, la réponse concernant son acceptation ou non doit être donnée en Décembre 1998. Les coordonnateurs du côté français en sont Maxime Crochemore (de l'Institut Gaspard Monge) et moi-même. E. W. Myers (de l'Université de Tucson en Arizona, États-Unis) est également un collaborateur de ce projet du côté français.
Recherche de satellites et de répétitions dispersées dans les génomes : Ce travail continue une collaboration avec E. W. Myers [16] [17]. Il a pour but la résolution de problèmes que nous ne pouvons pas traiter à l'heure actuelle avec l'algorithme déjà développé : identification de répétitions longues (les SINES, « Short Interspersed Nuclear Sequences », comme, par exemple, les séquences alu dont chaque unité répétée fait environ 300 paires de bases) ou très longues (les LINES, « Long Interspersed Nuclear Sequences »), identification d'objets résultant de réarrangements dans le génome (inversions, duplications, éléments transposés).
Le problème des répétitions dans un programme d'assemblage : Ce travail doit être réalisé en collaboration avec E. W. Myers. Il a débuté en Février/Mars 1998 lors d'un séjour que j'ai effectué à l'Université de Tucson en Arizona suite à une invitation de sa part. Il vise à trouver un moyen sensible et efficace de traiter le problème que posent les répétitions lors de l'assemblage d'une séquence. Ce problème est lié à celui du partitionnement d'un ensemble d'objets de types différents. Dans le cas de l'assemblage, les objets sont des fragments d'une même répétition initiale mais provenant de localisations diverses dans la séquence à assembler. Dans le cas de l'inférence de motifs par contre, les objets sont des séquences d'un ensemble possédant des familles de motifs divers, certaines séquences pouvant ne comporter aucun motif.