Institut de Mathématiques de Luminy Laboratoire
d'Informatique de Marseille

Equipe Méthodes Mathématiques pour la Génomique

Thèmes : Info-Bio-Math, Algorithmique Combinatoire, Classification

 

Alain Guénoche

Directeur de recherche CNRS
 

Liste des publications
 

Domaine de Recherche
 
 

Depuis une vingtaine d'années mes travaux portent sur l'algorithmique combinatoire, c'est-à-dire la recherche de méthodes de calcul dans des structures finies, graphes, hypergraphes, treillis, mots. Après une période consacrée à l'Informatique en Sciences Humaines (Reconnaissance des formes, Sériation chronologique, Edition de textes hiéroglyphiques, Traitements documentaires et statistiques de corpus), à l'énumération d'Ensembles Combinatoires et au tirage aléatoire de configurations (Permutations et Partitions avec contraintes, Arbres couvrants, Mots), j'ai orienté mes recherches dans deux directions : l'Analyse Combinatoire des Données et la Bio-Informatique, domaine pluridisciplinaire, source de nombreux problèmes à l'intersection des Mathématiques discrètes, de l'Informatique et de la Biologie moléculaire.

 

La bio-informatique, et plus particulièrement l'analyse de séquences biologiques, est l'étude, aux plans mathématique et informatique, des problèmes que posent la connaissance des génomes et des séquences protéiques, de leurs interactions et de leur expression. Grâce à une large coopération internationale, on dispose de grandes banques de séquences qui sont codées comme des mots sur des alphabets finis, et de données associées (structure, expression). Si la question fondamentale au plan biologique est bien évidemment le décryptage des mécanismes de la vie, les questions qui me concernent sont plus locales et débouchent sur des recherches en Info-Bio-Math ; plus particulièrement en algorithmique, sur des espaces métriques discrets (graphes, arbres, partitions, mots) pour des problèmes comme le séquençage, la conception des puces à oligos, la comparaison des génomes complets ou la prédiction fonctionnelle des protéines.

 

Mes trois sujets principaux actuels sont :

-       L’étude des réseaux d’interactions protéine-protéine dans une visée de prédiction fonctionnelle ;

-       Le partitionnement de graphes et les méthodes combinatoires en classification, avec application aux réseaux ci-dessus ;

-       La méthodologie de la reconstruction phylogénétique, depuis l'approximation d'une dissimilarité par une distance (additive) d'arbre jusqu’à la comparaison des X-arbres, suivant des critères topologiques.

 

Travaux récents

 

(I) L’étude des réseaux d’interaction, et des questions méthodologiques afférentes, a commencé pour moi en 2002 grâce à une collaboration avec B. Jacq et une équipe de l’IBDM (Marseille). Elle était basée sur le principe que l’on peut prédire les fonctions des protéines en cherchant à établir des classes de forte densité dans un réseau, si ces classes ont une interprétation fonctionelle. Nous nous sommes donc attachés à partitionner ces réseaux en classes dense, et à rechercher des fonctions communes aux classes, à l’aide de Gene Ontology. Une première méthode basée sur une distance de graphe, PRODISTIN, a été développée, puis une seconde basée sur la classification par densité. Le travail continue toujours en collaboration avec l’équipe de C. Brun (TAGC, Marseille), avec d’autres problématiques (protéines multifonctionnelles) et des méthodes de partitionnement en classes chevauchantes. Voici les principales publications auxquelles j’ai participé.

 

C. Brun, F. Chevenet, D. Martin, J. Wojcik, A. Guénoche, B. Jacq.- Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network, Genome Biology, 2003, http://genomebiology.com/2003/5/1/R6.

C. Brun, C. Herrmann, A. Guénoche.- Clustering proteins from interaction networks for the prediction of cellular functions, BMC Bioinformatics, 2004, 5:95.

A. Baudot, O. Martin, P. Mouren, F. Chevenet, A. Guénoche, B. Jacq, C. Brun.-  PRODISTIN Web Site: a tool for the functional classification of proteins from interaction networks, BioInformatics, 2006, 22 (2), 248-250.

J.B. Angelelli, A. Baudot, C. Brun, A. Guénoche.- Two local dissimilarity measures for weighted graph with application to biological networks, Advances in Data Analysis and Classification, 2008, 2, pp 3-16.

A. Baudot, J.B. Angelelli, A. Guénoche, B. Jacq, C. Brun.- Defining a Modular Signalling Network from the Fly Interactome, BMC Systems Biology 2008, 2:45, 17 p.

 

(II) Pour ce qui est du partitionnement de graphes et des méthodes combinatoires en Classification :

 

