Décompositions et Visualisations de graphes : applications aux données biologiques

Romain Yves Bourqui

Description

Sous la direction de Maylis Delest, David Auber
Thèse soutenue le 24 octobre 2008: Bordeaux 1
La quantité d’informations stockée dans les bases de données est en constante augmentation rendant ainsi nécessaire la mise au point de systémes d’analyse et de visualisation. Nous nous intéressons dans cette thèse aux données relationnelles et plus particulièrement aux données biologiques. Cette thèse s’oriente autour de trois axes principaux : tout d’abord, la décomposition de graphes en groupes d’éléments ”similaires” a?n de détecter d’éventuelles structures de communauté ; le deuxième aspect consiste à mettre en évidence ces structures dans un système de visualisation, et dans un dernier temps, nous nous intéressons à l’utilisabilité de l’un de ces systèmes de visualisation via une évaluation expérimentale. Les travaux de cette thèse ont été appliqués sur des données réelles provenant de deux domaines de la biologie : les réseaux métaboliques et les réseaux d’interactions génes- protéines.
-Visualisation de graphe
-Bioinformatique
-Evaluation
-Décomposition de graphe
The amount of information stored in databases is constantly increasing making necessary to develop systems for analysis and visualization. In this thesis, we are interested in relational data and in particular, in biological data. This thesis focuses on three main axes : ?rstly, the decomposition of graph into clusters of ”similar” elements in order to detect the community structures ; the second aspect is to highlight these structures in a visualization system; and thirdly, we are interested in the usability of one of these visualization systems through an experimental evaluation. The work presented in this thesis was applied on real data from two ?elds of biology : the metabolic networks and the gene-protein interaction networks.
-Graph visualization
-Graph decomposition
-Evaluation
-Bioinformatic
Source: http://www.theses.fr/2008BOR13630/document

Sujets

• Bio-informatique
• Évaluation

Informations

• Publié par: Thesee
• Nombre de lectures: 67
• Langue: Français
• Poids de l'ouvrage: 16 Mo

Extrait

oN d’ordre : 3630
`THESE
pr´esent´ee `a
´L’UNIVERSITE BORDEAUX I
´ ´ECOLE DOCTORALE DE MATHEMATIQUES ET INFORMATIQUE
par Romain BOURQUI
POUR OBTENIR LE GRADE DE
DOCTEUR
´ ´SPECIALITE : Informatique
D´ecomposition et Visualisation de
graphes : Applications aux Donn´ees
Biologiques
Soutenue le : 24 Octobre 2008
Apr`es avis de :
MMe. Pascale Kuntz-Cosperec Professeure Rapportrice
M. Alexandru Telea ... Professeur Rapporteur
Devant la Commission d’Examen compos´ee de :
´M. Eric Sopena ... Professeur ...... Pr´esident
MMe. Marie-France Sagot Directrice de Recheche Examinatrice invit´ee
MMe. Maylis Delest .. Professeure ..... Directrice de th`ese
M. David Auber ... Maˆıtre de Conf´erences Co-directeur de th`ese
- 2008 -D´ecomposition et Visualisation de graphes:
Applications aux Donn´ees Biologiques
Romain BourquiRemerciements
Mes remerciements s’adressent tout d’abord a` la r´egion Aquitaine pour avoir financ´e
mes travaux de th`ese ainsi qu’`a l’Universit´e Bordeaux 1 et au LaBRI pour m’avoir permis
delar´ealiserdansdebonnesconditions.Jesouhaiteensuiteremerciertouslesmembresde
monjurydeth`ese,PascaleKuntz-Cosperec,Marie-FranceSagot,EricSopenaetAlexandru
Teleapouravoiraccept´ederelireetpermisd’am´eliorerparleursremarquesmonmanuscrit
de th`ese.
Je tiens aussi a` remercier l’ensemble des membres du th`eme «Visualisation de grandes
masses de donn´ees» pour leurs qualit´es humaines ind´eniables, leur bonne humeur quoti-
dienneainsibiensuˆrqueleurhumoursans´egal(merciJean-Mi).Enparticulier,jevoudrais
remercier Maylis et David qui ont su me donner la chance de r´ealiser cette th`ese avec eux.
J’en profite pour signifier toute ma gratitude et mon amiti´e a` David pour le (bon) temps
qu’il m’a consacr´e et l’enthousiasme pour la recherche qu’il m’a transmis.
Je remercie d’autre part tous les membres de ma famille pour le soutien qu’ils m’ont
apport´e. Je remercie tout particuli`erement ma m`ere qui a toujours su nous pousser a`
donner le meilleur de nous-mˆemes. Je pense d’autre part a` mon d´efunt grand-p`ere Pierre
qui m’a donn´e sa passion pour la culture et la connaissance.
Je tiens enfin `a remercier mon amie Sabrina pour m’avoir support´e (dans tous les sens
du terme) notamment durant ces derniers mois. Son soutien moral ainsi que sa pr´esence
m’ont permis de surmonter nombre de difficult´es au cours de ces trois ann´ees.
iiis
ds
y

