[ Mathématique et génomique ] [ Autres thèmes de recherche ] [ Projet de recherche ]

Institut de Mathématiques de Luminy

Méthodes Mathématiques pour la Génomique
Rapport scientifique 1999-2002


Mathématique et génomique

L'Info-Bio-Math, plus communément appelée Bioinformatique, est un domaine de recherche inter-disciplinaire, né de la nécessité du recours à l'informatique et aux mathématiques pour aborder certains problèmes en biologie. Il s'agit, en ce qui nous concerne, de modéliser des processus de régulation, de prédire la fonction de protéines, d'analyser des séquences génétiques, par exemple les ordres de gènes dans les génomes complets. Les domaines concernés en Math-Info, sont la classification, la modélisation à l'aide de graphes, la combinatoire des mots, les processus stochastiques, l'algorithmique des ensembles ordonnés.

Classification (A. Guénoche, E. Remy).

Il s'agit d'étudier des méthodes de partitionnement pour la classification des protéines. Les données sont soit des graphes d'interaction, soit des niveaux quantitatifs d'expression mesurés par des puces à ADN (Données du transcriptome : on mesure l'intensité d'activation de plusieurs milliers de gènes dans différentes conditions expérimentales, ou dans des séries chronologiques). Quatre thèmes ont été développés :

Évaluation des valeurs manquantes (dans les données de transcriptome).

Plutôt que de renoncer à classer les gènes pour lesquels le niveau d'expression est parfois indéterminé, nous avons développé une méthode (non statistique) d'estimation de ces valeurs. Elle est basée sur une notion de voisinage autour d'un élément, lié à la dimension de leur espace de représentation (travail, mené en collaboration avec le Laboratoire Génome et Informatique d'Evry).

Sélection des éléments classables.

La plupart des gènes étudiés dans une puce à ADN n'ont pas d'effet dans les expériences étudiées, ou encore leur expression ne varie pas au cours du temps ; ils sont faciles à éliminer. Parmi les autres, on cherche des éléments qui ont suffisamment de "voisins" pour que leur affectation à des classes soit stable. Une des premières analyse à réaliser est de détecter les gènes dont les variations d'expression sont conjointes avec d'autres, de façon a construire des classes pertinentes.

Partionnement par optimisation de critères.

Dans le cas des graphes d'interaction comme dans celui des données d'expression, on se ramène à l'aide de métriques appropriées à un tableau de distance sur un ensemble X de gènes. Nous avons étudié des méthodes d'optimisation de différents critères sur l'ensemble des partitions de X à nombre de classes fixé. Nous avons également défini des critères d'ajustement d'une partition à une distance donnée, de façon à choisir, parmi plusieurs partitions concurrentes, établies sur le même ensemble, celle qui est le plus conforme à la distance initiale.

Représentation des partitions.

Une méthode de représentation des partitions par un arbre de boites qui met en évidence la qualité de la partition a été définie et implémentée. Celle-ci permettra, peut être, de remettre au goût du jour les méthodes de partitionnement en classification (travail réalisé en collaboration avec le LIF, Marseille).

Phylogénie (A. Guénoche).

Le problème de la reconstruction phylogénétique consiste à retrouver les arbres d'évolution d'un ensemble d'espèces, à partir de séquences alignées (pour faire apparaître les mutations), d'arbres déjà construits sur des sous-ensembles d'espèces (consensus ou puzzling d'arbres) ou d'une distance mesurée entre les espèces. Les méthodes développées ces dernières années portent :

Algorithmique des mots.

Conception des puces à oligo (A. Guénoche).

