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.

L'alignement multiple est une opération permettant de mettre en évidence la similarité entre plusieurs séquences. Il est notamment utilisé pour la reconstruction de phylogénies, la recherche de motifs et la prédiction de structures. Cette thèse s'intéresse au développement de nouveaux algorithmes pour ce problème particulièrement difficile, et introduit deux algorithmes progressifs ayant pour point commun de réaliser un alignement multiple par alignements successifs de groupes de séquences.<br />Le premier algorithme, Plasma utilise une méthode de descente, dont chaque itération consiste à réaliser des insertions de colonnes de brèches dans deux alignements multiples à aligner. Le second algorithme, Plasma II , est basé sur le principe de la programmation dynamique. Nous généralisons ici l'algorithme utilisé pour l'alignement de deux séquences, et étendons le cadre de la programmation dynamique `a l'alignement de deux alignements multiples. Cet algorithme ainsi que plusieurs variantes sont intensivement évalués sur les jeux d'essais de Balibase, montrant des résultats encourageants, voire compétitifs, par rapport à certains algorithmes de référence comme Clustal W, tant sur la qualité de l'alignement que sur le temps de calcul.

Cette thèse propose une nouvelle approche de découverte de signatures de familles de protéines. Etant donné un échantillon (non-aligné) de séquences appartenant à une famille structurelle ou fonctionnelle de protéines, cette approche infère des automates fini s non déterministes (NFA) caractérisant la famille.<br>Un nouveau type d'alignement multiple nommé PLMA est introduit afin de mettre en valeur les similarités partielles et locales significativement similaires. A partir de ces informations, les modèles de type NFA sont produits par un procédé relevant du domaine de l'inférence grammaticale. Les modèles NFA, présentés ici sous le nom de Protomates, sont des modèles graphiques discrets de forte expressivité, ce qui les distingue des modèles statistiques de type profils HMM ou des motifs de type Prosite.<br>Les expériences menées sur différentes familles biologiques dont les MIP et les TNF, montrent un succès sur des données réelles.

J'ai mis au point une méthodologie pour annoter les superfamilles d'enzymes, en décrire l'histoire et les replacer dans l'évolution de leurs voies métaboliques. J'en ai étudié trois : (1) les amidohydrolases cycliques, dont les DHOases (dihydroorotases, biosynthèse des pyrimidines), pour lesquelles j'ai proposé une nouvelle classification. L'arbre phylogénétique inclut les dihydropyrimidinases (DHPases) et allantoïnases (ALNases) qui ont des réactions similaires dans d'autres voies (dégradation des pyrimidines et des purines respectivement). (2) L'étude de la superfamille des DHODases (qui suivent les DHOases) montre une phylogénie semblable aux DHOases, avec également des enzymes d'autres voies, dont les DHPDases (qui suivent les DHPases). De cette observation est né le concept de module réactionnel, qui correspond à la conservation de l'enchaînement de réactions semblables dans différentes voies métaboliques. Cela a été utilisé lors de (3) l'étude des carbamoyltransférases (TCases) qui incluent les ATCases (précédant les DHOases). J'ai d'abord montré l'existence d'une nouvelle TCase potentiellement impliquée dans la dégradation des purines et lui ai proposé un nouveau rôle en utilisant le concept de module réactionnel (enchaînement avec l'ALNase). Dans ces trois grandes familles j'ai aussi mis en évidence trois groupes de paralogues non identifiés qui se retrouvent pourtant dans un même contexte génétique appelé " Yge " et qui formeraient donc un module réactionnel constitutif d'une nouvelle voie hypothétique. Appliqué à diverses voies, le concept de modules réactionnels refléterait donc les voies métaboliques ancestrales dont ils seraient les éléments de base.

Les objectifs de cette thèse s’inscrivent dans la large problématique du traitement des données issues de séquenceurs à très haut débit, et plus particulièrement des reads longs, issus de séquenceurs de troisième génération.Les aspects abordés dans cette problématiques se concentrent principalement sur la correction des erreurs de séquençage, et sur l’impact de la correction sur la qualité des analyses sous-jacentes, plus particulièrement sur l’assemblage. Dans un premier temps, l’un des objectifs de cette thèse est de permettre d’évaluer et de comparer la qualité de la correction fournie par les différentes méthodes de correction hybride (utilisant des reads courts en complément) et d’auto-correction (se basant uniquement sur l’information contenue dans les reads longs) de l’état de l’art. Une telle évaluation permet d’identifier aisément quelle méthode de correction est la mieux adaptée à un cas donné, notamment en fonction de la complexité du génome étudié, de la profondeur de séquençage, ou du taux d’erreurs des reads. De plus, les développeurs peuvent ainsi identifier les limitations des méthodes existantes, afin de guider leurs travaux et de proposer de nouvelles solutions visant à pallier ces limitations. Un nouvel outil d’évaluation, proposant de nombreuses métriques supplémentaires par rapport au seul outil disponible jusqu’alors, a ainsi été développé. Cet outil, combinant une approche par alignement multiple à une stratégie de segmentation, permet également une réduction considérable du temps nécessaire à l’évaluation. À l’aide de cet outil, un benchmark de l’ensemble des méthodes de correction disponibles est présenté, sur une large variété de jeux de données, de profondeur de séquençage, de taux d’erreurs et de complexité variable, de la bactérie A. baylyi à l’humain. Ce benchmark a notamment permis d’identifier deux importantes limitations des outils existants : les reads affichant des taux d’erreurs supérieurs à 30%, et les reads de longueur supérieure à 50 000 paires de bases. Le deuxième objectif de cette thèse est alors la correction des reads extrêmement bruités. Pour cela, un outil de correction hybride, combinant différentes approches de l’état de l’art, a été développé afin de surmonter les limitations des méthodes existantes. En particulier, cet outil combine une stratégie d’alignement des reads courts sur les reads longs à l’utilisation d’un graphe de de Bruijn, ayant la particularité d’être d’ordre variable. Le graphe est ainsi utilisé afin de relier les reads alignés, et donc de corriger les régions non couvertes des reads longs. Cette méthode permet ainsi de corriger des reads affichant des taux d’erreurs atteignant jusqu’à 44%, tout en permettant un meilleur passage à l’échelle sur de larges génomes et une diminution du temps de traitement, par rapport aux méthodes de l’état de l’art les plus efficaces. Enfin, le troisième objectif de cette thèse est la correction des reads extrêmement longs. Pour cela, un outil utilisant cette fois une approche par auto-correction a été développé, en combinant, de nouveau, différentes méthodologies de l’état de l’art. Plus précisément, une stratégie de calcul des chevauchements entre les reads, puis une double étape de correction, par alignement multiple puis par utilisation de graphes de de Bruijn locaux, sont utilisées ici. Afin de permettre à cette méthode de passer efficacement à l’échelle sur les reads extrêmement longs, la stratégie de segmentation mentionnée précédemment a été généralisée. Cette méthode d’auto-correction permet ainsi de corriger des reads atteignant jusqu’à 340 000 paires de bases, tout en permettant un excellent passage à l’échelle sur des génomes plus complexes, tels que celui de l’humain. / The aims of this thesis are part of the vast problematic of high-throughput sequencing data analysis. More specifically, this thesis deals with long reads from third-generation sequencing technologies. The aspects tackled in this topic mainly focus on error correction, and on its impact on downstream analyses such a de novo assembly. As a first step, one of the objectives of this thesis is to evaluate and compare the quality of the error correction provided by the state-of-the-art tools, whether they employ a hybrid (using complementary short reads) or a self-correction (relying only on the information contained in the long reads sequences) strategy. Such an evaluation allows to easily identify which method is best tailored for a given case, according to the genome complexity, the sequencing depth, or the error rate of the reads. Moreover, developpers can thus identify the limiting factors of the existing methods, in order to guide their work and propose new solutions allowing to overcome these limitations. A new evaluation tool, providing a wide variety of metrics, compared to the only tool previously available, was thus developped. This tool combines a multiple sequence alignment approach and a segmentation strategy, thus allowing to drastically reduce the evaluation runtime. With the help of this tool, we present a benchmark of all the state-of-the-art error correction methods, on various datasets from several organisms, spanning from the A. baylyi bacteria to the human. This benchmark allowed to spot two major limiting factors of the existing tools: the reads displaying error rates above 30%, and the reads reaching more than 50 000 base pairs. The second objective of this thesis is thus the error correction of highly noisy long reads. To this aim, a hybrid error correction tool, combining different strategies from the state-of-the-art, was developped, in order to overcome the limiting factors of existing methods. More precisely, this tool combines a short reads alignmentstrategy to the use of a variable-order de Bruijn graph. This graph is used in order to link the aligned short reads, and thus correct the uncovered regions of the long reads. This method allows to process reads displaying error rates as high as 44%, and scales better to larger genomes, while allowing to reduce the runtime of the error correction, compared to the most efficient state-of-the-art tools.Finally, the third objectif of this thesis is the error correction of extremely long reads. To this aim, aself-correction tool was developed, by combining, once again, different methologies from the state-of-the-art. More precisely, an overlapping strategy, and a two phases error correction process, using multiple sequence alignement and local de Bruijn graphs, are used. In order to allow this method to scale to extremely long reads, the aforementioned segmentation strategy was generalized. This self-correction methods allows to process reads reaching up to 340 000 base pairs, and manages to scale very well to complex organisms such as the human genome.

J'ai mis au point une méthodologie pour annoter les superfamilles d'enzymes, en décrire l'histoire et les replacer dans l'évolution de leurs voies métaboliques. J'en ai étudié trois : (1) les amidohydrolases cycliques, dont les DHOases (dihydroorotases, biosynthèse des pyrimidines), pour lesquelles j'ai proposé une nouvelle classification. L'arbre phylogénétique inclut les dihydropyrimidinases (DHPases) et allantoïnases (ALNases) qui ont des réactions similaires dans d'autres voies (dégradation des pyrimidines et des purines respectivement). (2) L'étude de la superfamille des DHODases (qui suivent les DHOases) montre une phylogénie semblable aux DHOases, avec également des enzymes d'autres voies, dont les DHPDases (qui suivent les DHPases). De cette observation est né le concept de module réactionnel, qui correspond à la conservation de l’enchaînement de réactions semblables dans différentes voies métaboliques. Cela a été utilisé lors de (3) l'étude des carbamoyltransférases (TCases) qui incluent les ATCases (précédant les DHOases). J'ai d'abord montré l'existence d'une nouvelle TCase potentiellement impliquée dans la dégradation des purines et lui ai proposé un nouveau rôle en utilisant le concept de module réactionnel (enchaînement avec l'ALNase). Dans ces trois grandes familles j'ai aussi mis en évidence trois groupes de paralogues non identifiés qui se retrouvent pourtant dans un même contexte génétique appelé « Yge » et qui formeraient donc un module réactionnel constitutif d'une nouvelle voie hypothétique. Appliqué à diverses voies, le concept de modules réactionnels refléterait donc les voies métaboliques ancestrales dont ils seraient les éléments de base. / I designed a methodology to annotate enzyme superfamilies, explain their history and describe them in the context of metabolic pathways evolution. Three superfamilies were studied: (1) cyclic amidohydrolases, including DHOases (dihydroorotases, third step of the pyrimidines biosynthesis), for which I proposed a new classification. The phylogenetic tree also includes dihydropyrimidinases (DHPases) and allantoinases (ALNases) which catalyze similar reactions in other pathways (pyrimidine and purine degradation, respectively). (2) The DHODases superfamily (after DHOases) show a similar phylogeny as DHOases, including enzymes from other pathways, DHPDases in particular (after DHPases). This led to the concept of reaction module, i.e. a conserved series of similar reactions in different metabolic pathways. This was used to study (3) the carbamoyltransferases (TCases) which include ATCases (before DHOases). I first isolated a new kind of TCase, potentially involved in the purine degradation, and I proposed a new role for it in the light of reaction modules (linked with ALNase). In those three superfamilies I also found three groups of unidentified paralogs that were remarkably part of the same genetic context called “Yge” which would be a reaction module part of an unidentified pathway. The concept of reactions modules may then reflect the ancestral metabolic pathways for which they would be basic elements.

Cette thèse est particulièrement destinée à traiter deux types de problèmes : clustering et l'alignement multiple de séquence. Notre objectif est de résoudre de manière satisfaisante ces problèmes globaux et de tester l'approche de la Programmation DC et DCA sur des jeux de données réelles. La thèse comporte trois parties : la première partie est consacrée aux nouvelles approches de l'optimisation non convexe. Nous y présentons une étude en profondeur de l'algorithme qui est utilisé dans cette thèse, à savoir la programmation DC et l'algorithme DC (DCA). Dans la deuxième partie, nous allons modéliser le problème clustering en trois sous-problèmes non convexes. Les deux premiers sous-problèmes se distinguent par rapport au choix de la norme utilisée, (clustering via les normes 1 et 2). Le troisième sous-problème utilise la méthode du noyau, (clustering via la méthode du noyau). La troisième partie sera consacrée à la bio-informatique. On va se focaliser sur la modélisation et la résolution de deux sous-problèmes : l'alignement multiple de séquence et l'alignement de séquence d'ARN par structure. Tous les chapitres excepté le premier se terminent par des tests numériques. / This Ph.D. thesis is particularly intended to treat two types of problems : clustering and the multiple alignment of sequence. Our objective is to solve efficiently these global problems and to test DC Programming approach and DCA on real datasets. The thesis is divided into three parts : the first part is devoted to the new approaches of nonconvex optimization-global optimization. We present it a study in depth of the algorithm which is used in this thesis, namely the programming DC and the algorithm DC ( DCA). In the second part, we will model the problem clustering in three nonconvex subproblems. The first two subproblems are distinguished compared to the choice from the norm used, (clustering via norm 1 and 2). The third subproblem uses the method of the kernel, (clustering via the method of the kernel). The third part will be devoted to bioinformatics, one goes this focused on the modeling and the resolution of two subproblems : the multiple alignment of sequence and the alignment of sequence of RNA. All the chapters except the first end in numerical tests.