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.