Serge DULUCQ
Serge Dulucq Professeur (Université Bordeaux 1)

Équipe LaBRI : Modèles et Algorithmes pour la Bioinformatique et la Visualisation
Fonction administrative : Vice-Président délégué au patrimoine de l'Université de Bordeaux
Courrier électronique : serge.dulucqarobaselabri.fr
Bureau : 372
Tél : +33 (0)5 40 00 60 81


Recherche

J'exerce actuellement mes activités de recherche au LaBRI au sein de l'Équipe "Modèles et algorithmes pour la bioinformatique et la visualisation " que j'ai contribué à créer en 2006, en collaboration avec D. Sherman et M. Delest. Auparavant, mes recherches se faisaient dans l'équipe "Combinatoire et Algorithmique".

Au cours de cette période de référence (2005-ce jour), mes recherches se sont orientées dans plusieurs directions : l'informatique théorique (combinatoire et algorithmique des mots, analyse d'algorithmes, codage par des mots et énumération), la combinatoire du groupe symétrique (théorie des représentations, combinatoire des tableaux et des permutations), la bioinformatique (algorithmique des séquences et des structures).

Au travers de mes activités, j'ai essayé d'avoir autant que possible un rôle d'animateur en encadrant des doctorants et les jeunes Maîtres de Conférences, en dispensant des enseignements au niveau DEA puis Master2 (cours "Combinatoire et Algorithmique" du tronc commun du DEA d'Informatique, puis module "Algorithmique pour la bioinformatique" dans le Master2 "Modèles et Algorithmes"), en obtenant et gérant plusieurs contrats (ACI, ANR, CNRS, Région), tout en ayant un certain nombre de responsabilités scientifiques au sein du LaBRI et au niveau national : Directeur du LaBRI (2003-2006), Chargé de Mission pour l'Informatique au département ST2I du CNRS (2006-ce jour).

Cette dernière mission, ajoutée à la direction de l'IUT Bordeaux 1 que j'ai prise en décembre 2007, ont considérablement réduit mes disponibilités actuelles pour le laboratoire et pour l'animation de mon équipe de recherche.

\item Description des activités de recherche
\item Combinatoire et Algorithmique

Depuis 2002, mes activités de recherche en Combinatoire et Algorithmique ont été moins importantes que par le passé, car j'ai souhaité donner une nouvelle orientation à mes recherches pour aborder des problèmes de nature algorithmique issus de la biologie. Ceci a conduit à la création de l'équipe "Modèles et algorithmes pour la bioinformatique et la visualisation " au début du quadriennal en cours (janvier 2007).

J'ai toutefois poursuivi des travaux que j'avais entamés sur la combinatoire des mots, l'algorithmique et l'analyse d'algorithmes, la combinatoire du groupe symétrique et les permutations à motifs exclus. Dans ce cadre, je maintiens une collaboration étroite avec le LaCIM de l'Université du Québec à Montréal (Srecko Brlek), laboratoire dans lequel je me suis rendu à plusieurs reprises pour des missions de travail de 15 jours à 1 mois.

\item Algorithmes et Méthodes pour la Bioinformatique

Les recherches que je mène au sein de notre groupe portent sur le traitement algorithmique des séquences et des structures macromoléculaires.

Concernant les séquences, nous travaillons sur des problèmes visant à rechercher des motifs (simples ou structurés), des régularités, des répétitions exactes ou approchées (en tandem ou dispersées), dans une séquence ou un ensemble de séquences. Nous abordons également des questions touchant à la statistique de motifs (afin de mettre en évidence des motifs sur ou sous représentés dans une séquence) pour mesurer la signification de la fréquence d'apparition de certains motifs dans les séquences. Cette approche, qui a pour objectif la recherche de zones informatives dans les génomes (gènes, sites de régulation, ...), repose sur des méthodes permettant d'obtenir dans certains cas des formules exactes pour la fréquence attendue des motifs recherchés.