Nous nous sommes intéressés au problème de la plus longue sous-séquence commune à un ensemble de p séquences données (p>2), puis au problème dual de la plus courte sur-séquence commune. Ce problème est important pour la conception des puces à oligos (courts fragments d'une vingtaine de nucléotides), ainsi que d'autres problèmes annexes en rapport avec la fiabilité de ces puces (nombre de façons disjointes de synthétiser un oligo).

Méthodes d'analyse symbolique des séquences (B. Mossé, S. Jaeger).

Ce travail s'inscrit dans le cadre de la thèse de Sébastien Jaeger qui vient d'être soutenue. Déjà bien connues et largement utilisées en physique pour l'analyse statistique des suites symboliques, la complexité et l'entropie quantifient la diversité et la qualité de la répartition des facteurs. La majorité des résultats existants concerne le cas des suites infinies ; nous nous sommes attachés à préciser leur comportement dans le cas fini. Une troisième classe d'indicateurs, inspirée de la mécanique statistique, qui comprend la pression thermodynamique et l'énergie moyenne, a également été proposée. Nous avons étudié le comportement de ces indicateurs lorsqu'ils sont calculés dans une fenêtre de lecture glissant le long d'un mot. Ils sont actuellement appliqués à l'étude de séquences régulatrices d'ADN de la drosophile.

Réseaux d'interaction entre gènes et produits de gènes (ARN, protéines).

Modélisation Bayesienne des réseaux d'interaction (E. Remy, en collaboration avec F. Campillo).

Nous nous intéressons à la construction de réseaux d’interaction en s’appuyant sur les données d’expressions géniques. Ces données étant bruitées (procédures expérimentales, précision des mesures, phénomènes biologiques aléatoires), il nous paraît légitime de considérer les expressions de gènes comme des réalisations de variables aléatoires. En nous inspirant des travaux de Friedman et al, nous étudions des méthodes de type réseaux bayesiens .

Analyse des réseaux de régulation génétiques (B. Mossé, E. Remy, en collaboration avec D. Thieffry et C. Chaouiya, ESIL).

En partant de la modélisation des régulations génétiques par un formalisme logique purement discret, développé par D. Thieffry et R. Thomas, nous avons proposé un formalisme mathématique qui décrit les graphes de régulation génétiques et les graphes dynamiques correspondant. Il permet d'une part de comparer des graphes synchrones et asynchrones, et d’autre part de démontrer des conjectures comme celles concernant les propriétés dynamiques des circuits positifs et négatifs, ou le calcul des contraintes paramétriques sur les combinaisons de circuits fonctionnels. Ce travail sert de base au développement d'un logiciel (GIN-sim) qui permet la simulation et l'analyse qualitative des réseaux d'interaction.

Autres thèmes de recherche

Marches aléatoires sur un amas infini de percolation (E. Remy, en collaboration avec P. Mathieu, Université de Provence, Marseille).

Soit Xk une marche aléatoire sur un graphe infini, C. Le comportement de Xk en temps long dépend de la géométrie à l'infini de C. En particulier, on connaît bien les liens entre les propriétés isopérimétriques du graphe C et le comportement de sup x,y C Px[Xk = y]. Cet aspect est surtout bien compris dans le cas de graphes assez réguliers, par exemple si C est un groupe.

Dans ce travail, nous étudions la décroissance du noyau de la chaleur sur les sous-graphes aléatoires de Zd obtenus en percolation. Contrairement au cas d'un groupe, les comportements des quantités sup x,y C Px[Xk = y] et sup y C P0[Xk = y] où 0 est l'origine, diffèrent. De fait, un amas de percolation contenant, avec probabilité 1, des morceaux linéaires arbitrairement longs, il est clair que sup x,y C Px[Xk = y] se comporte comme 1/ k. En revanche, en choisissant l'origine comme point de départ de la marche, on obtient un effet de 'moyennisation' et le comportement de sup y C P0[Xk = y] est le même que pour la marche aléatoire sur Zd, soit k-d/2.

Étude symbolique des suites obtenues par itération d'une substitution (B. Mossé).

Il s'agit des suites produites par une machine simple. Partant d'une lettre de l'alphabet choisi, on la remplace par un mot et on itère ce procédé : si l'alphabet est l'ensemble A = {a,b,c}, et si on remplace systématiquement a par abc, b par ca et c par bb, alors a devient abc, qui devient abccabb, qui devient abccabbbbabccaca, etc. Un intérêt grandissant a été porté à ces suites en dynamique symbolique, lié à la possibilité de coder avec elles l'itinéraire de points de certains systèmes et d'en déduire des propriétés intéressantes du système. Dans le domaine des langages formels, où on parle plutôt de D0L-systèmes, les efforts ont porté surtout sur des questions de décidabilité de telle ou telle propriété. Dans tous les cas, deux outils de base sont constitués par l'étude des fonctions de croissance des lettres, c'est-à-dire la longueur des itérés successifs, et de la fonction de complexité qui compte les facteurs de longueur n quand n varie. Une difficulté est alors rencontrée, la désitération, c'est-à-dire le besoin de retrouver après plusieurs applications successives d'une substitution la trace des objets dont on est parti. Ma contribution, centrée sur ces questions de désitération (problème de "reconnaissabilité" ou de "circularité") a été présenté dans mon habilitation, une partie originale étant constituée par des applications de la circularité à l'énumération de facteurs et à l'étude de la fonction de complexité. Dans ce thème, je continue à travailler sur une conjecture, la décidabilité de la locale caténativité des D0L-systèmes, et sur des liens avec les pavages autosimilaires.

Projet de recherche

L'ensemble des thèmes de recherche en cours et portant sur les années à venir s'inscrivent principalement dans le cadre de l'Info-Bio-Math. Ils sont motivés par les collaborations étroites que nous entretenons avec les laboratoires de recherche en biologie qui ont une approche bio-informatique de leurs problèmes. Ces derniers débouchent sur des recherches méthodologiques dont nous donnons ici un aperçu.

Robustesse des classifications par arbre (A. Guénoche, B. Ghattas).

En classification, je compte m'intéresser au problème de la variation de la topologie des arbres de classification en fonction de l'incertitude sur les distances. La classification par arbre peut être vue comme une approximation d'une distance donnée par une ultramétrique. Le problème sous jacent est de savoir si, quand on modifie raisonnablement une distance, on obtient un arbre de classification similaire, surtout du point de vue de sa topologie (ou hiérarchie des classes). Un travail récent de V. Chepoi et B. Fichet permet d'aborder le problème d'un point de vue combinatoire en utilisant la norme infinie ; ils ont montré comment calculer (de façon polynomiale) une ultramétrique à écart minimum - au sens de cette norme - d'une dissimilarité donnée. On en déduit assez facilement une façon de décider si il existe une ultramétrique U comprise entre deux dissimilarités données D' et D". Une première étude a permis de comprendre comment déterminer à partir d'une distance D un paramètre minimum a, tel qu'il existe une ultarmétrique comprise entre (1-a).D et (1+a).D. Ce a peut être interprété comme un coefficient d'incertitude minimum pour qu'il existe une représentation par une arbre de classification de cette distance.

Comparaison des ordres de gènes dans les génomes complets

(A. Guénoche, T. Colombo).

Il est largement admis que la diversité du vivant est due aux recombinaisons, duplication et réarrangement des gènes le long du ou des chromosomes. Le principe est de mesurer des distances génétiques entre espèces sur la base, non plus de la comparaison des séquences, mais de la comparaison des ordres des gènes conservés (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 à posé le principe du retournement de chaînes de gènes consécutifs ("reversal" distance). Elle a abouti, récemment à un algorithme de complexité linéaire pour compter le nombre de retournements d'intervalles qui permettent de passer d'un ordre à un autre. Ceci n'est valable que pour les permutations signées.

Mais il n'y a pas que les retournements d'intervalles à prendre en compte, puisqu'il y a aussi des translations d'intervalles. Il n'y a pas d'algorithme efficace dans le cas où on admet les deux types d'opérations simultanément, non plus que dans le cas des génomes circulaires. De plus, les transformations ne tiennent pas compte de la réalité biologique, à savoir que tout intervalle ne peut pas être déplacé (dans le cas circulaire il doit contenir l'origine ou la terminaison de réplication), quelle que soit sa longueur. Nous comptons étudier les problèmes de comparaison d'ordres en tenant compte de ces contraintes.

Il y a encore bien d'autres problèmes ordinaux liés à l'analyse des génomes, en particulier la recherche d'un ordre ancestral et d'une reconstruction phylogénétique basée sur la conservation des ordres. Pour cela nous étudions les problèmes algorithmiques de construction de plus longues chaînes communes à un ensemble de permutations éventuellement circulaires

Analyse des réseaux de régulation génétiques (B. Mossé, E. Remy, B. Ghattas).

En nous appuyant sur un premier travail de formalisation de réseaux de régulation génétiques, nous cherchons à formaliser, démontrer et éventuellement élargir les conjectures sous-jacentes : celles concernant les propriétés dynamiques des circuits positifs et négatifs, la localisation des attracteurs ou le calcul des contraintes paramétriques sur les combinaisons de circuits fonctionnels. Nous souhaiterions aussi mettre en relation les topologies du graphe et ses différents cycles, en déduire des propriétés de ces derniers (bassins d'attraction, etc…).

Page d'accueil
Sommaire