Complex graphs in biology : problems, algorithms and evaluation

La biologie est une science des modèles. L’histoire de cette science montre que ces modèles sont associés à la capacité d’observation des systèmes vivants. Par exemple, l’essor de l’observation microscopique a abouti à considérer la cellule comme unité du vivant, tandis que les dernières avancées biotechnologiques proposent l’ADN comme composante fondamentale biologique. L’ADN, ou acide désoxyribonucléique, est une molécule qui contient le génome, c’est-à-dire toute l’information génétique, d’une espèce. En février 2018, la base de données GenBank contenait plus de deux cents millions de génomes  . Toutes ces données biologiques peuvent être modélisées sous la forme de séquences. Ces séquences sont ensuite étudiées dans le but de déterminer tous les gènes présents dans un organisme, c’est-à-dire toutes les régions du génome qui sont utilisées par une cellule pour synthétiser des constituants essentiels de l’organisme appelés des protéines. Toutefois, déterminer l’ensemble des gènes d’un organisme n’est pas suffisant pour comprendre le fonctionnement de celui-ci. Pour cela, il est en effet nécessaire d’étudier les interactions entre les différentes entités biologiques, comme les gènes ou les protéines, qui le composent [27, 63].

Ces réseaux d’interactions biologiques se modélisent intuitivement sous la forme de graphes, et non plus de séquences. Par exemple, dans le cadre des réseaux d’interaction protéine protéine (appelés réseaux PPI, pour “Protein-Protein Interaction”), les sommets représentent des protéines et les arêtes des interactions physiques entre ces protéines. De même, les réseaux métaboliques sont utilisés pour représenter le métabolisme d’un organisme, c’est-à-dire l’ensemble des réactions chimiques effectuées au sein de cet organisme pour assurer son fonctionnement. Ces réseaux métaboliques sont constitués de métabolites, des molécules issues du métabolisme, ainsi que de ces réactions, qui prennent en entrée un ensemble de métabolites afin d’en produire un nouveau. Ainsi, dans le graphe des réactions d’un réseau métabolique, les sommets correspondent aux réactions, et deux sommets sont incidents s’il existe un métabolite commun parmi les métabolites de sortie de la réaction associée au premier sommet et les métabolites d’entrée de la réaction associée au deuxième sommet.

Les sommets des graphes représentant des réseaux biologiques peuvent également être colorés. Dans ce cas, la couleur d’un sommet donne une information supplémentaire sur la nature de l’entité biologique associée à celui-ci. Par exemple, si un graphe représente un réseau PPI, alors on peut colorer les sommets relativement à la fonction de la protéine qui leur est associée.

Définitions des propriétés d’un graphe

Les graphes sont des objets mathématiques utilisés pour représenter des interactions entre des entités. Leur première utilisation connue remonte en 1735 quand le mathématicien suisse Leonhard Euler a résolu le problème des sept ponts de Königsberg [49]. Dans ce problème, un fleuve sépare la ville de Königsberg (maintenant Kaliningrad) en quatre parties, qui sont reliées par sept ponts (voir la partie gauche de la Figure 1.1). Le but du problème est de déterminer s’il existe un chemin qui traverse chaque pont une et une seule fois, et dont la position d’arrivée est la même que celle de départ. Dans les paragraphes suivants, on utilise ce problème pour illustrer des notions clefs communément utilisées en théorie des graphes. Un graphe G = (V, E) est défini par un ensemble V d’entités, appelés des sommets, ainsi que par un ensemble E d’arêtes, qui relient des paires de ces sommets. On utilise également la notation V (G) (resp. E(G)) pour décrire l’ensemble des sommets (resp. arêtes) de G, avec n = |V (G)| et m = |E(G)|. Dans le graphe créé par Euler pour résoudre le problème des sept ponts de Königsberg, chaque partie de la ville est associée à un sommet et chaque pont entre deux parties de la ville est représenté par une arête entre les deux sommets correspondants à ces parties. On peut voir une illustration de ce graphe dans la Figure 1.1. Une arête entre deux sommets u et v du graphe est notée (u, v). Dans la Figure 1.1, l’arête (A, C) représente le pont reliant la partie A de la ville à la partie C. On dit également que A et C sont les extrémités de l’arête (A, C) et que l’arête (A, C) est incidente aux sommets A et C. Par ailleurs, un graphe est dit simple s’il ne contient pas plusieurs arêtes entre une même paire de sommets et s’il ne contient aucune arête d’un sommet à lui-même.

