Mise en correspondance multiple de données génomiques et post-génomiques : approches algorithmiques

L'alignement multiple de réseaux biologiques a pour objectif d'extraire des informations fonctionnelles des données haut-débit représentées sous forme de graphes. Ceci concerne, par exemple, les données d'interaction protéines-protéines, les données métaboliques ou même les données génomiques.

Cette thèse développe une approche générique et exacte d'alignement de réseaux biologiques. Dans un premier temps nous proposons un formalisme précis, qui s'appuie sur les notions de graphe de données stratifié et de multigraphe d'alignement, et qui définit les alignements multiples locaux en autorisant notamment un réglage de la conservation de la topologie entre les réseaux. Nous présentons ensuite un algorithme de construction et partitionnement à la volée du multigraphe d'alignement, qui permet de traiter de façon efficace l'alignement de nombreux réseaux biologiques. Dans un second temps, nous étendons ce formalisme dans le cas où des noeuds sont manquants sur certains réseaux. Nous détaillons les algorithmes associés, puis nous proposons différentes variantes adaptées à des problèmes biologiques spécifiques.