Ces thèmes de recherche, sur lesquels travaillent plusieurs équipes, notamment au sein de la communauté bioinformatique en France, sont d'une grande importance pour les biologistes (mise en évidence de structures biologiques pertinentes, étude de la régulation de l'expression et de la fonction des gènes, détermination de la structure des génomes, dynamique et évolution des génomes, prédiction de structures, phylogénie, ...). Nous menons ces travaux en collaborant notamment avec Mireille Régnier (INRIA Rocquencourt) et Alain Denise (LRI, Orsay). Ils ont en particulier fait l'objet de la thèse de Mathias Vandenbogaert (soutenue fin 2004) que j'ai codirigée avec Mireille Régnier.

Concernant les structures, nos recherches ont un caractère plus novateur. Elles ont pour objectif le développement de nouvelles méthodes pour la modélisation et la comparaison de structures secondaires d'ARN (édition et alignement, approches globale et locale), et la mise en œuvre des outils logiciels correspondants. À l'heure actuelle, le biologiste ne dispose d'aucun outil de ce type, alors qu'il utilise fréquemment des logiciels comme Blast et Fasta dédiés à la comparaison de séquences. Pourtant, la comparaison de structures secondaires est toute aussi importante, en particulier afin de mieux comprendre les fonctions des molécules d'ARN ou des protéines, de prédire avec une meilleure efficacité le repliement dans l'espace d'une molécule, d'identifier les motifs structuraux conservés lors des processus de mutation, de rechercher des structures communes à un ensemble de structures macromoléculaires, ... Une partie de ces travaux est menée en collaboration avec Alain Denise (LRI, Orsay) et Hélène Touzet (LIFL, Lille).

Dans ce contexte, nous avons montré comment de telles structures peuvent être représentées sous forme arborescente, avec un degré de précision variable (suivant les traitements à réaliser ou les besoins du biologiste) pouvant aller jusqu'à un codage exact de la structure par un arbre. Nous nous intéressons au problème de l'édition d'arbres, le point de départ de ce travail reposant sur l'algorithme de K. Zhang et D. Shasha qui constitue à ce jour la référence en matière de comparaison (édition) d'arbres étiquetés ordonnés.

Dans un premier temps, nous avons réalisé une analyse exacte de cet algorithme. En définissant un paramètre sur les sommets des arbres, que nous appelons hauteur réduite, nous obtenons par une approche combinatoire des formules exactes pour les complexités en moyenne et au pire de cet algorithme.

D'autre part, nous avons apporté un certain nombre de modifications à cet algorithme afin d'y intégrer des contraintes de nature biologique prises en compte dans le cas de la comparaison de séquences. Ces modifications ont pour but de densifier les régions mises en correspondance par l'algorithme d'édition afin de pouvoir mieux l'utiliser pour la comparaison de structures secondaires. Pour atteindre cet objectif, nous cherchons à maximiser le nombre de sommets mis en correspondance dans les deux arbres, tout en faisant en sorte que les régions conservées soient les plus grandes possible. En effet, un biologiste préfèrera voir dans un alignement de structures secondaires un petit nombre de motifs structuraux d'une certaine taille plutôt qu'un plus grand nombre d'éléments de taille beaucoup plus petite et dispersés. Nous poursuivons actuellement la mise en œuvre de ces méthodes afin d'évaluer la pertinence biologique de nos approches. Ces travaux ont fait l'objet de la thèse préparée sous ma direction par Laurent Tichit, actuellement Maître de Conférences à l'Université de la Méditerranée, Aix-Marseille II.

Dans des travaux récents menés avec Hélène Touzet (LIFL, Lille), nous avons introduit un schéma général de définition des algorithmes de calcul de la distance d'édition entre arbres, et dans ce cadre, nous donnons une analyse exacte de leur complexité. Ce résultat nous a permis d'obtenir un nouvel algorithme de calcul de distance, en construisant par programmation dynamique la stratégie optimale.