Une couverture par les sommets d’un graphe G = (V, E) est un ensemble de sommets V 0 ⊆ V tel que chaque arête de E est incidente à au moins un sommet de V 0 . Par exemple, on observe que le sous-ensemble de sommets {C, D} est une couverture par les sommets du graphe G dans la Figure 1.1. On dit que deux sommets u et v appartenant à V sont adjacents, ou voisins, s’il existe une arête (u, v) ∈ E. Pour tout sommet v ∈ V , le voisinage de v, noté N(v) = {u ∈ V : (v, u) ∈ E}, est l’ensemble des  voisins de v dans G. On note d(v) = |N(v)| le degré d’un sommet v. S’il existe une arête reliant chaque paire de sommets de G, alors G est une clique. Un ensemble de sommets V 0 ⊆ V est indépendant s’il n’existe aucune paire de sommets v1 et v2 qui appartiennent à V 0 tels que v1 et v2 sont voisins dans G. Dans la Figure 1.1, l’ensemble de sommets V 0 = A, B est indépendant.

Un chemin τ dans G contient une liste ordonnée de sommets de V tel qu’il existe une arête appartenant à E entre chaque paire de sommets consécutifs de τ . Un cycle est un chemin dont le sommet de départ est le même que celui d’arrivée. Enfin, un chemin (resp. cycle) est dit simple s’il ne contient pas deux fois la même arête. Ainsi, dans la Figure 1.1, τ1 =< A, C, B > est un chemin, τ2 =< A, D, B, C, D, A > est un cycle qui n’est pas simple car il contient deux fois l’arête (A, D), τ3 =< A, C, D, A > est un cycle simple, et τ4 =< A, B, C > n’est ni un cycle ni même un chemin. La longueur d’un chemin (resp. d’un cycle) est égale à son nombre d’arêtes.

Un graphe est connexe s’il existe un chemin entre chaque paire de sommets qu’il contient. Dans notre exemple, le graphe construit est connexe puisqu’on peut accéder à n’importe quelle partie de la ville en traversant un ou plusieurs ponts selon notre position d’origine. Un graphe G0 = (V 0 , E0 ) est un sous-graphe de G = (V, E) si V 0 ⊆ V , si E 0 ⊆ E et si les extrémités de toutes les arêtes de E 0 appartiennent à V 0 . La relation G0 ⊆ G signifie que G0 est un sous-graphe de G. Dans la Figure 1.1, le graphe G0 = (V 0 , E0 ) avec V 0 = {A, C, D} et E 0 = {(A, D)} est un sous graphe de G qui n’est pas connexe. Pour tout V 0 ⊆ V , G[V 0 ] désigne le sous graphe induit de G pour lequel V (G[V 0 ]) = V 0 et E(G[V 0 ]) = {(u, v) ∈ E : (u ∈ V 0) ∧ (v ∈ V 0 )} . En d’autres termes, E(G[V 0 ]) contient toutes les arêtes de E dont les deux extrémités appartiennent à V’ .

Problèmes et algorithmes 

On commence par définir les deux types de problèmes qui seront étudiés dans ce manuscrit : les problèmes de décision et les problèmes d’optimisation. On montre ensuite les relations entre ces deux types de problèmes, avant d’aborder les notions d’algorithme et surtout de complexité d’un algorithme.

On définit un problème de décision par des données d’entrées, dont l’ensemble constitue une instance, ainsi que par une question sur cette instance. Pour ce type de problèmes, la réponse à la question posée est soit “oui” (l’instance est appelée une YES-instance), soit “non” (l’instance est appelée une NO-instance). On donne un exemple de problème de décision avec le problème k-CYCLE ci-dessous.

k-CYCLE
• Instance: Un graphe G = (V, E), un entier k
• Question: Existe-t-il un cycle simple C de longueur supérieure ou égale à k dans G?

