|
|
Rapport d'activités de l'équipe
|
| Abdeddaïm Saïd | Maître de Conférences | Université de Rouen | ||
| Andary Philippe | Maître de Conférences | Université de Rouen | ||
| Duval Jean-Pierre | Professeur | Université de Rouen | ||
| Groult Richard | Doctorant | Université de Rouen | ||
| Guaiana Giovanna | Maître de Conférences | Université de Rouen | ||
| Hancart Christophe | Maître de Conférences | Université de Rouen | ||
| Lecroq Thierry | Professeur | Université de Rouen | ||
| Lefebvre Arnaud | Doctorant | Université de Rouen | ||
| Léonard Martine | Maître de Conférences | Université de Rouen | ||
| Patrou Bruno | Maître de Conférences | Université de Rouen |
Les activités de l'équipe « Combinatoire et Génome » s'orientent vers l'élaboration d'une logistique théorique pour étudier la régularité des chaînes de caractères, et, en tout premier lieu, celles qui interviennent dans le génome. Il est clair que la conception d'une telle logistique s'appuie sur un outillage conceptuel de haut niveau, dont les thématiques dépassent, par leur généralité, une étude restreinte des chaînes proprement dites. Ceci nous a conduit à dégager les cinq thématiques suivantes : recherche de motifs dans un texte, comparaison des chaînes de caractères, détections de répétitions, problèmes de codage, monoïdes de traces.
Dans ce cadre, T. Lecroq a soutenu une habilitation à diriger des recherches de l'Université de Rouen le 8 décembre 2000 sur quelques aspect de l'algorithmique du texte [34]. R. Groult ainsi qu'A. Lefebvre et J. Pelfrenne (UMR 6037) préparent une thèse sous la direction de J.-P. Duval, encadrés par J. Alexabdre (UMR 6037, Université de Rouen), S. Abdeddaïm, T. Lecroq, M. Léonard et L. Mouchard (UMR 6037, Université de Rouen).
P. Andary a participé à la création d'un environnement de programmation permettant d'effectuer des calculs symboliques aussi bien sur les automates booléens que sur les automates à multiplicité. Il s'intéresse maintenant aux fondements de la technologie objet.
J.-P. Duval a établi un résultat sur la périodicité, réponse à une question formulée par M.-P. Schützenberger [2]. En collaboration avec L. Mouchard il a précisé les relations entre permutations de bords et périodicité ultime [1] et poursuivi en collaboration avec A. Restivo et F. Mignosi (Université de Palerme, Italie) les travaux sur les relations entre mots récurrents et mots périodiques en application du théorème du point critique [3]. .
En collaboration avec M. Crochemore (Université de Marne-la-vallée), C. Hancart a rédigé un chapitre du « Algorithms and theory of computation handbook », dévolu aux algorithmes standard de recherche de mots [36].
C. Hancart et T. Lecroq, en collaboration avec M. Crochemore, ont rédigé un livre présentant de nombreuses techniques de traitement du texte [37]. Il s'agit du premier ouvrage en français d'algorithmique spécialisé sur le traitement du texte. Il présente les bases techniques utilisées dans les domaines de la recherche documentaire, de l'indexation pour les moteurs de recherche et des logiciels systèmes. Les méthodes qui y sont décrites trouvent leurs applications dans les domaines du traitement de la langue naturelle, de l'analyse des séquences génétiques et des bases de données textuelles.
Les trois mêmes auteurs ont publié un article présentant les méthodes de recherche de mots « à la Boyer-Moore » [5].
T. Lecroq a effectué une série de tests d'algorithmes de recherche de mots sur des alphabets de grande taille, ou de taille bornée [6], qui pourront se révéler utiles dans la perspective du passage du codage des caractères sur 8 bits au codage sur 16 ou 32 bits (unicode standard).
Avec M. Crochemore, il a rédigé un chapitre concernant la compression de texte paru en 1998 dans un volume intitulé « Algorithms and theory of computation handbook » [38].
Avec des co-auteurs polonais de l'Université de Varsovie, les mêmes auteurs ont construit un algorithme efficace pour la recherche d'un ensemble fini de mots dans un texte [8].
En collaboration avec C. Charras (Université de Rouen), il a réalisé un outil java pour l'illustration des algorithmes de recherche exacte d'un mot [17,19].
Avec C. Charras et J. D. Pehoushek, il a trouvé un nouvel algorithme très rapide pour la recherche de mots longs exprimés sur de petits alphabets [18].
En collaboration avec R. Cole (New York University), M. Crochemore, C. S. Iliopoulos et Y. J. Pinzon (King's College London), L. Mouchard (UMR 6037, Université de Rouen), W. Plandowski et W. Rytter (Université de Varsovie), T. Lecroq s'est intéressé à la recherche de motifs dans des séquences musicales [21,10,25,22], notamment au cas de la recherche delta et gamma approchée et de ces relations avec la recherche avec joker.
Cette question est évidemment au centre du problème qui consiste à comparer des chaînes génomiques.
Dans le cadre des activités algorithmiques associées au traitement de séquences biologiques, S. Abdeddaïm a travaillé sur le problème de l'alignement multiple. Ce problème NP-complet a suscité de nombreux travaux, parmi lesquels les solutions les plus praticables sont des algorithmes gloutons. S. Abdeddaïm a établi un lien entre la classe des algorithmes d'alignement glouton et le problème du calcul incrémental de la fermeture transitive d'un graphe orienté. Il a proposé trois nouveaux algorithmes pour ce dernier problème [12]. Ces algorithmes utilisent un recouvrement par chemins du graphe pour accélérer le calcul de la fermeture transitive et réduire l'espace nécessaire pour la représenter. L'implantation d'un algorithme de ce type lui a permis d'accélérer le programme d'alignement multiple DIALIGN d'un facteur de 120 sur 200 séquences de longueur moyenne égale à 100 [13,15] (en collaboration avec B. Morgenstern, AVENTIS Pharma, Grande-Bretagne). DIALIGN a pu être ainsi utilisé pour des applications lourdes en temps de calcul comme la prédiction de gènes dans les génomes récemment séquencés [14]. En vue d'une application dans ce dernier domaine, et avec J. Pelfrenne, doctorant en bioinformatique de l'UMR 6037 (biologie végétale) de l'Université de Rouen, S. Abdeddaïm étudie actuellement le problème de la constuction d'index de motifs approchés.
S. Abdeddaïm et T. Lecroq [29] sont intervenus au cours de l'École thématique du CNRS « Traitement de l'information en génétique moléculaire » (Asnelles-sur-Mer, 23-27 novembre 1998).
Avec J.-F. Myoupo et D. Semé (Université d'Amiens), T. Lecroq a donné un nouveau résultat pour produire un alignement entre deux mots sur un réseau systolique [7].
En collaboration avec C. Charras, il a réalisé l'implantation d'outils d'analyse liés à l'altération des données (problème de distance et d'alignement) [39].
M. Léonard et R. Groult travaille en collaboration avec L. Mouchard sur la recherche de répétitions évolutives dans les séquences de grande taille. Les biologistes s'intéressent aux séquences dans lesquelles une suite de nucléotides (ou fragment) apparaît plusieurs fois. Ces fragments apparaissent à intervalles plus ou moins réguliers et sont tous semblables, ou tout au moins très proches dans le sens qu'ils sont de la même longueur et ne diffèrent entre eux que de quelques nucléotides.
Étant donné un mot w, une répétition avec évolution dans w est une suite de facteurs de w, ordonnée selon l'ordre d'apparition des facteurs dans w et dans laquelle chaque facteur diffère de ses voisins d'au plus k lettres. On considère uniquement des facteurs de même longueur l. Deux facteurs successifs peuvent être distants ou se chevaucher d'au plus j positions. Le problème consiste à détecter toutes les répétitions pour k, l et j donnés.
Ils proposent tout d'abord une solution utilisant le partitionnement de Crochemore mais cette première méthode est très coûteuse en temps et ne permet pas d'étudier des séquences de taille supérieure à 13000 paires de bases. Ils présentent ensuite une seconde méthode, plus rapide mais plus coûteuse en espace puis des améliorations permettant de réduire la complexité en espace.
Avec A. Lefebvre, doctorant en bioinformatique de l'UMR 6037 (biologie végétale) de l'Université de Rouen, T. Lecroq a utilisé la structure d'oracle des facteurs pour détecter efficacement des répétitions dans de très longues séquences [20]. Un logiciel nommée FORRepeats (Factor ORacle Repeats) est en cours de développement. Cette stratégie permet de développer une nouvelle méthode de compression séquentielle et sans perte [23,9]. Un logiciel, nommé compror est disponible à l'adresse suivante : http://al.jalix.org/. Cette nouvelle méthode permet également d'estimer la complexité des séquences [24].
Ces différentes applications ont fait l'objet d'un article avec J. Alexandre, chercheur CNRS de l'UMR 6037 [26].
B. Patrou a étudié en collaboration avec I. Litovsky (Université de Nice-Sophia Antipolis) des problèmes liés aux codes dans le cadre de la théorie des langages. Ces travaux gravitent autour de deux extensions de l'opération étoile de Kleene que sont l'opération zigzag et une opération de mots de pile. Par rapport à ces opérations, des notions de codicité et de stabilité ont été étudiées et plusieurs algorithmes de décision ont été proposés. La notion d'enveloppe libre, rattachée à l'opération étoile, a été étendue à l'opération zigzag faisant ainsi apparaître des problèmes nouveaux intrinsèquement liés à cette opération. Quelques-uns ont été résolus mais plusieurs questions restent ouvertes. Enfin, une approche globale de la question permet de regrouper les opérations étoile et zigzag sous une même opération dont certaines propriétés ont pu être mises en relief.
G. Guaiana a porté son activité de recherche sur les monoïdes de traces, qui constituent un modèle sémantique du parallélisme. En collaboration avec R. Meyer, A. Petit et P. Weil, G. Guaiana a généralisé le principe du produit en couronne aux langages de traces [4]. Ce résultat décrit les langages de traces reconnus par un produit en couronne S o T de deux monoïdes de transformation S et T, en terme de fonctions séquentielles et en terme des langages de traces reconnus par S et T. Le principe du produit en couronne a été établi sur les langages formels par Straubing à la fin des années 70 et il a eu de nombreuses applications dans différents domaines de l'informatique comme la logique et la vérification.
En collaboration avec A. Restivo et S. Salemi, G. Guaiana a trouvé une construction simple et explicite d'un automate reconnaissant le produit de n langages de traces reconnaissables [28]. Ce travail généralise un autre résultat des mêmes auteurs qui associait un treillis au produit de deux langages de traces. L'étude du produit de langages des traces a conduit les trois auteurs à investiguer sur les familles de langages reconnaissables qui sont fermées par commutations partielles. Ils ont alors établi des connections entre la théorie des traces et la théorie des variétés des langages formels, en montrant en particulier que le niveau 3/2 de la hiérarchie de Straubing-Thérien est fermé par commutations partielles [28].
La technologie objet est une approche de la conception et de la programmation qui s'est avérée tout à fait efficace pour maîtriser la complexité du logiciel de grande envergure. Mais pour que ce logiciel soit de qualité (correct, robuste, réutilisable, extensible, ...), il est nécessaire d'explorer et d'établir les fondements de la notion d'objet (Abadi, Cardelli, ...) ainsi que la méthodologie de conception associée (Meyer, ...).
P. Andary souhaite donc orienter sa recherche vers une approche fondamentale de la technologie objet, en étudiant certains sujets comme : Modularité, Systèmes de types, Programmation par contrats, Validation, ...
P. Andary a participé, en tant que coordinateur technique, à la réalisation du projet SEA avec P. Caron, G. Duchamp, M. Flouret (LIH) et É. Laugerotte. De la réflexion menée par ce groupe est né un environnement de programmation (SEA) permettant d'effectuer des calculs symboliques (sous Maple 5) aussi bien sur les automates booléens que sur les automates à multiplicité.
Ce travail s'est concrétisé dans un article présenté à WIA'99 (Potsdam) [16]
Dans le cadre de la recherche sur le génome, l'équipe « Combinatoire et Génome » agit comme composante d'ABISS (Atelier Biologie Informatique Statistique et Sociolinguistique). Ce plan pluri-formation s'appuie sur un partenariat très fructueux entre le CNRS, l'Université de Rouen et la Région Haute-Normandie. Cette coopération a en particulier permis d'organiser à Rouen des rencontres importantes dont :
Dans cet axe de recherche, grâce aux compétences de ses membres et à la nature de ses activités, l'équipe « Combinatoire et Génome » constitue le lieu privilégié où sont formalisées les problématiques, et où sont étudiés les concepts combinatoires ainsi élaborés.
L'axe Informatique et Génome est un sujet fédérateur. Il a fait l'objet d'une action CNRS, dans ce cadre notre laboratoire et ABISS étaient tous deux présents dans le « Réseau Informatique et Génomes ». Notre participation concernait plus particulièrement le point de vue algorithmique pour permettre de manière originale et performante, la détection de régularités dans les séquences nucléiques et protéiques.
Dans le cadre de l'action spécifique « Algorithmes pour la bioinformatique » (ALBIO) du département STIC du CNRS, S. Abdeddaïm s'est vu confier l'animation du thème « alignement » avec J.-S. Varré (LIFL).
T. Lecroq a déposé une demande de création d'un groupe de travail intitulé « Algorithmique des séquences » dans le cadre du renouvellement du GDR-ALP (« Algorithmique, Langage et Programmation »). Ce groupe de travail se propose d'étudier les aspects aussi bien théoriques et combinatoires des suites de symboles que les aspects pratiques en particulier les applications en biologie moléculaire. Il s'intéressera plus spécifiquement aux problèmes de recherche et d'extraction de motifs, d'indexation, de compression de données, de comparaison et d'alignement de séquences, de recherche dans des données compressées, de recherche de répétitions et d'analyse en moyenne des algorithmes, de statistiques et probabilités sur les séquences.
S. Abdeddaïm est membre nommé de la 64esection du CNU.
C. Hancart et T. Lecroq interviennent dans le DÉA IFA (Informatique Fondamentale et Applications) à l'Université de Marne-la-Vallée.
T. Lecroq est bénéficiaire de la Prime d'Encadrement Doctoral et de Recherche depuis octobre 2000.
Dans le cadre de l'Institut Franco-Russe A. M. Liapunov d'informatique et de mathématiques appliquées, conjoint à l'INRIA et à l'Université de Moscou, T. Lecroq s'est rendu à l'Université de Moscou en avril 1998 et au LORIA à Nancy en février 1999.
S. Abdeddaïm travaille à la fois avec des chercheurs de Lyon (sous la direction de M. Gouy) et de Cork en Irlande (sous la direction de D. Higgins).
J.-P. Duval a été membre du comité scientifique des conférences WORDS qui ont eu lieu en 1999 à Rouen et en 2001 à Palerme (Italie).
T. Lecroq est le coordinateur principal d'une bourse (« Collaborative Linkage Grant » PST.CLG.977017) de l'OTAN nommée « String Algorithmics » regroupant des équipes des Universités de Rouen, Marne-la-Vallée, McMaster (Canada), Haifa (Israel), Padoue (Italie) et du King's College London (Royaume-Uni).
T. Lecroq a ou va faire partie du comité de programme des organisations suivantes :
Il a été examinateur de la thèse de J. F. Reid, « String algorithms for decomposing partially occluded images », soutenue au King's College London le 7 septembre 2001. Il est rapporteur de la thèse de Z. Tronícek de l'Université Technique Tchèque à Prague, République Tchèque, intitulée « Searching subsequences » qui sera soutenue le 14 décembre 2001.
http://www-igm.univ-mlv.fr/~lecroq/seqcomp/, 1998. En
collaboration avec C. Charras.
This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.42)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 cg.tex
The translation was initiated by Thierry.Lecroq on 2001-11-16