Identification de motifs dans les réseaux métaboliques - Page 1 - test Tous nos livres sont imprimés dans les règles environnementales les plus strictes Il est interdit de reproduire intégralement ou partiellement la présente publication sans autorisation du Centre Français d’exploitation du droit de Copie (CFC) – 20 rue des GrandsAugustins – 75006 PARIS – Tél. : 01 44 07 47 70 / Fax : 01 46 34 67 19. © Éditions Edilivre – Collection Universitaire – 2008 ISBN : 978-2-35607-642-7 Dépôt légal : Août 2008 Tous droits de reproduction, d’adaptation et de traduction, intégrale ou partielle réservés pour tous pays. No d’ordre 202-2007 Ann´e 2007 e ` These Pr´sent´e e e ´ devant l’Universite Claude Bernard - Lyon 1 pour l’obtention ˆ du Diplome de Doctorat (arrˆt´ du 7 aoˆt 2006) ee u et soutenue publiquement le 26 octobre 2007 par Vincent Lacroix Identification de motifs dans les r´seaux m´taboliques e e D´finitions, algorithmes, et application e au m´tabolisme d’Escherichia coli e Directrice de th`se : Marie-France Sagot e Jury : Christian Gautier Michel Habib St´phane Robin e Marie-France Sagot Stefan Schuster Leen Stougie Dominique de Vienne ´ UNIVERSITE CLAUDE BERNARD-LYON 1 Pr´sident de l’Universit´ e e Vice-Pr´sident du Conseil Scientifique e Vice-Pr´sident du Conseil d’Administration e Vice-Pr´sident du Conseil des Etudes et e de la Vie Universitaire Secr´taire G´n´ral e e e M. le Professeur L. COLLET M. le Professeur J. F. MORNEX M. le Professeur J. LIETO M. le Professeur D. SIMON M. G. GAY ´ SECTEUR SANTE Composantes UFR de M´decine Lyon R.T.H. La¨nnec e e UFR de M´decine Lyon Grange-Blanche e UFR de M´decine Lyon-Nord e UFR de M´decine Lyon-Sud e UFR d’Ontologie Institut des Sciences Pharmaceutiques et Biologiques Institut Techniques de R´adaptation e D´partement de Formation et Centre de e Recherche en Biologie Humaine Directeur Directeur Directeur Directeur Directeur Directeur : : : : : : M. M. M. M. M. M. le Professeur le Professeur le Professeur le Professeur O. ROBIN le Professeur D. VITAL-DURAND X. MARTIN F. MAUGUIERE F.N. GILLY F. LOCHER Directeur : M. le Professeur MATILLON Directeur : M. le Professeur P. FARGE SECTEUR SCIENCES Composantes UFR de Physique UFR de Biologie UFR de M´canique e UFR de G´nie Electrique et des Proc´d´s e e e UFR de Sciences de la Terre UFR de Math´matique e UFR d’Informatique UFR de Chimie Biochimie UFR STAPS Observatoire de Lyon Institut des Sciences et des Techniques de l’Ing´nieur de Lyon e IUT A IUT B Institut de Science Financi`re et d’Assue rances Directeur Directeur Directeur Directeur Directeur Directeur Directeur Directeur Directeur Directeur Directeur : : : : : : : : : : : M. le Professeur A. HOAREAU M. le Professeur H. PINON M. le Professeur H. BEN HADID M. le Professeur A. BRIGUET M. le Professeur P. HANTZPERGUE M. le Professeur M. CHAMARIE M. le Professeur M. EGEA Mme. le Professeur H. PARROT M. le Professeur R. MASSARELLI M. le Professeur R. BACON M. le Professeur J. LIETO Directeur : M. le Professeur M. C. COULET Directeur : M. le Professeur R. LAMARTINE Directeur : M. le Professeur J. C. AUGROS Remerciements Je voudrais remercier ici tous ceux qui ont compt´ pour moi pendant ces e trois ann´es et qui ont su me donner l’envie de faire ce travail. e Tout d’abord, merci a mes rapporteurs, Michel Habib, Stefan Schuster et ` Dominique de Vienne d’avoir accept´ de lire et d’´valuer cette th`se. e e e Merci aux membres de mon comit´ de pilotage, Thomas Schiex, Gilles e Curien, Alain Viari et Laurent Duret qui ont permis de valider et critiquer les ´tapes interm´diaires de ma th`se. e e e Merci ` Cris, ma premi`re collaboratrice, c’´tait un plaisir de travailler a e e ensemble. Merci ` Leen et Alberto, tant de simplicit´ et d’intelligence r´unies, c’est a e e rare, et avec l’esprit d’´quipe ! e Merci ` Christian pour sa sagesse et son humanisme. a Merci ` Anne et Alain qui ont ´t´ ` l’origine de ce travail et qui m’ont a eea propos´ un sujet si riche. e Merci ` Sophie, St´phane, Jean-Jacques et Franck pour leur clart´ et leur a e e p´dagogie dans un domaine aussi difficile a appr´hender que celui des graphes e ` e al´atoires. e Merci ` Daniel d’avoir pris le temps de discuter de mes motifs. a Merci ` Fabien de m’avoir fait d´couvrir le dessin de graphes, j’esp`re a e e qu’on continuera a travailler ensemble. ` Merci a Misou puis Agn`s et Nathalie pour leur patience pour toutes les ` e missions de derni`re minute. e Merci a St´phane, Bruno et Lionel pour leur disponibilit´ et leur s´r´nit´ ` e e ee e face a des pannes g´n´ralement incompr´hensibles. ` e e e Merci ` L´o pour les hauts et les bas, les r´p`tes entre midi et deux, et a e e e son humour a toute ´preuve. ` e ´ Merci ` Emilie pour les caf´s-allong´s, les p’tites bi`res en terrasse, le a e e e temps des discussions. Merci ` Maud pour les bonnes vieilles fˆtes de ces derni`res ann´es. a e e e Merci ` Vicente pour les preuves math´matiques et les innovations lina e guistiques. v Merci ` Ludo d’avoir ´t´ un soutien sur le m´tabolisme, avec quelques a ee e mails douteux parlant de coude de la glycolyse. Merci ` Patricia et Manu d’avoir ´t´ pr´sents et ` l’´coute dans les moa ee e a e ments difficiles. Merci ` Odile pour sa bonne humeur et ses bonnes id´es. a e Merci ` Christelle pour les enseignements, c’´tait un plaisir de les pr´parer a e e ensemble. Merci ` Paulo pour les discussions sur la science. a Merci ` Pierre qui grˆce ` ses contrepetries m’a permis de faire une belle a a a th`se. e Merci ` Jeane et Sa¨ d’avoir ´t´ l` au d´but et d’avoir apport´ l’impulsion a ıd ee a e e initiale a l’´quipe. ` e ´ ´ Merci ` tous les Baobabs, Marilia, Claire, Elise, Nuno, Vincent, Eric, a Laurent, Sandrine... et les autres a venir. ` Merci ` Marie-France, fondatrice du baobab, tu ne comptes pas ton temps a pour les autres. Merci pour cet environnement scientifique et humain. Et merci ` tout lecteur potentiel, cette th`se prend son sens si elle peut a e vous ˆtre utile. e Table des mati`res e Introduction 1 Pr´ambule e 1.1 Qu’est-ce qu’une m´thode scientifique ? . . . . . . . . . . . . . e 1.2 Diff´rentes approches en bioinformatique . . . . . . . . . . . . e 1.3 La d´marche suivie dans cette th`se . . . . . . . . . . . . . . . e e ´ 2 Etat de l’art sur les r´seaux biologiques e 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Qu’est-ce qu’un r´seau biologique ? . . . . . . . . . . e 2.1.2 Les r´seaux m´taboliques . . . . . . . . . . . . . . . . e e 2.1.3 Les r´seaux de r´gulation de g`nes . . . . . . . . . . e e e 2.1.4 Les r´seaux de transduction du signal . . . . . . . . . e 2.1.5 Int´gration des r´seaux . . . . . . . . . . . . . . . . . e e 2.2 Donn´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 2.2.1 Les reconstructions de r´seaux . . . . . . . . . . . . . e 2.2.1.1 La premi`re ´tape de reconstruction . . . . e e 2.2.1.2 Le raffinement du mod`le . . . . . . . . . . e 2.2.1.3 Les outils disponibles . . . . . . . . . . . . . 2.2.2 Bases de donn´es . . . . . . . . . . . . . . . . . . . . e • KEGG . . . . . . . . . . . . . . . . • ECOCYC/BIOCYC . . . . . . . . 2.3 Mod´lisation du m´tabolisme . . . . . . . . . . . . . . . . . e e 2.3.1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1.1 Le graphe des compos´s et le graphe des r´ace e tions . . . . . . . . . . . . . . . . . . . . . . 2.3.1.2 Le graphe biparti et l’hypergraphe des compos´s . . . . . . . . . . . . . . . . . . . . . e 2.3.1.3 L’orientation des arˆtes . . . . . . . . . . . e 2.3.1.4 Le choix du mod`le de graphe . . . . . . . . e 2.3.1.5 Compos´s ubiquitaires . . . . . . . . . . . . e 2.3.2 Matrice stochiom´trique et Mod`les bas´s sur des cone e e traintes . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 R´seaux de Petri . . . . . . . . . . . . . . . . . . . . e ´ 2.3.4 Equations diff´rentielles . . . . . . . . . . . . . . . . e vii 1 5 5 7 8 11 11 11 12 14 15 15 16 16 17 17 18 18 19 20 20 21 . . . . . . . . . . . . . . . . . 21 . . . . 22 23 25 26 . 28 . 31 . 32 2.4 Analyse structurelle du m´tabolisme, les grandes questions e 2.4.1 Analyses topologiques classiques . . . . . . . . . . . 2.4.2 Les r´seaux “scale-free” . . . . . . . . . . . . . . . e 2.4.3 Les r´seaux petit-monde . . . . . . . . . . . . . . . e 2.4.4 Complexit´, robustesse et modularit´ . . . . . . . . e e 2.4.4.1 Complexit´ . . . . . . . . . . . . . . . . . e 2.4.4.2 Robustesse . . . . . . . . . . . . . . . . . 2.4.4.3 Modularit´ . . . . . . . . . . . . . . . . . e ´ 2.4.5 Evolution du m´tabolisme . . . . . . . . . . . . . . e 2.4.5.1 Analyse comparative . . . . . . . . . . . . 2.4.5.2 Mod`les d’´volution du m´tabolisme . . . e e e 2.4.5.3 Lien entre m´tabolisme et g´nome . . . . e e . . . . . . . . . . . . . . . . . . . . . . . . 33 33 34 36 37 37 38 39 46 46 49 52 3 Une nouvelle d´finition de motif dans le cadre des r´seaux e e m´taboliques e 55 3.1 La notion de motif . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Un exemple initial de motif dans le cadre des r´seaux m´taboliques e e - Cas de la synth`se de la lysine . . . . . . . . . . . . . . . . . 56 e 3.3 D´finitions - Mod´lisation . . . . . . . . . . . . . . . . . . . . 58 e e 3.3.1 Une nouvelle d´finition de motif . . . . . . . . . . . . . 58 e 3.3.2 D´finition des occurrences . . . . . . . . . . . . . . . . 60 e 3.3.3 D´finition des couleurs et de la fonction de score . . . . 62 e 4 La recherche de motifs color´s dans un graphe e 4.1 Le probl`me de la recherche de motifs color´s . . . . . . . . e e 4.1.1 L’´tude de complexit´ . . . . . . . . . . . . . . . . . e e 4.1.1.1 Complexit´ param´trique . . . . . . . . . . e e 4.1.2 Complexit´s relatives des motifs topologiques et des e motifs color´s . . . . . . . . . . . . . . . . . . . . . . e 4.1.3 Un algorithme de comptage exact . . . . . . . . . . . 4.1.4 La gestion des gaps . . . . . . . . . . . . . . . . . . . 4.2 Application de la recherche de motifs a l’´volution de voies ` e m´taboliques . . . . . . . . . . . . . . . . . . . . . . . . . . e 65 . 65 . 66 . 68 . 68 . 69 . 71 . 73 5 Inf´rence de motifs et sur-repr´sentation e e 77 5.1 Algorithme d’inf´rence . . . . . . . . . . . . . . . . . . . . . . 78 e 5.1.1 La version actuelle de l’algorithme d’inf´rence . . . . . 78 e 5.1.2 Temps d’ex´cution et limites actuelles . . . . . . . . . . 80 e 5.1.3 Vers un algorithme d’inf´rence . . . . . . . . . . . . . . 81 e 5.2 Analyse pr´liminaire et nombre de solutions . . . . . . . . . . 84 e 5.2.1 Le nombre de solutions . . . . . . . . . . . . . . . . . . 84 5.2.2 Le regroupement, le d´groupement ou le filtrage des e solutions, vers une autre d´finition de motif . . . . . . 86 e 5.2.3 L’interpr´tation des solutions - Contexte voies m´taboliques e e - Dessin de graphes . . . . . . . . . . . . . . . . . . . . 88 5.3 Statistiques dans les graphes . . . . . . . . . . . . . . . . . . 5.3.1 L’importance du mod`le de graphe al´atoire . . . . . e e 5.3.2 Diff´rents mod`les de graphe al´atoire . . . . . . . . e e e 5.3.2.1 Erd¨s-R´nyi . . . . . . . . . . . . . . . . . . o e 5.3.2.2 ERMG . . . . . . . . . . . . . . . . . . . . 5.3.2.3 Mod`le ` topologie fixe . . . . . . . . . . . . e a 5.3.3 La p-valeur sur le nombre de composantes connexes . 5.3.4 Limitations actuelles de notre m´thode . . . . . . . . e 5.3.4.1 Pr´cisions des estimations, nombre de simue lations a effectuer . . . . . . . . . . . . . . . ` 5.3.4.2 Motifs sur-repr´sent´s ` cause de motifs de e e a taille inf´rieure . . . . . . . . . . . . . . . . e . . . . . . . . 89 89 90 91 92 93 94 95 . 95 . 96 99 99 100 101 104 106 110 110 113 116 117 123 6 Applications de l’inf´rence de motifs e 6.1 Pr´sentation des donn´es et du pr´traitement . . . . . . . . . e e e 6.2 Analyse syst´matique des motifs . . . . . . . . . . . . . . . . . e 6.2.1 Analyse des motifs exacts . . . . . . . . . . . . . . . . 6.2.2 Analyse de motifs approch´s, au seuil 3 . . . . . . . . . e 6.2.2.1 Motif approch´ de taille 3 . . . . . . . . . . . e 6.2.2.2 Motif approch´ de taille 4 . . . . . . . . . . . e 6.2.2.3 Motifs approch´s de taille 5 et 6 . . . . . . . . e 6.2.2.4 Motifs approch´s de taille 7 . . . . . . . . . . e 6.2.3 Conclusion sur les motifs approch´s et l’analyse syst´mae e tique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Comparaison entre motifs et op´rons . . . . . . . . . . . . . . e 6.4 Lien entre topologie des r´seaux m´taboliques et expression e e des enzymes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 MOTUS 7.1 Traitement des donn´es . e 7.2 Mode recherche . . . . . 7.3 Mode inf´rence . . . . . e 7.4 Mode visualisation . . . Conclusions et perspectives ´ e A El´ments de base sur le m´tabolisme e ´e B El´ments de base sur la complexit´ algorithmique e C Articles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 . 126 . 126 . 127 . 129 131 147 149 151 Introduction L’identification du support de l’h´r´dit´ (la mol´cule d’ADN) a marqu´ ee e e e un tournant d´cisif dans l’histoire de la biologie ouvrant les portes au d´velope e pement de la biologie mol´culaire. Plus r´cemment, le s´quen¸age de g´nomes e e e c e complets a permis d’acc´l´rer significativement le processus de d´tection ee e et d’annotation des g`nes encod´s dans l’ADN. Mais cette d´marche (dite e e e r´ductionniste) qui consiste a identifier chaque g`ne dans un organisme pr´sente e ` e e des limites. Un organisme vivant ne peut ˆtre r´duit ` la liste de ses g`nes. e e a e En effet, il ne suffit pas qu’un g`ne soit contenu dans un g´nome pour e e conf´rer une capacit´ ` un individu. La relation entre g´notype (ensemble des e ea e g`nes) et ph´notype (ensemble des caract`res observ´s) est beaucoup plus e e e e complexe. Une des voies qui se d´veloppe actuellement pour expliquer ce lien e est l’´tude syst´matique des interactions entre les mol´cules pr´sentes dans e e e e une cellule (g`nes, prot´ines, petites mol´cules). Ces interactions peuvent e e e ˆtre directes (interactions physiques de prot´ines) ou indirectes (un facteur e e de transcription r´gule un autre g`ne en se fixant en amont de la s´quence e e e codante, ou deux enzymes catalysent des ´tapes cons´cutives dans une voie e e m´tabolique). Si on consid`re toutes ces interactions ensemble, on parle de e e r´seau d’interaction. L’id´e est que chaque g`ne n’est plus isol´ dans un coin e e e e de la cellule mais au centre d’un complexe r´seau d’interaction et c’est en e comprenant mieux ces interactions qu’on parviendra a mieux comprendre la ` fonction de ce g`ne et son influence sur le ph´notype. e e Dans ce contexte, la recherche de motifs dans un r´seau d’interaction e mol´culaire a pour but d’identifier des parties importantes de ce grand r´seau. e e La recherche de motifs correspond a la recherche d’´l´ments r´p´t´s au sein ` ee e ee du r´seau. L’int´rˆt de trouver des ´l´ments r´p´t´s est de deux ordres : e ee ee e ee – D’un point de vue fonctionnel, on peut ainsi quantifier la redondance d’un r´seau. Plusieurs r´p´titions d’un motif peuvent correspondre a e e e ` plusieurs moyens de r´aliser une mˆme fonction. Si l’une des voies vient e e a e ` d´faillir, une voie de secours peut ˆtre utilis´e. e e – D’un point de vue ´volutif, on peut faire l’hypoth`se que les groupes e e de mol´cules d´tect´s comme similaires ont une origine ´volutive come e e e mune. Par le pass´, il n’y avait alors qu’un seul groupe de mol´cules e e qui accomplissait cette fonction. D´tecter des motifs dans un r´seau permet donc ` la fois d’obtenir des e e a informations sur le fonctionnement du r´seau mais aussi sur la fa¸on dont il e c 1
Identification de motifs dans les réseaux métaboliques - Page 1
Identification de motifs dans les réseaux métaboliques - Page 2
wobook
edilivre.com