Langues : English français
Accueil > Manifestations > Thèses et HDR > Thèses > Hafedh Mohamed Babou

Hafedh Mohamed Babou

Directeur de thèse

Irena Rusu
Guillaume Fertin

Résumé

La comparaison de réseaux biologiques est actuellement l’une des
approches les plus prometteuses pour aider à la compréhension du
fonctionnement des organismes vivants. Elle apparaît comme la suite
attendue de la comparaison de séquences biologiques dont l’étude ne
représente en réalité que l’aspect génomique des informations manipulées
par les biologistes.

Dans cette thèse, nous proposons une approche innovante permettant de
comparer deux réseaux biologiques modélisés respectivement par un graphe
orienté D et un graphe non-orienté G, et dotés d’une fonction f
établissant la correspondance entre les sommets des deux graphes.
L’approche consiste à extraire automatiquement une structure dans D,
biologiquement significative, dont les sommets induisent dans G, par f,
une structure qui soit aussi biologiquement significative.

Nous réalisons une étude algorithmique du problème issu de notre approche
en commençant par sa version dans laquelle D est acyclique (DAG). Nous
proposons des algorithmes polynomiaux pour certains cas, et nous montrons
que d’autres cas sont algorithmiquement difficiles (NP-complets). Pour
résoudre les instances difficiles, nous proposons une bonne heuristique et
un algorithme exact basé sur la méthode branch-and-bound. Pour traiter le
cas où D est cyclique, nous introduisons une méthode motivée par des
hypothèses biologiques et consistant à décomposer D en DAGs tels que les
sommets de chaque DAG induisent dans G un sous-graphe connexe. Nous
étudions également dans cette thèse, l’inférence des voies de
signalisation en combinant les informations sur les causes et sur les
effets des événements extra-cellulaires. Nous modélisons ce problème par
un problème d’orientation de graphes mixtes et nous effectuons une étude
de complexité permettant d’identifier les instances faciles et celles
difficiles.


Mots clés :
Réseaux hétérogènes, Biologie computationnelle, NP-difficulté,
APX-difficulté, Complexité paramétrée, Heuristiques, Branch-and-Bound.

Abstract

Comparison of biological networks

The comparison of biological networks is now one of the most
promising approaches that help in understanding the functioning of
living organisms. It appears as the expected continuation of the
comparison of biological sequences, whose study represents in reality only
the genomic aspect of the information manipulated by biologists.

In this thesis, we propose an innovative approach allowing to compare two
biological networks modeled respectively by a directed graph D and an
undirected graph G, and provided with a correspondence function f between
the vertices of both graphs. The approach consists in extracting
automatically a biologically significant structure in D whose vertices
induce in G a biologically significant structure as well. We realize an
algorithmic study of the problem arising in our approach by starting with
its variant in which D is acyclic (DAG).

We provide polynomial algorithms for several cases and we show that other
cases are algorithmically difficult (NP-completes). In order to solve the
difficult instances, we propose a reliable heuristic and an exact
algorithm based on the
branch-and-bound method. To deal with the case where D is cyclic, we
introduce a method motivated by biological hypotheses and consisting in
decomposing D into DAGs such that the vertices of each DAG induce in G a
connected subgraph. We also study in this thesis, the problem of signaling
pathways inference by combining the information on causes and effects of
extra-cellular events. We model this problem by a problem of mixed
graphs orientation and we perform a complexity study allowing to identify
the easy and the
difficult instances.


Keywords :
Heterogeneous networks, Computational biology, NP-hardness,
APX-hardness, Parametrized complexity, Heuristics, Branch-and-Bound.

Composition du jury

  • Dominique Barth, Professeur - Université de Versailles (Rapporteur)
  • Ioan Todinca, Professeur - Université d’Orléans (Rapporteur)
  • Thierry Lecroq, Professeur - Université de Rouen (Examinateur)
  • Stéphane Vialette, Directeur de recherche CNRS - Université Paris-Est (Examinateur)
  • Irena Rusu, Professeur – Université de Nantes (Directrice de thèse)
  • Guillaume Fertin, Professeur – Université de Nantes (Co-encadrant de thèse)

Dernière modification : vendredi 26 octobre 2012