En collaboration avec une équipe de l'ENST (I. Charon, L. Denoeud, O. Hudry) nous avons étudié une distance d'édition entre partitions sur un même ensemble, la distance des transferts. Il s'agit du nombre minimum de transferts, d'un élément d'une classe dans une autre, éventuellement vide, pour passer d'une partition à une autre. Nous avons indiqué comment calculer cette distance, et établi des formules analytiques pour la distance maximum à une partition fixée, sur l'ensemble de toutes les partitions à n éléments ou celles ayant des cardinaux des classes identiques. Nous avons également étudié la distribution de cette distance sur l'ensemble des partitions et l'avons comparée aux autres indices de distance entre partitions.

 

I. Charon, L. Denoeud, A. Guénoche, O. Hudry.- Maximum transfer distance between partitions, Journal of Classification, 23, 1, 2006, 103-121.

L. Denoeud, A. Guénoche.- Comparison of distance indices between partitions, Proceedings of IFCS'2006, Data Science and Classification, V. Batagelj et al. (Eds.), Springer, 2006, 21-28.

 

Enfin j’ai entrepris depuis 2003 une comparaison des algorithmes de partitionnement de graphes (découpage, optimisation de critères (inertie, modularité) et marche aléatoire)

 

            A. Guénoche.- Comparison of algorithms in graph partitioning, ALIO/EURO conference on Combinatorial Optimization, Paris, 2005 and RAIRO, 42 (2008) 469-484 . http://www.rairo-ro.org/10.1051/ro:2008029.

          A. Guénoche (2009) Distances pour le partitionnement de graphe, in Partitionnement de Graphe, C.D. Bichot & P. Siarry (Eds.), Hermes, to appear.

           J.B. Angelelli, A. Guénoche L. Reboul (2009) Détection de communautés, disjointes ou chevauchantes, dans les réseaux, in Partitionnement de Graphe, C.D. Bichot & P. Siarry (Eds.), Hermes, to appear.

 

(III) Pour ce qui relève de la reconstruction phylogénétique, le travail récent a débuté par la comparaison de l’ordre des MUMs, plus longs mots communs à deux génomes, et uniques (présents une seule fois dans chaque génome). Nous nous sommes restreints à ceux qui ont une longueur significative (c'est-à-dire supérieure au maximum prévisible dans des séquences aléatoires, longueur qui dépend du taux de G+C). Nous avons d’abord cherché de longs fragments conservés, c’est à dire dépourvus de grands réarrangements. Pour les déterminer, nous avons construit des plus longues chaînes communes (LCC) de MUMs (suites maximales d'éléments placés dans le même ordre) dans lesquels les écarts entre MUMs consécutifs sont bornés. Ce problème est polynomial, quel que soit le nombre de génomes comparés. De plus, l'algorithme étudié est extensible au cas des ordres circulaires et à plus de deux génomes.

 

F. Guyon, A. Guénoche.- Comparing bacterial genomes from linear orders of patterns, 2003, Discrete Applied Mathematics, 156, 8, 2008, 1251-1262.

 

Puis nous nous sommes attachés à montrer qu’une distance basée sur la somme des longueurs des MSM (plus longs mots communs de longueur significative) était bien une distance évolutive. En tous cas, elle donne de bien meilleurs résultats que toutes les autres distances sans alignement (fréquence des mots rapportées à un modèle, compression, etc) auxquelles nous l’avons comparée dans un processus de simulation précis, ainsi que pour la reconstruction de phyla bactériens (collaboration avec C. Brochier). Ceci nous a conduit à étudier plusieurs critères de comparaison des topologies de X-arbres, dont le fameux MAST (maximum agreement sub-tree) pour lequel nous avons proposé une heuristique très efficace applicable à un grand nombre d’arbres

 

F. Guyon, A. Guénoche.- An evolutionary distance based on maximal unique matches to compare complete genomes, ASMDA conference, Chania, Mai 2007, Communications in Statistics (ID414194), 2010.

F. Guyon, C. Brochier, A. Guénoche (2009) Comparing alignment free string distances for complete genome phylogeny, Advances in Data Analysis and Classification, 3, 2, 2009, 95-108.

A. Guénoche, H. Garreta, L. Tichit (2009) About the largest subtree common to several phylogenetic trees, Proceedings ASMDA’09, Jansen et al. (Eds.), pp 6 - 10.

 

Mon projet de recherche porte sur :

 

La congruence des arbres évolutifs (en collaboration avec P. Darlu). Les arbres de gènes ne racontent pas tous la même histoire évolutive. Ici, ce sont les différentes souches de bactéries pathogènes qui sont étudiées. Nous cherchons à comparer les arbres de gènes et surtout à déterminer des familles de gènes congruents.

