Institut de Mathématiques de Luminy 
Equipe Méthodes Mathématiques pour la Génomique
Thèmes : Info-Bio-Math, Algorithmique Combinatoire, Classification
Alain Guénoche
Directeur de recherche CNRS
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.