Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Comparaison de réseaux biologiques : Graphe orienté vs Graphe non-orienté
Hafedh Mohamed Babou

21 March 2013, 14h00
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche :

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 ce travail, 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.

Enfin, pour montrer l'efficacité de notre heuristique, nous l'appliquerons sur des données simulées et sur des données biologiques réelles.

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

Pour en savoir plus :
Séminaires
Some recent results on the integer linear programm
Théorie des graphes
Friday 12 October 2018 - 14h30
Salle : 445 - PCRI-N
Hung Nguyen .............................................

Maximum Independent Set in H-free graphs
Théorie des graphes
Friday 05 October 2018 - 14h30
Salle : 445 - PCRI-N
Edouard BONNET .............................................

A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 29 June 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Distributionally Robust Optimization with Principa
Optimisation combinatoire et stochastique
Friday 29 June 2018 - 11h00
Salle : 455 - PCRI-N
Dr. Jianqiang Cheng .............................................