Institut de Mathématiques de Luminy

RAPPORT D'ACTIVITÉ

MÉTHODES MATHÉMATIQUES POUR LA GÉNOMIQUE

1. INTRODUCTION
2. CLASSIFICATION FONCTIONNELLE
 

2.1.   Méthodes de partitionnement
2.2.   Comparaison des partitions
2.3.   Prédiction fonctionnelle des protéines

3. MODÉLISATION DE RÉSEAUX DE RÉGULATION GÉNÉTIQUES
4. GÉNOMIQUE COMPARATIVE
 

4.1.   Recherche de synthénies
4.2.   Comparaison des génomes bactériens complets
4.3.   Conception des bio-puces
4.4.
   Comparaison évolutive des tumeurs

1. INTRODUCTION

L'équipe MMG développe des recherches méthodologiques pour l'étude de questions biologiques. Elle sont essentiellement de trois types : Classification fonctionnelle des protéines, Modélisation des réseaux de régulation cellulaire, Génomique comparative. Les domaines mathématiques et informatiques concernés sont essentiellement les Mathématiques discrètes, la Statistique et l'Algorithmique combinatoire.

2. CLASSIFICATION FONCTIONNELLE

Les chercheurs concernés sont S. Bérard, T. Colombo et A. Guénoche.

2.1. Méthodes de partitionnement

Plusieurs problèmes en Biologie peuvent se décrire en terme de graphes dans lesquels les sommets sont des gènes - ou les protéines correspondantes - et la relation qui les lie porte sur des propriétés comme l'orthologie (héritage direct d'un gène ancestral commun), des profils d'expression similaires dans des conditions expérimentales particulières ou le contact direct au cours d'un processus biologique. Les propriétés communes de ces graphes est qu'ils ont plusieurs milliers de sommets et qu'ils sont de petit diamètre ; ce sont des small worlds (Milgram 1967).

Une façon d'aborder les problèmes biologiques sous-jacents est de rechercher des classes dans ces graphes, caractérisées par une densité d'arêtes plus forte que le moyenne. Cette question est également d'actualité pour des problèmes d'autre nature, comme l'analyse de réseaux sociaux (Batagelj, 2000, Newman, 2001) ou l'étude du "Web graph" (Barabasi et al. 1999) qui se posent plus ou moins de la même façon. Plusieurs méthodes récentes ont été définies dans ces domaines, essentiellement à partir de pondérations d'arêtes et de déconnection du graphe par élimination des arêtes de poids fort. Ce sont donc des méthodes de graph partitioning.

Notre approche est basée sur une pondération des sommets, par une fonction de densité et la construction des classes autour des sommets de densité localement maximum. Plusieurs fonctions, basées sur le nombre d'arêtes dans le voisinage de chaque sommet ont été étudiées et comparées ainsi que plusieurs stratégies progressives d'agglomération autour de "noyaux" que l'on étend. Des procédures de simulation on permit de définir un algorithme performant quand la différence de densité d'arêtes à l'intérieur des classes ou entre classes est nette.

L'intérêt immédiat de cette classification par densité est son efficacité. Si l'on a n sommets dans un graphe de degré maximum , l'évaluation de la fonction de densité est en O(n2) alors qu'une pondération des arêtes est pour le moins en O(n2). Compte tenu de la taille des graphes considérés, la linéarité en n est ici essentielle.

2.2. Comparaison des partitions

L'évaluation des performances et la comparaison des algorithmes de partitionnement (d'un graphe ou d'un ensemble muni d'une métrique) nous a amené à comparer une partition initiale P et celle, notée Q, qui était reconstruite par un algorithme particulier. Les indices classiques de comparaison des partitions portent sur le nombre de paires d'éléments simultanément réunis ou séparés dans P et Q et des indices statistiques normalisés ont été définis.

