Soutenance mémoire
Contrairement aux prédictions effectuées il y a quelques années, le nombre de gènes chez l’homme ne serait que de 25.000 [Cla05]. Si, par exemple, ce nombre est comparé aux 45.000 gènes du riz, il est légitime de supposer que la relative complexité d’un organisme n’est pas directement liée à son nombre de gènes, tout du moins pas de façon linéaire. En effet, lister les gènes présents dans un organisme est parfois discutable, car il ne suffit pas de relever la présence d’un gène dans une cellule pour que le caractère correspondant soit automatiquement exprimé. L’une des méthodes utilisées pour mieux comprendre les liens complexes entre le génotype (ensemble des gènes relevés chez un individu) et le phénotype (ensemble des caractères observés chez un individu) consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites…). Celles-ci forment ce qui est appelé un réseau biologique. Leur utilisation permet la réponse à de nouvelles problématiques. Les réseaux principalement utilisés dans cette thèse sont les réseaux d’interactions entre protéines ainsi que les réseaux métaboliques.
De manière algorithmique, nous représentons un réseau biologique par un graphe, où les sommets représentent les éléments biologiques, et où les arêtes représentent les interactions entre les éléments correspondants. Ce graphe est, de plus, coloré sur les sommets. La couleur représente alors une certaine propriété biologique de l’élément (une classe de protéines, une classe de réactions…). Un problème largement étudié dans la littérature consiste à déterminer si une certaine requête, représentée par un chemin, un arbre ou un graphe, est présente dans le graphe représentant le réseau biologique. Ce problème, analogue à celui de la recherche de motif dans un texte ou de requête dans une base de données, est fondamental en biologie. Il permet en effet d’identifier les parties importantes d’un grand réseau ou encore de découvrir des fonctions communes entre différentes espèces. Cependant, ce type de problème est rapidement difficile algorithmiquement puisqu’il est proche des problèmes de morphismes de graphes.
Récemment, Lacroix, Fernandes et Sagot ont introduit une variante du problème de requête dans un réseau biologique, avec un problème appelé GRAPH MOTIF [LFS06]. Il a été montré que la topologie des requêtes était parfois inconnue ou tout simplement non pertinente. Par conséquent, dans ce nouveau formalisme, la requête (ou le motif) est seulement un multi-ensemble de couleurs. Le problème consiste alors à déterminer s’il existe un sous-graphe connexe, contenant toutes les couleurs du motif . L’approche choisie est plus fonctionnelle que topologique.
Généralités algorithmiques
Graphes
Nous introduisons ici seulement quelques bases sur les graphes. D’autres définitions importantes seront données tout au long de ce document, lorsqu’elles seront nécessaires. Le lecteur désirant plus de détails pourra se référer par exemple au livre de Reinhard Diestel [Die05]. Le graphe est un objet abondamment utilisé en pratique, dans des domaines divers et variés. La théorie sous-jacente à leur étude, la théorie des graphes, est également largement étudiée. La terminologie utilisée est agréablement intuitive. Ainsi, la plupart des termes employés sont explicites et se retiennent assez facilement. Un graphe G = (V, E) est constitué d’un ensemble V (de l’anglais vertices) de sommets (ou nœuds) ainsi que d’un ensemble E ⊆ V ×V (de l’anglais edges) de paires de sommets, nommées arêtes. Dans la suite, les graphes sont considérés sans boucle, c’est-à-dire sans arête de la forme {u, u}. Des graphes se trouvent dans de nombreuses applications. Un graphe peut représenter le réseau Internet, des réseaux biologiques, le réseau des connaissances entre citoyens, des réseaux de communications, des planifications de tâches… Nous avons choisi d’illustrer les notions de cette section à l’aide du réseau du métro de Paris 1 . Nous pouvons en effet représenter formellement ce réseau à l’aide d’un graphe, où chaque station est un sommet, et où une voie ferrée reliant deux stations est représentée par une arête.
En toute généralité, les voies ferrées entre les stations permettent une circulation dans les deux sens. Le graphe alors associé est donc dit non-orienté, car il contient des arêtes. Une arête entre deux sommets u et v est notée comme un ensemble à deux éléments {u, v}. Le graphe représentant le réseau du métro (Figure 1.1) est non-orienté. Nous pouvons cependant désirer donner une orientation à ces liens entre deux sommets. Par exemple, les trains ne circulent que dans un seul sens entre les stations Pré St-Gervais et Botzaris sur la ligne 7bis (voir Figure 1.2). Nous parlons alors d’arc plutôt que d’arête. L’ensemble des arcs d’un graphe est noté A (de l’anglais Arcs) et est également constitué d’un ensemble de paires de sommets, c’est-à-dire A ⊆ V ×V . Un arc entre deux sommets u et v est noté (u, v) si l’orientation est de u vers v, et (v, u) sinon. Un graphe G = (V, A) contenant uniquement des arcs est dit orienté. Nous manipulerons dans la suite de cette thèse essentiellement des graphes non-orientés. Ainsi, il faudra considérer les graphes comme tels lorsque aucune précision ne sera donnée. Dans la majorité des cas, E et A sont des ensembles simples, c’est-à-dire sans répétition. Dans le cas contraire, ce sont des multi-ensembles, où plusieurs liens entre deux sommets sont possibles et de la notion de multi-graphe associée. C’est par exemple le cas dans le graphe du métro Figure 1.1 où l’on trouve deux arêtes reliant les stations Gare du Nord et Gare de l’Est. La taille d’un graphe, lorsque aucune précision ne sera donnée, fera référence à son nombre de sommets, c’est-à-dire à |V |, souvent noté n. Les graphes peuvent être pondérés. Une fonction de poids est alors ajoutée aux arêtes (ou arcs), y associant un nombre, souvent réel, c’est-à-dire G = (V, E, w), où w est une fonction telle que w : E → R. Autrement dit, pour chaque arête e ∈ E, la valeur w(e) donne le poids de l’arête. Le graphe du métro Figure 1.1 peut être pondéré par la distance entre les stations.
Deux sommets u et v de V sont dits voisins (ou adjacents) si e = {u, v} ∈ E, les sommets u et v sont alors incidents à l’arête e. Au contraire, u et v sont dits indépendants si {u, v} ∈/ E. Dans le graphe du métro Figure 1.1, les stations Père Lachaise et Gambetta sont voisines, en revanche, les stations Gambetta et Gare de l’Est sont indépendantes. Ces notions sont identiques dans un graphe orienté, en remplaçant les arcs orientés par une arête non orientée. Ainsi, deux sommets sont voisins quel que soit le sens de l’arc les reliant. L’ensemble des voisins d’un sommet u ∈ V , noté N(u), est constitué des sommets partageant une arête avec u :
N(u) = {v : {u, v} ∈ E}.
Le nombre de ces voisins est appelé degré de u, noté d(u) :
d(u) = |N(u)|.
Un chemin est une séquence de sommets telle que chaque sommet possède une arête avec le sommet suivant de la séquence. Plus formellement, un chemin à n sommets est noté Pn = (u1, u2, . . . , un), où l’arête {ui , ui+1} ∈ E pour 1 ≤ i ≤ n − 1. Attention, la longueur d’un chemin fait référence à son nombre d’arêtes. Un chemin où chaque sommet n’apparaît qu’une seule fois dans la séquence (absence de boucle) est appelé chemin simple. Ceci implique que ui 6= uj , 1 ≤ i < j ≤ n. Le sous-graphe du graphe du métro induit par les sommets {Ménilmontant, Couronnes, Belleville, Goncourt, République, Parmentier} est un chemin simple à 6 sommets, de longueur 5. Un cycle est un chemin où le premier et le dernier sommet de la séquence sont confondus, c’est-à-dire un = u1. Le sous-graphe du graphe du métro induit par les sommets {Ménilmontant, Couronnes, Belleville, Goncourt, République, Parmentier, Rue St-Maur, Père Lachaise, Ménilmontant} est un cycle. Un graphe non-orienté est dit connexe s’il existe un chemin entre chaque paire de sommets du graphe. Par exemple, le graphe du métro Figure 1.1 n’est pas connexe car il existe au moins deux sommets (par exemple Châtelet et une des stations du funiculaire de Montmartre) sans chemin les reliant. En revanche, le graphe Figure 1.3 est connexe. Une composante connexe d’un graphe G est un sous-graphe maximal connexe de G. Le graphe du métro Figure 1.1 contient deux composantes connexes, celle composée des deux stations du funiculaire de Montmartre et celle contenant toutes les autres stations.
C’est certainement le mathématicien suisse Leonhard Euler (1707 – 1783) qui a introduit le premier la notion de graphe. En effet, en 1736, dans un article en latin ([Eul36], traduction en anglais dans [BLW86]) reprenant la démonstration faite l’année précédente devant les membres de l’Académie de SaintPétersbourg, il résout un problème populaire concernant les ponts de la ville prussienne de Königsberg (maintenant Kaliningrad en Russie). En effet, cette ville est construite autour de deux îles, et reliée à ces dernières via 7 ponts comme illustré ci-dessous. L’histoire raconte que les habitants ont longtemps essayé de trouver une route traversant tous les ponts exactement une seule fois. Euler a montré qu’une telle route n’existait pas. En effet, le (multi)graphe associé à cette configuration (illustré à droite du schéma ci-dessous), où chaque rive est un sommet et où chaque pont est une arête, contient plus de deux sommets de degré impair. Or, une telle route n’existe que si au plus deux sommets ont un degré impair. Si un graphe admet un chemin passant par chaque sommet du graphe et revenant au point de départ, il est dit Eulérien, en l’honneur d’Euler. Chaque sommet doit alors avoir un degré pair. Ceci se comprend intuitivement : pour chaque sommet, il faut pouvoir y arriver et en repartir .
|
Table des matières
Introduction
I Quelques bases
1 Généralités algorithmiques
1.1 Graphes
1.2 Problèmes et algorithmes
1.2.1 Classification et analyse d’algorithmes
1.2.2 Classification de problèmes
1.3 Contourner la NP-Complétude
1.3.1 Analyser des sous-problèmes
1.3.2 La complexité paramétrée
1.3.3 Recherche de noyaux
1.3.4 Algorithmes d’approximation
1.3.5 Heuristiques
1.3.6 Programmation linéaire
1.3.7 Algorithmes exponentiels exacts
2 Quelques notions de biologie
2.1 Le dogme central de la biologie moléculaire
2.1.1 L’ADN
2.1.2 L’ARN
2.1.3 Les protéines
2.1.4 Les gènes
2.2 Les réseaux biologiques
2.2.1 Généralités
2.2.2 Trois réseaux biologiques d’interactions moléculaires
2.2.3 Obtention, stockage et qualité des données
2.2.4 Topologie des réseaux
2.2.5 Évolutions des réseaux
II Algorithmique des réseaux biologiques
3 Problèmes algorithmiques des réseaux biologiques
3.1 Des motivations biologiques
3.2 …et les questions algorithmiques sous-jacentes
3.2.1 L’alignement de plusieurs réseaux
3.2.2 L’intégration de plusieurs réseaux
3.2.3 La recherche de sous-réseaux
4 Recherche exacte de motifs
4.1 Motivations et définition
4.2 Complexité classique
4.3 Complexité paramétrée
4.3.1 Avec un motif colorful
4.3.2 Avec multi-ensemble comme motif
4.4 Recherche de noyaux
4.5 Compter les motifs
5 Vers une définition plus souple de GRAPH MOTIF
5.1 Résultats de complexité paramétrée
5.1.1 Quand des insertions et des délétions sont autorisées
5.1.2 Quand un ensemble de couleurs est associé aux sommets du graphe
5.1.3 Quand un poids est associé aux arêtes du graphe
5.2 Résultats d’approximation
5.2.1 Maximiser la taille de la solution
5.2.2 Minimiser le nombre de substitutions
5.3 Utilisation de modules pour GRAPH MOTIF
5.3.1 Définitions autour des modules
5.3.2 Quand les modules rejoignent GRAPH MOTIF
5.3.3 Difficulté du problème
5.3.4 Des algorithmes pour le problème de décision
5.3.5 Problèmes ouverts et discussions
6 Implémentations et évaluations
6.1 GraMoFoNe, un greffon Cytoscape
6.1.1 Méthodes et implémentation
6.1.2 Fonctionnalités
6.2 Évaluation pratique et comparaisons
6.2.1 Acquisition des données
6.2.2 Paramètres
6.2.3 Expérimentations
6.2.4 Comparaison avec les travaux relatifs
7 Comparaison de réseaux hétérogènes
7.1 Motivations et définitions
7.2 Résultats de complexité
7.3 Ajouter une contrainte de connexité sur les DAG
III Génomique comparative et structure secondaire d’ARN
8 Génomique Comparative
8.1 La mosaïque minimum
8.1.1 Motivations et définitions
8.1.2 Résultats connus
8.1.3 Contributions
8.2 Comparaison de génomes avec duplications
8.2.1 Motivations et définitions
8.2.2 Résultats connus
8.2.3 Contributions
8.3 Intervalles communs de génomes
8.3.1 Motivations
8.3.2 Résultats connus
8.3.3 Contributions
8.4 Minimiser les duplications de gènes
8.4.1 Motivations et définitions
8.4.2 Résultats connus
8.4.3 Contributions
9 Comparaison de structures secondaires d’ARN
9.1 Motivations et définitions
9.2 Résultats connus
9.3 Contributions
Conclusion
