Alignement Multiple de Données Génomiques et Post-Génomiques : Approches Algorithmiques

Multiple alignment of biological networks is used to extract functional information from high-throughput data represented by graphs. This data can be protein-protein interactions, metabolic pathways or even the gene layout on a chromosome. We start by giving a precise formalism, based on the notions of layered datagraph and alignment multigraph (MGA), which defines local multiple alignments in the datagraph, allowing for example the tuning of the topology conservation between networks. Next, we present a new algorithm that builds and partitions the MGA ''on the fly", which allows us to deal with alignment of numerous biological networks. In a second part, we extend the formalism to be able to recover alignments - which we call ''partial" - when there are missing nodes on some networks. We explain the algorithms we have designed to compute those alignments, and then we give some improvements and some variants tailored to deal with specific biological problems.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. 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 (MGA), 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 MGA, qui permet de traiter de façon efficace l'alignement de nombreux réseaux biologiques. Dans un second temps, nous étendons le formalisme pour parvenir à retrouver des alignements - que nous qualifions de ''partiels" - lorsqu'il y a des noeuds manquants sur certains réseaux. Nous détaillons les algorithmes associés, puis nous proposons différentes améliorations, et des variantes adaptées à des problèmes biologiques particuliers