Etude algorithmique d'un problème de comparaison de réseaux biologiques

Un réseau biologique est une représentation abstraite d'un système biologique. L'objectif principal de la modélisation par des réseaux est d'étudier les relations entre les composants de ces réseaux pour analyser ou prédire des fonctions biologiques. Les études récentes montrent qu'un système biologique ne peut être compris en se basant uniquement sur la fonction de chacun de ses composants, beaucoup des fonctions étant réalisées par un groupe de composants (par exemple les complexes des protéines, les opérons,

etc.). Il existe essentiellement deux types de comparaison : comparaison de réseaux homogènes et comparaison de réseaux hétérogènes. Dans le premier cas, on compare des réseaux de même type, ce qui conduit généralement à un problème d'alignement des graphes. Par contre, le second cas concerne la comparaison de réseaux de types différents et donc représentés par  des graphes qui ne sont pas de même nature (par exemple graphe orienté vs graphe non-orienté). Nous introduisons et étudions un problème algorithmique d’optimisation combinatoire  nommé One-to-One SkewGraM issu la comparaison de réseaux hétérogènes. Nous montrons que le problème est NP-Complet tout en identifiant la frontière entre les instances faciles et les instances difficiles. Nous proposons  également une heuristique que nous appliquons sur des instances réelles et des instances simulées.