é
pli
M
ne
o
:
Field
A
mé
bst
D
r
Ke
act
w
:
r
:
:
f
:
e
:

u
-
R
ts
o
D´ecomposition et Visualisation de graphes : Applications aux Donn´ees
Biologiques
La quantit´e d’informations stock´ee dans les bases de donn´ees est en constante
augmentation rendant ainsi n´ecessaire la mise au point de syst`emes d’analyse et de vi-
sualisation. Nous nous int´eressons dans cette th`ese aux donn´ees relationnelles et plus
particuli`erement aux donn´ees biologiques. Cette th`ese s’oriente autour de trois axes prin-
cipaux : tout d’abord, la d´ecomposition de graphes en groupes d’´el´ements ”similaires”afin
de d´etecter d’´eventuelles structures de communaut´e; le deuxi`eme aspect consiste `a mettre
en´evidencecesstructuresdansunsyst`emedevisualisation,etdansunderniertemps,nous
nous int´eressons a` l’utilisabilit´e de l’un de ces syst`emes de visualisation via une´evaluation
exp´erimentale.
Les travaux de cette th`ese ont´et´e appliqu´es sur des donn´ees r´eelles provenant de deux
domaines de la biologie : les r´eseaux m´etaboliques et les r´eseaux d’interactions g`enes-
prot´eines.
Visualisationdegraphe,d´ecompositiondegraphe,´evaluation,bioinformatique
Informatique
Graph Clustering and Visualization : Application to Biological Data
Theamountof informationstoredindatabasesisconstantlyincreasingmaking
necessarytodevelopsystemsforanalysisandvisualization.Inthisthesis,weareinterested
in relational data and in particular, in biological data. This thesis focuses on three main
axes : firstly, the decomposition of graph into clusters of ”similar” elements in order to
detect the community structures; the second aspect is to highlight these structures in
a visualization system; and thirdly, we are interested in the usability of one of these
visualization systems through an experimental evaluation.
The work presented in this thesis was applied on real data from two fields of biology :
the metabolic networks and the gene-protein interaction networks.
Graph visualization, graph decomposition, evaluation, bioinformatic
Computer Science
iiiivTable des mati`eres
R´esum´e / Abstract iii
Table des mati`eres v
Table des figures xi
Liste des tableaux xxi
1 Introduction 1
1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Extraction, D´ecomposition et Filtrage . . . . . . . . . . . . . . . . . . . . 3
1.3 Plongement Visuel et Rendu . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Utilisation par l’expert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Mise en oeuvre d’un syst`eme de visualisation d’information . . . . . . . . 5
1.6 Organisation du m´emoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 D´efinitions et Notations 11
2.1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Dessin de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 R´eseaux biologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Autres d´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
vTable des mati`eres
3 D´ecomposition et Visualisation : Etat de l’art 23
3.1 D´ecomposition de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Qualit´e d’une d´ecomposition . . . . . . . . . . . . . . . . . . . . . 24
3.1.2 Approches divisives . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.3 Approches agglom´eratives . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.4 Approches topologiques . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Visualisation de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Algorithmes de dessin de graphe planaire . . . . . . . . . . . . . . 29
3.2.2 Algorithmes de dessin de graphe orient´e acyclique . . . . . . . . . 31
3.2.3 Algorithmes par analogie physique . . . . . . . . . . . . . . . . . . 33
3.2.4 Approches par ´echantillonnage et mod`ele de forces . . . . . . . . . 38
3.2.5 Approches bas´ees sur les matrices . . . . . . . . . . . . . . . . . . 40
3.2.6 Approches bas´ees sur le partitionnement . . . . . . . . . . . . . . . 42
3.3 Visualisation de graphe partitionn´e . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Visualisation de donn´ees biologiques : Cas particulier du m´etabolisme . . 49
3.4.1 Visualisation de voies m´etaboliques. . . . . . . . . . . . . . . . . . 50
3.4.2 Visualisation de r´eseaux m´etaboliques . . . . . . . . . . . . . . . . 52
4 D´ecomposition de graphe 55
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 D´ecomposition en composantes hautement connexes . . . . . . . . . . . . 58
4.3.1 D´ecompositions en composantes 2- et 3-connexes . . . . . . . . . . 59
4.3.2 D´ecomposition en composantes 4-connexes . . . . . . . . . . . . . 60
4.4 Evaluer la qualit´e d’une d´ecomposition chevauchante . . . . . . . . . . . . 62
4.4.1 Densit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.4.2 Modularit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.4.3 G´en´eralisation de MQ . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.5 Evaluation de la qualit´e de la d´ecomposition . . . . . . . . . . . . . . . . 64
4.5.1 Donn´ees et protocole . . . . . . . . . . . . . . . . . . . . . . . . . . 64
vi