Nous nous sommes intéressés à une autre mesure de proximité entre partitions définie comme le plus petit nombre d'éléments qu'il faut déplacer d'une classe dans une autre, éventuellement vide, pour transformer P en Q. En collaboration avec un groupe de l'ENST (I. Charron, O. Hudry, C. Denoeud), nous avons étudié cette distance d'édition entre partitions d'un ensemble, que nous avons baptisée distance des transferts notée (P,Q). Nous avons principalement :

Cette distance permet d'énumérer les partitions très proches d'une partition P et ainsi de comparer les indices de distance classiques, basés sur les paires. Tous ont le défaut de donner des valeurs identiques à des partitions très proches ou très éloignées du point de vue des transferts.

2.3. Prédiction fonctionnelle des protéines

L'un des objectifs du projet EIDIPP, soutenu par l'ACI IMPBio est d'étudier les interactions protéine-protéine par des méthodes informatiques appliquées à des graphes d'interaction. Le but est de déterminer des classes fonctionnelles, qui regroupent des protéines collaborant à une même fonction biologique. L'hypothèse largement admise en Biologie, et qui est défendue par l'équipe de B. Jacq (Laboratoire de Génétique et Physiologie du Dévelop-pement) avec qui nous collaborons sur ce sujet, est que ces classes fonctionnelles sont repérables grâce à une forte densité d'arêtes.

De fait, nous disposons de graphes dont les sommets sont les protéines d'un organisme, actuellement la levure (ou la drosophile) et les arêtes correspondent à la relation d'interaction directe. Ce graphe est la synthèse de plusieurs types de données ; soit des relations extraites de la littérature scientifique, soit le résultat d'expérimentations biochimiques à grande échelle. Par ailleurs, une liste de fonctions connues pour les protéines de la levure (YPD) a été établie. Pour la plupart des protéines, une fonction au moins est connue ; on cherche à prédire celle des autres.

Nous avons développé une première approche (Prodistin) grâce à laquelle nous avons obtenu des résultats encourageants quant à la prédiction fonctionnelle, meilleurs que ceux produits par d'autres méthodes. La règle de prédiction que nous avons adoptée est relativement simple. On commence par mesurer une distance entre protéines sur la base du nombre d'interacteurs communs (distance de Sczekanovsky-Dice). Cette distance étant proche d'une ultramétrique, on construit un arbre de classification. Les classes sélectionnées (non disjointes) correspondent à des sous-arbres dont les protéines possèdent au moins une fonction majoritaire. Les prédictions sont faites à l'intérieur des classes, sans tenir compte des interactions externes. Pour mesurer la qualité des prédictions, on applique la règle de prédiction aux protéines de fonctions connues et l'on mesure le pourcentage de fonctions retrouvées et le pourcentage de fonctions prédites qui sont vraies.

Un prolongement de ce travail est en cours dans lequel les classes (éventuellement chevauchantes) sont maintenant réalisées par la méthode de classification par densité et les prédictions fonctionnelles se font en référence au standard actuel des descriptions fonctionnelles, "Gene Ontology", dans lequel les fonctions sont décrites par un réseau de termes partiellement ordonné par spécificité.

3. MODÉLISATION DE RÉSEAUX DE RÉGULATION GÉNÉTIQUES

Les chercheurs concernés sont B. Mossé et E. Remy.

Les biologistes ont systématiquement recours à des schémas pour représenter les réseaux de régulation impliqués dans les processus et fonctions biologiques qu'ils étudient. Cette pratique se formalise assez naturellement en ayant recours à la théorie des graphes. Dans le cas de systèmes de régulation génétiques, les gènes ou leurs produits sont associés aux sommets du graphe et leurs interactions sont représentés par les arcs reliant ces sommets (arcs signés, positivement dans le cas d'une activation, et négativement dans le cas d'une inhibition). Dès lors que l'on veut préciser la dynamique d'expression de réseaux de régulation complexes, il s'avère nécessaire de préciser formellement la manière dont la combinaison des différentes interactions afférentes influence l'expression ou l'activité d'un composant moléculaire. Nous avons choisi de travailler sur la base de deux méthodes formelles qualitatives.

