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

Chargé 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 (Classification d'amphores, Sériation chronologique, Edition de textes hiéroglyphiques) et à l'Énumération d'Ensembles Combinatoires et au tirage aléatoire de configurations (Permutations et Partitions avec contraintes, Arbres couvrants), 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. Mon sujet principal actuel est la classification d'un ensemble muni d'une distance, soit par la construction de partitions qui optimisent un critère soit par la construction d'arbres, autrement dit, l'approximation d'une dissimilarité par une distance (additive) d'arbre. Ces recherches sont motivées par la prédiction fonctionnelle des protéines et à la reconstruction d'arbres phylogénétiques.

Je suis co-auteur (en collaboration avec J.P. Barthélemy) d'un ouvrage Les arbres et les représentations des proximités, édité en français chez Masson (1988) et en anglais Trees and Proximity Representations chez John Wiley (1991), d'une quinzaine d'articles dans des revues internationales (Discrete Math., J. of Classification, ..) et d'autant d'exposés dans des colloques internationaux dont les actes sont publiés sous forme de livre.

 

Travaux récents

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 de longs fragments de DNA et des séquences protéiques, de leurs interaction 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 d'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 mais débouchent sur des travaux de recherche en Info-Bio-Maths ; plus particulièrement en algorithmique, sur les mots et les graphes, et en classification pour des problèmes comme le séquençage, la conception des puces à oligos, l'évolution ou la prédiction fonctionnelle des protéines.

Distance d'ordres

Ces dernières années, j'ai étudié la construction d'arbres, en partant non plus des distances, mais des ordres de proximité relatifs à chaque élément. A chacun on associe l'ordre des distances croissantes aux autres éléments, c'est-à-dire l'ordre suivant lequel il voit tous les autres. Puis on calcule la distance de la différence symétrique entre ces relations de préordre pour obtenir une distance d'ordres. La distance entre deux préordres est basée sur le nombre de désaccords et de semi-accords sur les paires d'éléments. La distance d'ordres associée à une disimilarité ne dépend que de sa préordonnance, c'est-à-dire de l'ordre de ses valeurs. J'ai d'abord montré que la distance d'ordres associée à une distance d'arbre est elle-même une distance d'arbre de même topologie (ensemble de bifurcations). J'ai ensuite donné une interprétation ordinale de la condition des quatre points et montré qu'une préordonnance est représentable par un arbre ssi sa distance d'ordres est une distance d'arbre.

Distance partielle et reconstruction phylogénétique

En collaboration avec B. Leclerc (EHESS) et L. Duret (CNRS) nous avons étudié ce même problème d'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 pairs 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 apparaît 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 de grandes familles de graphes support pour que le problème soit traitable et défini un algorithme de complexité polynomiale qui permet de décider si un graphe (valué) donné peut être complété pour donner une distance d'arbre.

Conception des puces à oligos

Les oligonucléotides sont de courtes séquences - une vingtaine des bases - A, T, G ou C - fixées sur un support - verre ou silicium - de quelques cm2. Ces puces permettent de détecter, par hybridation, la présence de séquences complémentaires dans une solution qui leur est soumise. Cette technique devrait révolutionner, dans les dix ans à venir, l'analyse médicale - recherche de virus ou de bactéries - aussi bien que le contrôle de l'environnement et la qualité agro-alimentaire. C'est aussi une technique qui s'avère essentielle pour l'étude du fonctionnement de la cellule, puisque ces puces permettent de détecter les ARN, donc les protéines actives, au fil des processus biologiques. Les problèmes que j'ai abordés sont de trois 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 sur-séquence des oligos, et que les masques sont coûteux à réaliser, on aboutit à un problème d'optimisation combinatoire, celui de la sur-sé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, ces copies étant synthétisées à l'aide de suites différentes de masques. Ainsi, pour un oligo, un même masque ne pourrait ê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 sur-séquence (de masques) permet de réaliser deux copies disjointes d'un même oligo. La question à traiter 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éalisable avec une sur-séquence de masques.

 

(iii) Enfin, nous avons développé une méthode constructive qui permet d'établir une sur-séquence d'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.

 

 
Projet de recherche

Algorithmique combinatoire pour la génomique

 

 

 

Le séquençage systématique des génomes complets a permis de détecter la quasi totalité des gènes d'un organisme. Cette masse d'information permet de poser un des problèmes essentiels en Biologie : identifier la fonction de chaque gène, sachant que près de la moitié de ces gènes codent pour des protéines dont on ignore la fonction. Jusqu'à présent l'outil de base était la comparaison structurelle des séquences, mais à celui-ci viennent s'ajouter d'autres approches nouvelles :

- les puces à ADN permettent de mesurer le niveau d'expression des gènes dans certaines conditions expérimentales et/ou à un moment donné ;

- des expériences systématiques de double hybridation qui détectent les interactions directes protéines-protéines.

Ces deux types de données supplémentaires permettent d'aborder la classification fonctionnelle des protéines et ainsi de fournir des hypothèses fortes sur la fonction des gènes associés, en particulier quand les séquences ne ressemblent à rien de connu.

 

Ce séquençage des génomes complets permet aussi de connaître l'agencement des gènes dans chaque espèce. A partir d'une définition formelle de l'orthologie, qui permet d'identifier les paires de gènes directement hérités d'un ancêtre commun, on peut mettre en bijection certains des gènes de deux organismes et aborder la question de l'histoire évolutive des espèces.

 

Dans les années à venir, je compte travailler sur deux thèmes particulièrement importants en info-bio-math : la classification fonctionnelle des protéines et la comparaison des génomes suivant l'ordre de leurs gènes ou de motifs. Le premier thème couvre quatre sujets : les méthodes de partitionnement, la recherche de zones denses dans les graphes d'interaction, la recherche de classes de profils d'expression et la classification par arbre dans le cas de distances incertaines. Les deux premiers points sont déjà l'objet de recherches en cours, dans le cadre d'un contrat bioinformatique financé par les EPST. Le second thème débouche sur des questions d'informatique théorique (génération du groupe des permutations d'ordre fini, tableaux standards) ; il est aussi intéressant du point de vue de l'algorithmique combinatoire que du point de vue de l'évolution.

 

 

1 CLASSIFICATION FONCTIONNELLE DES PROTEINES

 

Sur ce sujet, j'ai monté en 2000-2001 un projet de recherche en collaboration avec deux laboratoires de biologie de Marseille (le LGPD - génétique du développement - et le LCB - évolution des génomes bactériens), et trois équipes d'informatique (l'IML, l'ENST Paris et l'IRESTE à Nantes). Il a été retenu par une commission inter-EPST de Bio-Informatique et a débuté au printemps 2002. Nous avons obtenu un soutien sur deux ans. Le travail est en cours et doit se poursuivre en 2003, et début 2004.

 

1.1 METHODES DE PARTITIONNEMENT

 

Ce sont des méthodes de classification dans lesquelles on cherche à construire des partitions d'un ensemble, indépendamment de l'organisation des classes sous forme hiérarchique. Notre projet porte sur le développement de méthodes de construction de classes, sans passer par l'approximation d'un arbre de classification, ni par une projection dans un espace euclidien. Notons X l'ensemble des éléments à classer et D la distance calculée sur chaque paire d'éléments de X. Les méthodes étudiées relèvent de l'optimisation combinatoire : on cherche à optimiser un critère, une fonction de D, sur l'ensemble des partitions de X à nombre de classes fixé. Cette approche n'est pas nouvelle (on consultera (Hansen, Jaumard 1997) pour un bilan récent) mais pratiquement ignorée en Bio-Informatique, exceptées les méthodes de centres (k-means) qui n'opèrent pas à partir d'une distance. Nous avons largement entamé cette étude, pour plusieurs types de distance (booléenne, euclidienne ou arborée).

 

Généralement le nombre de classes n'est pas connu ; c'est à l'utilisateur de fixer des bornes inférieures et supérieures pour le nombre attendu de classes. Les programmes calculent alors une partition optimisée pour chaque valeur tombant dans cet intervalle. Devant ce grand nombre de partitions, correspondant à un critère d'optimisation et un certain nombre de classes, il faut se donner les moyens de choisir. Nous avons étudié plusieurs critères de comparaison et avons proposé, avec H. Garreta (LIF), un mode de représentation des partitions sous la forme d'un arbre de boites qui permet d'apprécier graphiquement la qualité d'une partition ; le logiciel correspondant est accessible.

 

1.2 RECHERCHE DE ZONES DENSES DANS UN GRAPHE D'INTERACTION

 

Des techniques modernes de cribles double-hybride permettent de détecter des interactions directes entre proteines. Souvent l'orientation n'est pas donnée, et les liens sont considérés comme des arêtes (non orientées) qui permettent de construire un graphe d'interaction ; les sommets sont donc toutes les protéines d'une espèce donnée, et un arc relie les protéines A et B si et seulement si A interagit avec B, ou si elles ont un interacteur commun. L'hypothèse sous jacente à notre travail, en collaboration avec B. Jacq et C. Brun (LGPD) est que si deux protéines partagent un grand nombre d'interacteurs communs, il y a de grandes chances qu'elles soient fonctionnellement reliées. Les graphes que nous analysons portent sur plusieurs organismes (E. Coli, H. Pylori). Ils peuvent être très gros, contenant plusieurs milliers de sommets, et de degré moyen compris entre 3 et 6.

 

Notre approche consiste à chercher dans le graphe des zones de forte densité d'arêtes c'est à dire des classes dans lesquelles les protéines interagissent beaucoup. Une première étude nous a conduit à mesurer une distance entre sommets basée sur le nombre d'interacteurs communs. Nous avons utilisé la distance de Szekanovki-Dice, classique pour le partitionnement de grands graphes. Du fait que deux sommets non adjacents à un même sommet sont à distance maximum, cette distance est très proche d'une ultramétrique et donc il n'y a pas de difficulté à la représenter sous forme d'un arbre de classification. Reprenant un travail antérieur, nous avons ainsi identifié un certain nombre de classes dans l'arbre, classes auxquelles nous pouvons donner une interprétation fonctionnelle. Ce premier travail a été présenté à JOBIM'2002 et, complété par une analyse de la validité des prédictions, sera proposé à une revue de Biologie moléculaire.

 

Une seconde étude, à entreprendre, porte sur la notion de quasi-clique, c'est à dire de sous-ensemble de sommets constituant un sous-graphe de degré borné inférieurement (par exemple au moins 4 interactions). Certains algorithmes de construction de cliques maximales dans un graphe peuvent être adaptés à la définition de ces configurations.

 

1.3 CLASSIFICATION DES DONNEES D'EXPRESSION

 

Une puce à ADN permet de mesurer les quantités d'ARN produits par une cellule dans des conditions expérimentales particulières à un instant donné. Elle révèle ainsi quels sont les gènes actifs. La répétition de cette observation à des instants consécutifs permet d'étudier le fonctionnement d'une cellule. Les biologistes espèrent beaucoup de cette technique pour analyser et modéliser les réseaux d'interactions entre protéines, en fonction de conditions expérimentales imposées.

Une puce mesure pour chaque gène, l'intensité de son expression. La comparaison de ces variables quantitatives, à différents moments, permet de caractériser des profils d'expression et ainsi d'analyser les relations de dépendance ou de simultanéité d'activation. Les puces sont réalisées avec des objectifs généraux et la plupart des gènes accessibles sur la puce ne sont pas particulièrement activés dans le processus étudié. Donc il n'est pas souhaitable de classer tous les éléments. De plus, certains sont loin de tous les autres, et donc inclassables, parce qu'ils n'entrent pas dans une classe homogène. Plutôt que de chercher à les éliminer en premier lieu, nous comptons développer une approche connue sous le nom de classification séquentielle.

 

Nous avons réalisé un premier travail, en collaboration avec M. Lescot (LGPD), en classant un certain nombre de gènes d'Arabidopsis Thaliana impliqués dans un phénomène de stress. Notre approche est basée sur l'observation des variations d'intensités d'expression consécutives. Du point de vue méthodologique, nous avons d'abord construit une suite de classes homogènes. A chaque étape, on étudie toutes les classes centrées sur chaque élément. On optimise un critère comme le diamètre ou le rayon, puis on retire la "meilleure" classe. Et l'on réitère la procédure tant que l'on peut extraire un nouveau groupe. Les éléments déclarés inclassables sont ceux qui restent. Ensuite, nous avons appliqué aux protéines sélectionnées une méthode de partitionnement avec un critère adapté aux données euclidiennes. Enfin, en nous basant sur la comparaison des partitions correspondant à différents nombres de classes, nous sommes arrivés à des classes satisfaisantes [70].

 

 

2 COMPARAISON DES GENOMES SELON L'ORDRE DES GENES

 

Mon second thème de recherche porte sur la comparaison des ordres des gènes, dans les génomes complets. Il est largement admis que la diversité du vivant est dûe aux recombinaisons, duplications et réarrangements des gènes le long du ou des chromosomes. Le principe est de mesurer des distances évolutives entre espèces sur la base de la comparaison non plus des séquences, mais des ordres des gènes hérités d'un gène ancestral commun, dits gènes orthologues.

 

Cette étude a été commencée il y a une petite dizaine d'années par D. Sankoff qui a posé le principe du retournement d'intervalles de gènes consécutifs (reversal distance). Il s'agit de compter le nombre minimum de retournements d'intervalles qui permettent de passer d'un ordre à un autre. Elle a abouti, récemment, à un algorithme de complexité linéaire (B. Moret [2001]), dans le cas signé, c'est-à-dire lorsque l'on différencie les brins porteurs des gènes.

 

Cette approche très combinatoire de la comparaison des génomes ne tient pas compte d'un certain nombre de difficultés :

- D'abord beaucoup de génomes bactériens ont un chromosome circulaire et la notion d'intervalle doit être étendue au delà des extrémités de l'ordre ou de la permutation.

- Il ne faut pas considérer que les retournements d'intervalles, puisqu'il y a aussi des translations. Il n'y a pas d'algorithme efficace (polynomial) si l'on admet les deux types d'opération simultanément.

- Les transformations ne tiennent pas compte de la réalité biologique, à savoir que tout intervalle ne peut pas être déplacé, quelle que soit sa position dans l'ordre et sa longueur. En particulier dans le cas des génomes circulaires, les intervalles retournés devraient contenir l'origine de réplication (ou la terminaison). Ceci pose l'intéressant problème des permutations circulaires que l'on peut engendrer à l'aide de retournements d'intervalles centrés sur l'une ou l'autre extrémité. Il est clair que, si l'on a le même nombre de gènes de part et d'autre de ces points diamétralement opposés, on ne peut engendrer qu'un petit nombre d'ordres.

 

Dans le cas où l'on ne sait pas différencier les brins, le problème de l'évaluation de cette distance est NP-difficile. Il en est de même si l'on mélange les opérations de translations et de retournement. J'ai pensé à lui substituer une autre mesure de similitude, la longueur d'une plus longue chaîne commune (LCC). Il s'agit de trouver la plus longue suite de gènes placés dans le même ordre dans deux génomes ou plus. Ce problème est polynomial dans le cas de deux, mais il le reste aussi pour plus de deux génomes, ce qui n'est pas le cas des plus longues sous-séquences communes. De plus l'algorithme étudié est extensible au cas des ordres circulaires. On a donc une mesure de similitude facilement calculable, quelque soit le nombre de gènes considérés (plusieurs milliers).

 

En terme de permutation, puisque l'on peut toujours numéroter les gènes communs (orthologues) dans l'ordre de l'un des génomes, l'une des permutations est l'identité et la plus longue chaîne d'éléments dans le même ordre est une suite croissante dans les autres permutations. Ceci relie le problème de la plus longue chaîne commune aux tableaux standards, bien connus en Combinatoire. La construction de Schensted-Robinson met en bijection les permutations et les paires de tableaux standards de même forme ; la longueur de la plus longue suite croissante est le nombre de cases de la première ligne des tableaux. Puisque l'on sait dénombrer les tableaux standards de forme donnée, on peut évaluer le nombre de permutations ayant une plus longue suite croissante de longueur fixée. On peut ainsi espérer évaluer des probabilités sur cet indice statistique, grâce à des résultats récents (Aldous, Diaconis, 1999) qui donnent la loi asymptotique de la longueur de cette suite.

 

 

Publications 98-2002

Revues
 

O. Gascuel, B. Bouchon-Meunier, G. Caraux, P. Gallinari, A. Guénoche Y. Guermeur, Y. Lechevallier, C. Marsala, L. Miclet, J. Nicolas, R. Nock, M. Ramdani, M. Sebag, B. Tallur, G. Venturini, P. Vitte.- Twelve numerical, symbolic and hybrid supervised classification methods, International Journal of Pattern Recognition and Artificial Intelligence, 12, 5, 1998, pp. 517-571.

A. Guénoche.- Ordinal properties of tree distances, Special Issue of Discrete Math. on Discrete Metric Spaces, 192, 1998, pp. 103-117.

A. Guénoche, S. Grandcolas.- Approximation par arbre d'une distance partielle, Mathématiques, Informatique et Sciences humaines, 146, 1999, 51-64.

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

C. Brun, A. Guénoche, B. Jacq.- Approach of the functional evolution of duplicated genes in Saccharomyces cerevisiae using a new classification method based on protein-protein interaction data, Journal of Structural and Functional Genomics, 3, 2003, 213-224.

A. Guénoche.- Partitions optimisées : évaluation et comparaison, Mathématiques, Informatique et Sciences humaines, à paraître, 2003. [ PDF ] 200 k

 

A. Guénoche.- About the design of oligo-chips, Discrete Applied Maths, to appear. [ PDF ] 149 k

 

Conférences internationales avec actes
 

A. Guénoche, P. Préa.- Counting and selecting at random phylogenetic topologies to compare reconstruction methods, Proceedings of the Conference of the International Federation of the Classifications Societies, IFCS'98, Roma, Short papers volume, pp. 242-245.

A. Guénoche, S. Grandcolas.- Estimating missing values in tree distances, in Data Analysis, Classification and Related Methods, H.A.L. Kiers et al. (Eds.), Proceedings of the IFCS'2000, Springer, 2000, pp. 143-148.

 

A. Guénoche.- On the realisations of a word in a sequence, Ordinal and Symbolic Data Analysis Conference, OSDA'2000, Bruxelles, Juillet 2000.

Guénoche Alain, Garreta H. - Can we have confidence in a tree representation ? Proceedings of JOBIM'2000, Lecture Notes in Computer Sciences, vol. 2066, pp. 43-53, 2001. 
[ PDF ] 164 k

 

A. Guénoche, B. Leclerc, V. Makarenkov, On the extension of a partial metric to a tree metric, International Conference on Graph Theory, Marseille, Aout 2000, Discrete Maths, to appear. [ PDF ] 213 k

 

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

 

Et maintenant, quelques textes plus divertissant :


Balades dans les Calanques au départ de Luminy

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