P. Darlu, A. Guénoche (2009) The TreeOfTrees method to evaluate the congruence between gene trees, submitted

 

Le consensus de partitions. Il s’agit d’un « vieux » problème de construction d’une partition médiane pour un ensemble de partitions sur un même ensemble X.  Depuis longtemps, l’on sait qu’il peut être résolu par programmation en nombres entiers, mais du fait du nombre de contraintes (O(n^3)) il ne peut être abordé que pour les X de petite taille. Nous améliorons une heuristique basée sur le partitionnement d’un graphe et le transfert d’éléments, pour traiter le consensus de partitions à plusieurs milliers d’éléments.

A.    Guénoche (2010) Consensus de partitions : une approache constructive, ROADEF’2010.

 

Le Bootsrap Clustering qui consiste à générer, par re-échantillonage ou autre, plusieurs jeux de données à partir des données initiales ; on peut pondérer aléatoirement les variables d'un tableau de données, mettre des poids aléatoires sur les arêtes d'un graphe ou faire du tirage avec remise des arêtes. A chacun correspondra une partition, obtenue par une méthode quelconque, et leur consensus est supposé plus robuste que la partition d'un seul jeu. C’est donc un domaine d’application de la méthode de consensus.

 

 

Travaux plus anciens

 

DISTANCE PARTIELLE ET RECONSTRUCTION PHYLOGENETIQUE

 

En collaboration avec B. Leclerc (EHESS) nous avons étudié le problème de l'ajustement d'une distance par un arbre à partir de distances partielles, c'est à dire dans le cas où certaines valeurs sont inconnues - par exemple si les séquences ne se chevauchent pas. Pour les distances d'arbre sur n taxons, B. Leclerc a montré que 2n-3 valeurs étaient suffisantes à condition que ces paires constituent ce que l'on appelle, en Théorie des Graphes, un 2-arbre (ensemble de triangles deux à deux adjacents). J'ai montré que l'on pouvait se satisfaire d'une condition plus faible, et nous avons comparé les stratégies de choix de ces 2n-3 valeurs. Nous avons abouti à la "méthode des triangles", qui impose d'établir un ordre tel que, pour tout élément, il existe au moins deux autres éléments à distances connues placés avant lui, même s'ils ne sont pas adjacents. Toujours en collaboration avec B. Leclerc, nous avons étudié la possibilité de prolonger une distance partielle donnée en une distance d'arbre. En tant que problème de décision, il a été montré NP-complet. Mais suite à l'étude des méthodes de reconstruction à partir de distances partielles, il apparait que le problème peut être résolu en un temps polynomial pour de nombreuses instances. Les valeurs connues de distance permettent de définir un graphe support de cette distance partielle. Nous avons décrit des familles de graphes support pour lesquelles le problème est de complexité polynomiale et défini un algorithme qui permet de décider si un graphe (valué) donné peut être complété en une distance d'arbre.

 

A. Guénoche, B. Leclerc.- The triangles method to build X-trees from incomplete distance matrices. RAIRO Operations Research, 35, 2001, pp. 283-300. [ PDF ] 189 k

