Modélisation de réseaux biologiques

Modélisation de réseaux biologiques

Les réseaux biologiques représentent chacun une vue partielle de l’activité moléculaire à l’intérieur de la cellule. Dans cette section nous allons décrire les principaux réseaux couramment étudiés en biologie. Pour chaque type de réseau nous présentons les différentes modélisations proposées en littérature.

Réseaux d’interaction protéine-protéine

Les réseaux d’interaction protéine-protéine (ou PPI, pour proteinprotein interaction) représentent les interactions physiques entre protéines au sein d’un organisme . Il existe des méthodes expérimentales, dites à haut débit, pour mettre en évidence ces interactions. Les méthodes à haut débits principalement utilisées sont d’une part la méthode double hybride [FS89, ICO+01], qui est est utilisée pour identifier les interactions entre deux protéines, et d’autre part la spectrométrie de masse [TSB+08] pour identifier les interactions entre plusieurs protéines. Il est important de noter que ces méthodes ne sont pas exactes, elles donnent parfois des interactions qui n’existent pas réellement, appelées faux positifs ; elles peuvent aussi manquer des interactions réelles (faux négatifs).

Modélisation. Les interactions entre paires de protéines identifiées par la méthode expérimentale double hybride sont modélisées par un graphe non-orienté dans lequel les sommets sont les protéines et les arêtes représentent leurs interactions [KGS04, Kla09, TGH09, SUS07, LLB+09, SLF06, KBS09, CG08, BML+05, DBVS09, NK07, ZZW+07, KYL+04, HMD06, GH09, ESU08, KGS05, BHMK+09, ZRBV09]. Étant donné que les méthodes expérimentales ne sont pas exactes, il est possible d’ajouter des pondérations sur les arêtes pour indiquer le degré de confiance en l’existence d’une interaction, la force d’interaction ou la probabilité d’avoir une telle interaction [FNS+06, TF09, SSRS06, SXB08b, JHM08, DSG+08]. Les interactions entre plusieurs protéines, comme celles cherchées par la méthode de spectrométrie de masse, sont modélisées par un hypergraphe ; une hyper-arête représente alors une interaction entre deux protéines ou plus [KGS04].

Réseaux métaboliques

Le métabolisme est généralement défini comme étant le processus à travers lequel les organismes vivants acquièrent et utilisent de l’énergie pour accomplir différentes tâches [LCTS08]. L’acquisition de l’énergie est un processus de synthèse organique appelé anabolisme, tandis que l’utilisation d’énergie est un processus de dégradation organique appelé catabolisme. L’anabolisme et le catabolisme sont réalisés par une succession des réactions transformant des substrats en produits. Certaines réactions sont spontanées (c’est-à-dire les substrats se transforment en produits sans catalyseur), mais la plupart nécessite la présence d’enzymes pour les catalyser. Une réaction est dite irréversible si elle s’effectue dans un seul sens. Par contre, une réaction réversible peut s’effectuer dans les deux sens : les substrats deviennent alors produits et inversement.

Étant donnée une réaction R, on note par sub(R) (resp. prod(R)) l’ensemble des substrats (resp. produits) de R. L’ensemble des composants de R est noté comp(R) (comp(R) = sub(R) ∪ prod(R)). Une réaction réversible R dont les substrats sont A et B et les produits sont C et D est représentée par l’équation suivante.

A + B ↔ C + D (1.1)

Une réaction irréversible R, transformant des substrats A et B en produits C et D, est notée par l’équation suivante.

A + B → C + D (1.2)

Si, de plus, la réaction R est catalysée par une enzyme E, l’équation est écrite comme suit.

A + B →ᴱ C + D (1.3)

Les réactions du métabolisme forment le réseau métabolique. Ce réseau est décomposé en ensemble des modules fonctionnels (des sousréseaux) appelés voies métaboliques (en anglais : metabolic pathways). Voir la Figure 1.2 qui montre la voie métabolique de dégradation d’éthylbenzène chez la bactérie Escherichia coli.

Modélisation. Il existe essentiellement quatre types de représentations [LCTS08] : graphe des composants (substrats et produits), graphe des réactions, graphe des enzymes et graphe biparti (composants vs réactions). Ces graphes peuvent être orientés ou non-orientés, l’orientation permettant de différencier les réactions irréversibles de celles qui sont réversibles.

Le graphe des composants [ELJ06, WR07]
Le graphe des composants est un graphe non-orienté dont les sommets correspondent aux composants (c’est-à-dire substrats et produits) et on met une arête entre deux composants A et B s’il existe une réaction dont l’un est substrat et l’autre est produit.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1 Concepts de base
1.1 Modélisation de réseaux biologiques
1.1.1 Réseaux d’interaction protéine-protéine
1.1.2 Réseaux métaboliques
1.1.3 Réseaux de régulation de la transcription des gènes
1.1.4 Réseaux physiques
1.1.5 Réseaux de transduction de signal
1.2 Éléments de théorie des graphes
1.2.1 Graphes non-orientés
1.2.2 Graphes orientés
1.3 Notions de complexité
1.3.1 Classes P et NP
1.3.2 Classe NPO
1.3.3 Comment contourner la NP-difficulté ?
1.3.4 Complexité paramétrée
2 Comparaison de réseaux biologiques Hétérogènes
2.1 Comparaison de réseaux homogènes (alignement de réseaux)
2.2 Comparaison de réseaux hétérogènes
2.3 Notre modèle
2.4 Raffinement du modèle
2.5 Étude de complexité du problème One-to-One SkewGraM
2.6 Deux algorithmes pour résoudre One-to-One SkewGraM
2.6.1 L’heuristique AL G OH
2.6.2 L’algorithme exact AL G OBB
2.7 Transformation d’une instance de SkewGraM vers une instance de One-to-One SkewGraM
2.8 Résultats expérimentaux
2.8.1 Données simulées
2.8.2 Données réelles biologiques
Conclusion
3 Décomposition d’un graphe orienté en DAGs
3.1 Décomposition de graphes
3.2 Formulation des problèmes
3.3 Partitionnement d’un graphe en DAGs
3.4 Couverture d’un graphe par DAGs
Conclusion
4 Orientation de graphes
4.1 État de l’art sur l’orientation de graphes
4.1.1 MGO et ses variantes
4.1.2 D’autres problèmes d’orientation de graphes
4.2 Notre contribution
4.3 Formulation des problèmes
4.4 Réduction aux graphes mixtes acycliques (MAGs)
4.5 Complexité du problème S-GO
4.5.1 Algorithmes polynomiaux
4.5.2 Résultats de difficulté
4.6 Complexité du problème MIN-D-GO
4.6.1 Algorithmes polynomiaux
4.6.2 Résultats de difficulté
Conclusion
Conclusion générale