La première méthode est la modélisation logique. Elle associe à chaque élément du réseau une variable discrète multivaluée représentant de façon qualitative ses différents niveaux d'expression, et des fonctions qui représentent son niveau de synthèse. Un des objectifs est de caractériser des liens entre des propriétés structurelles ou topologiques du réseau de régulation et des propriétés dynamiques du système (points stationnaires, stables/instables, cycles limites, bassins d'attraction, etc...) Une analyse (dans ce cadre logique) de la dynamique de circuits de régulation isolés a déjà donné des résultats prometteurs, mettant en valeur la génération de ces propriétés dynamiques selon le signe du circuit, en cohérence avec les conjectures de R. Thomas. Nous souhaitons maintenant regarder la généralisation de tels résultats, toujours dans le cadre logique.

Des problèmes combinatoires apparaissent (surtout en ce qui concerne la génération des graphes dynamiques), qui sont liés à l'accroissement des réseaux de gènes considérés au-delà de quelques dizaines d'éléments. Pour pallier cette difficulté, nous mettons parallèlement en oeuvre une approche à l'aide de réseaux de Petri. Une proposition de réécriture systématique de réseaux logiques en réseaux de Petri nous donne des perspectives encourageantes, car cela ouvre la voie vers une grande classe d'outils algébriques à exploiter. Cette approche a été appliquée tout d'abord dans un cadre booléen, pour modéliser et analyser les réseaux de régulation moléculaire impliqués dans le contrôle de la différentiation des lymphocytes Th du cycle cellulaire durant le début du développement de Drosophila melanogaster et de la morphogénèse de la plante Arabidopsis Thaliana, puis dans le cadre multivalué pour le réseau de contrôle de la décision lytique/lysogénique du bactériophage Lambda.

4. GÉNOMIQUE COMPARATIVE

Les chercheurs concernés sont G. Didier, B. Ghattas, A. Guénoche, L. Tichit.

4.1. Recherche de synthénies

Le fait qu'un groupe de gènes apparaissent successivement le long d'un génome leur permet, à cause de mécanismes de transcription relatifs à la structure de l'ADN cellulaire, d'être exprimés dans des temps rapprochés et, de ce fait, être potentiellement impliqués dans une même fonction biologique.

Retrouver un même ensemble de gènes apparaissant successivement le long d'un chromosome, éventuellement - et surtout - dans des ordres différents dans plusieurs génomes, peut résulter d'une pression sélective due a une coopération effective de ces gènes pour réaliser une même fonction biologique. Une méthode pour détecter des groupes de gènes fonctionnellement associés consiste donc à mettre en évidence des conservations locales de la composition génique dans des génomes différents.

Le problème a été, dans un premier temps, étudié sous une forme restrictive puisqu'on n'y autorise qu'un seul exemplaire d'un gène par organisme. Sous cette hypothèse, chaque séquence des gènes d'un organisme est représentée comme une permutation de l'ensemble total des gènes. La détermination des conservations locales de composition dans des permutations, appelées intervalles communs, a été résolue, initialement dans un cadre non-génomique, de manière très efficace (A. Bergeron, F. Corteel, M. Raffinot).