A. Guénoche, B. Leclerc, V. Makarenkov.- On the extension of a partial metric to a tree metric, 6th International Conference on Graph Theory 2000, J.L. Fouquet, I. Rusu (Eds.) Discrete Maths, 276/1-3, 2003, pp. 229-248[ [PDF ] 213 k

 

 

CONCEPTION DES PUCES A OLIGOS

 

Les oligonucléotides sont de courtes séquences - une vingtaine des bases - A, T, G ou C - fixées sur un support  de quelques cm2. Ces puces permettent de détecter, par hybridation, la présence de séquences complémentaires. Cette technique a révolutionné, l'analyse biologique et médicale – détection de mutations - aussi bien que le contrôle de l'environnement - recherche de virus ou de bactéries. C'est une technique qui s'avère essentielle pour l'étude du fonctionnement de la cellule, puisque ces puces permettent de quantifier l'expression des gènes, au fil des processus biologiques. Les problèmes que j'ai abordés sont de deux types :

(i)         La conception des puces : les puces à oligos de haute densité sont réalisées par une synthèse en parallèle des oligos sur leur support. La technique employée est celle des masques qui permet de positionner un des quatre nucléotides à l'extrémité des oligos qui doivent être ainsi prolongés. Cette technique est réalisée actuellement selon un protocole qui nécessite un nombre de masques égal à quatre fois la longueur des oligos à synthétiser. Considérant que la séquence des masques est une surséquence commune aux oligos, on aboutit à un problème d'optimisation combinatoire, celui de la surséquence de longueur minimum. Dès que le nombre d'oligos est supérieur à 2, le problème est NP-difficile. Nous avons comparé des méthodes approchées dont les résultats en moyenne sont similaires ; elles permettent néanmoins de réaliser une économie de l'ordre de 10 à 15 % sur le nombre de masques pour des puces à 20 000 oligos.

(ii)        Pour des raisons de fiabilité dues à la très haute intégration des puces, et aux difficultés relatives à la synthèse in-situ, il peut être intéressant de faire figurer sur la puce plusieurs réalisations d'un même oligo, soit des copies synthétisées à l'aide de suites différentes de masques. Ainsi, pour un oligo, un même masque ne devrait être utilisé que pour une seule de ses réalisations. Nous avons défini une méthode de programmation dynamique pour déterminer si une surséquence (de masques) permet de réaliser deux copies disjointes d'un même oligo. La question est celle de la complexité du problème de décision : Etant donné un entier k, un mot m et une séquence s, est-ce que s contient k copies disjointes de m ? Dans le cas où k = 2, nous avons montré que le problème est polynomial; un algorithme énumératif permet de déterminer le nombre maximum de copies disjointes réalisables avec une surséquence de masques. Nous avons développé une méthode constructive qui permet d'établir une suite de masques capable d'engendrer un ensemble d'oligos donné, telle que chaque oligo ait au moins deux réalisations disjointes. Elle est linéaire en fonction du nombre d'oligos et quadratique en leur longueur.

 

A.    Guénoche.- Supersequences of masks for oligo-chips, Journal of Bioinformatics and Computational Biology, 2, 3, 2004, 459-469.

A.  Guénoche.- About the design of oligo-chips, Discrete Applied Mathematics, 147, 2005, 57-67.

 

RECHERCHE DE ZONES DENSES DANS UN GRAPHE

 

Partant d'un graphe, on cherche à construire des classes de sommets ayant un pourcentage d'arêtes internes supérieur à la moyenne (des communautés). L'idée de départ est de calculer en chaque sommet une valeur de densité, fonction du nombre d'arêtes présentes dans son voisinage. La construction des classes se fait alors de façon progressive, en cherchant les zones de densité maximum, puis en affectant progressivement les sommets adjacents à ces zones, pour fabriquer successivement des classes "noyaux", des classes "étendues" et finalement des classes "complètes", qui réalisent soit une partition des sommets du graphe, soit un recouvrement, si l'on admet des affectations multiples. Pour mettre au point et valider la méthode, nous avons établi des mesures de comparaison entre partitions, en particulier une distance d'édition égale au plus petit nombre d'éléments à déplacer pour passer d'une partition à une autre. On aboutit à un problème d'affectation (couplage de poids minimum dans un graphe biparti) bien connu en recherche opérationnelle.

 

La méthode de construction de classes à l'aide d'une fonction de densité peut s'appliquer é n'importe quel espace métrique. Etant donné un tableau de distance, il suffit d'en extraire un graphe et d'évaluer la densité en chaque sommet à l'aide des valeurs de distances dont sont munies les arêtes du graphe. Deux types de graphes extraits ont été comparés ; les graphes seuil, ne contenant que les paires (arêtes) dont la distance est inférieure ou égale à un seuil donné ; les graphes "réguliers" de degré k, en sélectionnant pour chaque sommet ses k plus proches voisins. Une fois l'un de ces paramètres fixé, la densité est mesurée ; elle est inversement proportionnelle à la moyenne des distances aux sommets adjacents. La construction des classes à partir des maxima locaux de la fonction de densité est alors réalisée.

 

T. Colombo, Y. Quentin, A. Guénoche.- Recherche de zones denses dans un graphe : application aux gènes orthologues, Colloque « Knowledge Discovery and Discrete Mathematics », Actes des Journées Informatiques de Metz, 2003, pp. 203-212.

A. Guénoche, H. Garreta.- Representation and evaluation of partitions, Proceedings of IFCS'2002, K. Jajuga et al. (Eds.), Springer, 2002, pp 131-138.

A. Guénoche.- Clustering by vertex density in a Graph, Meeting of the International Federation of the Classification Societies, IFCS'2004, in Classification, Clustering and Data Mining, D. Banks et al. (Eds.), Springer, 15-23.

T. Colombo, A. Guénoche.- Looking for high density zones in a graph, in Selected Contributions in Data Analysis and Classification, P. Brito et al. (Eds.), Springer, 2007, pp. 193 - 201.

 

 

 

Et maintenant, quelques textes plus utiles ou plus divertissants :

 

De la thèse considérée comme un genre littéraire


Balades dans les Calanques au départ de Luminy