Actuellement, nous travaillons sur de nouvelles opérations d'édition sur les arbres dans le but de comparer avec plus de pertinence biologique les structures d'ARN. Ces opérations étendent les opérations usuelles sur les séquences en permettant des insertions, suppressions ou substitutions de bases appariées, et des opérations permettant d'apparier deux bases (qui ne l'étaient pas auparavant), ou inversement la séparation d'un appariement en deux bases non appariées. Nous avons donné un premier algorithme utilisant ces nouvelles opérations pour aligner des structures secondaires d'ARN. Ce travail est au cœur de la thèse soutenue par Claire Herrbach en 2007, préparée sous ma direction et celle d'Alain Denise (LRI, Orsay). Claire Herrbach a poursuivi ce travail dans le cadre d'un post-doc financé par l'ANR (projet Brasero).

Je m'intéresse également à des problèmes touchant aux réarrangements génomiques, et à l'étude de l'évolution par analyse de l'ordre des gènes. Ces travaux ont fait l'objet de la thèse de Géraldine Jean soutenue en 2008, thèse que j'ai encadrée en collaboration avec Macha Nikolski.

Extrait de publications


Guillaume Blin, Alain Denise, Serge Dulucq, Claire Herrbach, Helene Touzet. Alignments of RNA structures.. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2010, 7 (2), pp.309-322.

Claire Herrbach, Alain Denise, Serge Dulucq. Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm. Theoretical Computer Science, Elsevier, 2010, 411, pp.2423-2432.

Pascal Ferraro, Aïda Ouangraoua, Laurent Tichit, Serge Dulucq. Local Similarity Between Quotiented Ordered Trees. Journal of Discrete Algorithms, Elsevier, 2007, 5 (1), pp.23-35.

David Auber, Maylis Delest, Serge Dulucq, Jean-Philippe Domenger. Efficient drawing and comparison of RNA secondary structure. Journal of Graph Algorithms and Applications (JGAA), Brown University, 2006, 10, pp.329-351.

Srecko Brlek, Serge Dulucq, Annie Ladouceur, Laurent Vuillon. Combinatorial properties of smooth infinite words. Theoretical Computer Science, Elsevier, 2006, 352 (1-3), pp.306-317.


Responsabilité pédagogique

\item Directeur de l'IUT Bordeaux 1 depuis décembre 2007 : 9 départements sur 2 sites (Gradignan, Agen), 17 Licences Professionnelles, 2000 étudiants en formation initiale ou continue, 180 enseignants et enseignants chercheurs, 100 personnels BIATOS permanents ou contractuels, 400 vacataires professionnels.

\item Membre élu au Conseil Scientifique de l'ENSEIRB depuis 2003.

\item Membre nommé au Conseil d'Administration de Bordeaux Unitec (incubateur et pépinière pour la création d'entreprises innovantes en région Aquitaine) depuis 2003.

\item Membre élu au Conseil d'Administration de l'IUT Bordeaux 1 (2005-2008).

\item Membre de la Commission de Spécialistes 27ème section commune à l'Université Bordeaux 1 et l'ENSEIRB (1988-2008). Membre de 3 Comités de Sélection en 2009.

\item Activités Pédagogiques : Enseignements divers en formation initiale au département informatique de l'IUT Bordeaux 1. Cours du tronc commun du DEA Informatique, puis en 2ème année du Master Informatique spécialité "Modèles et Algorithmes", et en 2ème année du Master de Bioinformatique.

Administration

\item Directeur du LaBRI du 1er janvier 2003 au 31 décembre 2006.

\item Chargé de mission pour l'Informatique au département ST2I du CNRS depuis mai 2006.

\item Président du Comité de Pilotage du programme "Domaines Émergents" (DEFIS) de l'ANR (l'un des 5 programmes thématiques STIC de l'ANR).

\item Expert auprès du MESR (DSPT9 puis DGRI) depuis 2003 : évaluation des Masters, des Écoles Doctorales, jurys PEDR (président du jury PEDR en 2005 et PES en 2009).


Page mise à jour le 13/08/2010 à 10:56