Un problème d’optimisation est défini par une instance et une solution à donner en sortie qui doit être la “meilleure” solution contenue dans l’instance par rapport à un critère de mesure. Cette mesure doit soit être maximisée (problème de maximisation) ou minimisée (problème de minimisation) ; les noms des problèmes étudiés dans ce manuscrit sont assez explicites pour ne pas avoir à préciser si un problème d’optimisation est un problème de maximisation ou de minimisation. On donne un exemple de problème d’optimisation avec le problème LONGEST CYCLE ci-dessous.

LONGEST CYCLE
• Instance: Un graphe G = (V, E)
• Sortie: Un cycle simple C de longueur k ∈ N
• Mesure: k

On observe que les problèmes k-CYCLE et LONGEST CYCLE permettent tous les deux de répondre au problème des ponts de Königsberg qui est présenté dans la Section 1.1.1. En effet, un graphe G = (V, E) contient un cycle eulérien si la réponse à k-CYCLE avec k = |E| est “oui”, ou bien si k est au moins égal à |E| dans la solution donnée en sortie de LONGEST CYCLE. En règle générale, on peut facilement transformer un problème de décision (resp. d’optimisation) Q en problème d’optimisation Q0 (resp. de décision) ; on appelle Q0 la version optimisation (resp. décision) de Q. Dans ce manuscrit, tous les problèmes dont le nom commence par “k-” sont des problèmes de décision.

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 rapport-gratuit.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 Généralités algorithmiques
1.1 Théorie des graphes
1.1.1 Définitions des propriétés d’un graphe
1.1.2 Exemples de classes de graphes
1.1.3 Graphes orientés
1.1.4 Décomposition arborescente d’un graphe
1.2 Théorie de la complexité
1.2.1 Problèmes et algorithmes
1.2.2 Les classes P et NP
1.2.3 La classe APX
1.2.4 Les classes FPT, W[1], W[2] et XP
1.3 Quelques techniques pour obtenir des algorithmes FPT
1.3.1 Algorithme de branchement
1.3.2 Programmation dynamique
1.3.3 Le color-coding et ses améliorations
1.3.4 Recherche de noyau
1.4 Conclusion
2 Le problème GRAPH MOTIF et ses variantes
2.1 Motivations et modélisation de GRAPH MOTIF
2.2 Présentation de quelques variantes de GRAPH MOTIF
2.2.1 Suppression des répétitions de couleurs dans le motif
2.2.2 Maximisation de la cardinalité d’une sous-occurrence du motif
2.2.3 Ajout d’une fonction de pondération sur les arêtes
2.3 Caractérisation des instances difficiles
2.4 Résultats de complexité paramétrée
2.4.1 Paramétrer par la taille du motif
2.4.2 Paramétrer par le dual
2.5 Liste de logiciels pour résoudre GRAPH MOTIF
2.6 Conclusion
3 Le problème MAXIMUM COLORFUL ARBORESCENCE : caractérisation des instances difficiles
3.1 Le problème MAXIMUM COLORFUL ARBORESCENCE
3.2 Résultats de complexité en fonction de la nature du graphe d’entrée et du graphe de hiérarchie de couleurs
3.2.1 Résultats de complexité quand le graphe d’entrée est un arbre
3.2.2 Résultats de complexité quand le graphe d’entrée est un comb-graph
3.2.3 Résultats de complexité quand le graphe d’entrée est une superstar
3.2.4 Résultats de complexité quand le graphe d’entrée est un caterpillar
3.2.5 Résultat de complexité quand le graphe de hiérarchie de couleurs est un arbre
3.3 Conclusion
4 Résultats de complexité paramétrée pour MAXIMUM COLORFUL ARBORESCENCE
4.1 Motivations et introduction des paramètres étudiés
4.2 Résultats théoriques
4.2.1 Etude de MCA en fonction du nombre `C de répétitions de couleurs dans G
4.2.2 Etude de MCA en fonction des couleurs difficiles de H
4.2.3 Etude de MCA en fonction de la treewidth de H
4.3 Expérimentations
4.3.1 Présentation des instances
4.3.2 Analyse des résultats
4.4 Conclusion
Conclusion

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.