Malheureusement l'approche précédente ne permet pas de prendre en compte l'existence de duplications d'un gène dans un même génome donnant des gènes dits paralogues. A partir de certaines de leurs propriétés, nous avons donc tout d'abord mis au point un algorithme permettant de déterminer les segments de même composition génique présents dans deux génomes, autrement dit les intervalles communs de séquences qui ne sont pas nécessairement des permutations (WABI'03). Ces résultats et algorithmes ont été ensuite étendus à des questions plus générales, incluant notamment la recherche de conservations locales de composition génique dans un nombre quelconque de génomes, et améliorés du point de vue de la complexité algorithmique (article soumis).

4.2. Comparaison des génomes bactériens complets

Ce thème porte sur la comparaison des ordres des gènes, dans les génomes complets. Il est largement admis que la diversité du vivant est due 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.

Cette approche a été proposée il y a une 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. Le premier algorithme polynomial, dans le cas signé, c'est-à-dire lorsque l'on différencie les brins porteurs des gènes, a été proposé par Hannenali et Pevzner (1995). Récemment un algorithme de complexité linéaire a été donné par B. Moret [2001].

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

Pour contourner certaines de ces difficultés, en collaboration avec F. Guyon (Université Paris 7), nous avons pensé :

La reconstitution d'un petit nombre de grands fragments de génomes considérés comme conservés, indépendamment des petits remaniements, permet de construire des scénarios évolutifs plus simples que ceux établis par la reversal distance.

4.3. Conception des bio-puces

Il y a deux types de bio-puces ; les puces à oligonucléotides qui contiennent jusqu'à 1 000 000 de courts fragments d'une vingtaine de bases, et les puces à ADN qui présentent quelques milliers de fragments de quelques centaines de bases. Ils sont fixés sur un support - verre ou nylon - de quelques cm2 et permettent de détecter, par hybridation, la présence de fragments complémentaires dans une solution qui leur est soumise. Cette technique a révolutionné les analyses médicales et écologiques - recherche de virus, de bactéries, de tumeurs ou d'anomalies de comportements cellulaires - aussi bien que le contrôle de 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 ARNs, donc les gènes activés, au fil des processus biologiques.

Les problèmes informatiques que nous avons abordés sont de trois types :

--- 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 des oligos, et que les masques sont très coûteux à réaliser, 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 utilisés pour des puces à 20 000 oligos.

--- 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 copies de chaque oligo, ces copies étant synthétisées à l'aide de suites de masques différentes. Ainsi, pour un oligo, un masque ne doit être utilisé que pour une seule de ses copies. La question à traiter est celle de la complexité du problème de décision : Etant donné un entier k, un mot et une séquence v, est-ce que v contient k copies disjointes de ? 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. Dans le cas où k = 2, le problème est donc polynomial. Un algorithme énumératif permet de déterminer le nombre maximum de copies disjointes réalisables avec une surséquence de masques.

--- Enfin, nous avons développé une méthode constructive qui permet d'établir une courte surséquence d'un ensemble de N oligos de longueur L. Si elle ne contient qu'une seule copie de chaque oligo, c'est une surséquence simple qui est obtenue en O(NL2) ; si chaque oligo a au moins deux copies disjointes, c'est une surséquence double obtenue en O(NL3). Du fait que ces algorithmes sont linéaires en fonction du nombre d'oligos, et que L est très petit par rapport à N, on peut traiter en quelques secondes des problèmes de toute dimension.

4.4. Comparaison évolutive des tumeurs

Les données de puces CGH permettent de savoir si un fragment d'ADN pris dans une cellule tumorale est dans sont état naturel (codé 0), s'il a disparu (codé -1) ou a été amplifiée (codé 1). De plus un examen clinique permet de préciser l'état d'avancement de la tumeur et l'on connaît parfois la durée de vie du patient. Le problème que nous avons abordé, en collaboration avec F. Guyon (Paris 7) et l'Institut Curie (C. Rouveirol, E. Barrillot, F. Radvanyi), est celui de la comparaison évolutive des tumeurs d'un même cancer à partir de ces données. Il est clair que les zones disparues, ne peuvent ni réapparaître ni être amplifiées, et que l'on peut ainsi établir une relation d'ordre partielle sur les tumeurs, l'une pouvant être un état antérieur à l'autre.

Dans cette étude qui débute, nous nous attachons à comparer l'état de gravité observé des tumeurs avec la relation d'ordre, en particulier pour celles qui n'ont que très peu de zones de mutations, mais qui sont dans des états cliniques avancés. Ces zones contiennent certainement des gènes responsables des cancers observés. Un autre but poursuivi est la classification des tumeurs, selon les procédés évolutifs suivis, qui peut révéler des types de cancers et déboucher sur des traitements appropriés.

Page d'accueil
Sommaire