La génomique comparative est l'étude des relations structurales et fonctionnelles entre des génomes appartenant à différentes souches ou espèces. Cette discipline offre ainsi la possibilité d'étudier et de comprendre les processus qui façonnent les génomes au cours de l'évolution. Dans le cadre de cette thèse, nous nous sommes intéressés à la génomique comparative des bactéries et plus particulièrement aux méthodes relatives à la comparaison des séquences complètes d'ADN des génomes bactériens. Ces dix dernières années, le développement d'outils informatiques permettant de comparer des génomes entiers à l'échelle de l'ADN est devenu une thématique de recherche à part entière. Actuellement, il existe de nombreux outils dédiés à cette tâche. Cependant, jusqu'à présent, la plupart des efforts ont été dirigés vers la réduction du temps de calcul et l'optimisation de la mémoire au détriment de l'évaluation de la qualité des résultats obtenus. Pour combler ce vide, nous avons travaillé sur différents problèmes statistiques soulevés par la comparaison de génomes complets bactériens. Notre travail se divise en deux axes de recherche. Dans un premier temps, nous nous sommes employés à évaluer la robustesse des alignements de génomes complets bactériens. Nous avons proposé une méthode originale fondée sur l'application de perturbations aléatoires sur les génomes comparés. Trois scores différents sont alors calculés pour estimer la robustesse des alignements de génomes à différentes échelles, allant des nucléotides aux séquences entières des génomes. Notre méthode a été expérimentée sur des données génomiques bactériennes réelles. Nos scores permettent d'identifier à la fois les alignements robustes et non robustes. Ils peuvent être employés pour corriger un alignement ou encore pour comparer plusieurs alignements obtenus à partir de différents outils. Dans un second temps, nous avons étudié le problème de la paramétrisation des outils de comparaisons de génomes entiers. En effet, la plupart des outils existants manquent à la fois de documentation et de valeurs par défaut fiables pour initialiser leurs paramètres. Conséquemment, il y a un besoin crucial de méthodes spécifiques pour aider les utilisateurs à définir des valeurs appropriées pour les paramètres de ces outils. Une grande partie des outils de comparaisons de génomes complets est fondée sur la détection des matches (mots communs exacts). Le paramètre essentiel pour ces méthodes est la longueur des matches à considérer. Au cours de cette thèse, nous avons développé deux méthodes statistiques pour estimer une valeur optimale pour la taille des matches. Notre première approche utilise un modèle de mélange de lois géométriques pour caractériser la distribution de la taille des matches obtenus lorsque l'on compare deux séquences génomiques. La deuxième approche est fondée sur une approximation de Poisson de la loi du comptage des matches entre deux chaînes de Markov. Ces méthodes statistiques nous permettent d'identifier facilement une taille optimale de matches à la fois pour des séquences simulées et pour des données génomiques réelles. Nous avons également montré que cette taille optimale dépend des caractéristiques des génomes comparés telles que leur taille, leur composition en base ou leur divergence relative. Cette thèse représente une des toutes premières études dont l'objectif est d'évaluer et d'améliorer la qualité des comparaisons des génomes complets. L'intérêt et les limites de nos différentes approches sont discutés et plusieurs perspectives d'évolution sont proposées. / Comparative genomics is the study of the structural and functional relationships between genomes belonging to different strains or species. This discipline offers great opportunities to investigate and to understand the processes that shape genomes across the evolution. In this thesis, we focused on the comparative genomics of bacteria and more precisely, on methods dedicated to the comparison of the complete DNA sequences of bacterial genomes. This last decade, the design of specific computerized methods to compare complete genomes at the DNA scale has become a subject of first concern. Now, there exist many tools and methods dedicated to this task. However, until now, most of the efforts were directed to reduce execution time and memory usage at the expense of the evaluation of the quality of the results. To fill this gap, we worked on different statistical issues related to the comparison of complete bacterial genomes. Our work was conducted into two directions. In the first one, we investigated the assessment of the robustness of complete bacterial genome alignments. We proposed an original method based on random perturbations of the compared genomes. Three different scores were derived to estimate the robustness of genome alignments at different scales, from nucleotides to the complete genome sequences. Our method was trained on bacterial genomic data. Our scores allow us to identify robust and non robust genome alignments. They can be used to correct an alignment or to compare alignments performed with different tools. Secondly, we studied the problem of the parametrization of comparison tools. Briefly, most of the existing tools suffer from a lack of information and of reliable default values to set their parameters. Consequently, there is a crucial need of methods to help users to define reliable parameter values for these tools. Most of the comparison tools are rooted on the detection of word matches. The key parameter for all these tools is the length of the matches to be considered. During this thesis, we developed two statistical methods to estimate an optimal length for these matches. Our first approach consisted in using a mixture model of geometric distributions to characterize the distribution of the length of matches retrieved from the comparison of two genomic sequences. The second approach is rooted on a Poisson approximation of the number of matches between two Markov chains. These statistical methods allow us to easily identify an optimal length for the matches from both simulated and real genomic data. We also showed that this optimal length depends on the characteristics of the compared genomes such as their length, their nucleotide composition, and their relative divergence. This thesis represents one of the earliest attempts to statistically evaluate and to improve the quality of complete genome comparisons. The interest and limitations of our different methods are discussed and some perspectives are proposed.

Le paludisme, ou malaria, est une maladie infectieuse qui touche plus de 350 millions d'êtres humains et qui tue chaque année 2,5 millions de personnes à travers le monde. Les parasites responsables de la malaria sont des apicomplexes du genre Plasmodium, essentiellement P. falciparum. Le génome de P. falciparum, est séquencé depuis octobre 2002, et présente un des taux les plus faibles de gènes annotés, avec ~60 % de gènes sans fonction attribuée. Il est difficile, voire impossible, d'identifier dans le génome de P. falciparumi, certains gènes, responsables de fonctions mesurées biochimiquement chez le parasite, par similarité avec des séquences homologues caractérisées dans d'autres organismes. Cette difficulté rencontrée lors des recherches automatiques d'homologie est une limite à tout projet exploratoire du génome malarial fondé sur la phylogénie moléculaire. En particulier, l'inventaire des séquences héritées de l'algue ancestrale, qui a réalisé l'endosymbiose secondaire qui caractérise le phylum des Apicomplexa (sous génome d'origine algale dans lequel il est possible de rechercher des cibles pour des médicaments herbicides), peut être rendu incomplet. Les caractéristiques atypiques du génome et du protéome de Plasmodium, résumées sous le terme de biais compositionnel (en particulier un pourcentage en adénosine+thymidine supérieur à 80%), ont été soupçonnées d'être un cas limite pour les outils d'analyse de séquence existants. L'objet de cette thèse a donc été d'examiner l'influence possible de ce type de biais sur les méthodologies de comparaisons de séquences et de façon plus approfondie sur leurs statistiques.<br />Nous avons proposé des développements théoriques nouveaux, associés à la statistique de la Z-value introduite par Lipman et Pearson pour évaluer la significativité d'un score d'alignement de deux séquences protéiques: (1) le théorème TULIP permettant de déduire un majorant de la probabilité d'un score d'alignement de séquences (i.e. la P-value) par la valeur 1/Z-value2 et (2) la déduction des propriétés remarquables de la distribution des Z-values à partir de quelques hypothèses sur l'évolution des protéines dans le contexte de la théorie de la fiabilité des systèmes. Ces développements théoriques ont permis certaines avancées sur le plan pratique de l'identification de séquences homologues initialement non détectées par le théorème de Karlin-Altschul et d'étayer la relation entre les scores d'alignements et l'information mutuelle, au sens de la théorie de l'information.<br />En construisant un espace de configuration des protéines homologues, permettant une expression du théorème TULIP et ayant une cohérence avec la théorie synthétique de l'évolution, nous avons déduit une méthode de reconstruction de phylogénies de séquences protéiques à l'aide des Z-values. Les phylogénies moléculaires reconstruites par cette méthode sont concordantes avec celles obtenues à partir d'alignements multiples et permettent par ailleurs de résoudre certaines incohérences rapportées avec les méthodes de reconstruction phylogéniques classiques.<br />En prenant en compte le modèle statistique que nous avons élaboré, nous avons entrepris une première analyse de l'évolution du biais en acides aminés chez Plasmodium corrélativement à l'évolution du biais en acides nucléiques dans le génome malarial et en fonction de la divergence évolutive, établie en prenant le génome non biaisé d'Arabidopsis thaliana comme référence. Nous avons observé que le biais des séquences malariales était corrélé au pourcentage de divergence avec leurs homologues végétaux. Nos analyses suggèrent de plus que le biais est vraisemblablement la conséquence d'une évolution au niveau nucléique. Nous avons examiné la possibilité de construire une famille de matrices tenant compte de cette dissymétrie dans le cas de la comparaison de Plasmodium et d'Arabidopsis. Ces matrices appelées DirAtPf, possèdent (1) une sensibilité théorique et (2) une spécificité supérieure aux familles de matrices existantes.<br />Les perspectives des travaux présentés dans ce mémoire incluent une progression de l'annotation automatique de Plasmodium falciparum et la mise en place d'une procédure statistiquement robuste et phylogénétiquement consistante pour caractériser le sous-génome algal du parasite malarial.

L'échec des modèles pour prévoir l'alignement de bandes dans un empilement MOS (métal-oxyde-semiconducteur) rend utile et intéressant une étude à l'échelle atomique. Nous exposons deux théories ab initio: d'abord la théorie de la fonctionnelle de la densité (DFT), dont dépendent les codes Abinit et Siesta utilisés pour étudier la nature quantique des matériaux ; puis la théorie de l'approximation GW qui corrige les niveaux d'énergies électroniques mal évalués avec l'approximation utilisée en DFT. Ces deux théories sont appliquées à chaque matériau composant l'empilement. Puis nous étudions la façon dont intervient le dipôle dans l'alignement de bandes. La méthode de Van de Walle et Martin est adaptée pour évaluer de façon précise ces alignements grâce à l'approximation GW. Enfin cette méthode est appliquée aux différentes interfaces oxyde/semiconducteur et métal/oxyde et montre que les alignements de bandes estimés par simulation tendent vers un accord avec les mesures expérimentales.

L’évolution des protéines est un domaine important de la recherche en bioinformatique et catalyse l'intérêt de trouver des outils d'alignement qui peuvent être utilisés de manière fiable et modéliser avec précision l'évolution d'une famille de protéines. TM-Align (Zhang and Skolnick, 2005) est considéré comme l'outil idéal pour une telle tâche, en termes de rapidité et de précision. Par conséquent, dans cette étude, TM-Align a été utilisé comme point de référence pour faciliter la détection des autres outils d'alignement qui sont en mesure de préciser l'évolution des protéines. En parallèle, nous avons élargi l'actuel outil d'exploration de structures secondaires de protéines, Helix Explorer (Marrakchi, 2006), afin qu'il puisse également être utilisé comme un outil pour la modélisation de l'évolution des protéines. / Protein evolution is an important field of research in bioinformatics and catalyzes the requirement of finding alignment tools that can be used to reliably and accurately model the evolution of a protein family. TM-Align (Zhang and Skolnick, 2005) is considered to be the ideal tool for such a task, in terms of both speed and accuracy. Therefore in this study, TM-Align has been used as a point of reference to facilitate the detection of other alignment tools that are able to accurately model protein evolution. In parallel, we expand the existing protein secondary structure explorer tool, Helix Explorer (Marrakchi, 2006), so that it can also be used as a tool to model protein evolution.

Détecter des similarités et des homologies entre protéines est une étape cruciale du processus d'annotation des génomes. Afin de détecter des homologies, les alignements de séquences, globaux ou locaux, sont couramment utilisés. Néanmoins, dans la "zone d'ombre", nous devons utiliser les méthodes de reconnaissance de repliements. Dans ce domaine, le problème du "Protein Threading" (PTP) utilise des paramètres pairés pour aligner globalement une séquence de protéine avec une structure de protéine. À notre connaissance, il n'existe pas de méthode d'alignement local utilisant des paramètres pairés. À partir du PTP, nous proposons cinq modélisations mathématiques de ces alignements locaux qui ont été implémentées et testées grâce au logiciel CPLEX 10.0. Nous avons ensuite développé un algorithme dédié permettant de résoudre un de ces modèles. Cet algorithme utilise des techniques connues en recherche opérationnelle : la séparation-évaluation, la descente de sous-gradient et la relaxation lagrangienne. Bien que les alignements locaux soient d'une plus grande complexité, nous montrons qu'ils sont réalisables et qu'ils améliorent la qualité des alignements.

L’évolution des protéines est un domaine important de la recherche en bioinformatique et catalyse l'intérêt de trouver des outils d'alignement qui peuvent être utilisés de manière fiable et modéliser avec précision l'évolution d'une famille de protéines. TM-Align (Zhang and Skolnick, 2005) est considéré comme l'outil idéal pour une telle tâche, en termes de rapidité et de précision. Par conséquent, dans cette étude, TM-Align a été utilisé comme point de référence pour faciliter la détection des autres outils d'alignement qui sont en mesure de préciser l'évolution des protéines. En parallèle, nous avons élargi l'actuel outil d'exploration de structures secondaires de protéines, Helix Explorer (Marrakchi, 2006), afin qu'il puisse également être utilisé comme un outil pour la modélisation de l'évolution des protéines. / Protein evolution is an important field of research in bioinformatics and catalyzes the requirement of finding alignment tools that can be used to reliably and accurately model the evolution of a protein family. TM-Align (Zhang and Skolnick, 2005) is considered to be the ideal tool for such a task, in terms of both speed and accuracy. Therefore in this study, TM-Align has been used as a point of reference to facilitate the detection of other alignment tools that are able to accurately model protein evolution. In parallel, we expand the existing protein secondary structure explorer tool, Helix Explorer (Marrakchi, 2006), so that it can also be used as a tool to model protein evolution.

Ces travaux de thèse concernent la conception et l'étude d'algorithmes, d'une part pourprédire les quantités thermodynamiques et la structure secondaire des ARN, d'autre part pour l'alignement de séquences.Dans une première partie, nous appliquons un algorithme de Monte-Carlo pour approximer la densité d'états d'énergie des structures secondaires d'une séquence d'ARN, ou d'une hybridation de deux molécules d'ARN données. Nous montrons d'abord que la densité estimée par notre programme est aussi bonne que la densité exacte, et le temps d'exécution de notre programme est beaucoup plus rapide. Nous calculons ensuite la température de dénaturation d'une hybridation de deux molécules d'ARN. Nous montrons que nos températures de dénaturation sont plus proches des valeurs expérimentales que celles des deux autres programmes existants.Puis, dans une deuxième partie, nous implémentons un algorithme de programmation dynamique qui engendre des structures sous-optimales, dédié principalement à la prédiction des deux structures fonctionnelles des riboswitchs. Nous appliquons d'abord notre programme sur un riboswitch TPP dans lequel nous avons réussi à détecter les deux structures fonctionnelles. Nous montrons ensuite que les structures prédites par notre programme sont plus proches de la structure réelle par rapport aux cinq autres programmes existants, sur un échantillon de riboswitch purine.Enfin, dans une troisième partie, nous présentons un algorithme de recherche des alignements sous-optimaux de séquences pour améliorer la qualité d'alignement des séquences. Nous comparons d'abord nos alignement à ceux produits par l'algorithme de Needdleman-Wunsch. Nous prédissons plus d'alignements de référrence par rapport l'algorithme de Needdleman-Wunsch. Nous calculons ensuite les fréquences des paires de bases alignées et les entropies de position spécifique dans nos alignements sous-optimaux. Nous montrons que les entropies calculées à partir de notre programme sont plus corrélées que celles des autres programmes avec les positions des paires de résidus fiablement alignées selon BAliBASE.

Nous présentons des résultats numériques et théoriques concernant les cascades en turbulence bidimensionnelle, et plus spécialement la cascade d'un traceur, en développant une approche dans l'espace physique. Une telle approche permet de mettre en évidence l'absence d'intermittence dans la cascade inverse d'énergie, y compris dans des situations dominées par les structures cohérentes. Le coeur de la thèse est consacré à l'analyse et à la modélisation de la cascade d'un traceur. Nous proposons une méthode de diagnostic de la cascade d'un traceur : considérant l'évolution d'un incrément de traceur, nous définissons dans l'espace physique le flux entre échelles de la variance de traceur. Nous nous intéressons ensuite au problème de la paramétrisation du mélange turbulent. Nous justifions l'emploi une paramétrisation anisotrope, que nous baptisons diffusivité de déformation (strain diffusivity, SD)[Dubos01]. Nous relions ses propriétés diffusives aux propriétés géométriques de l'écoulement. La vorticité est en deux dimensions un traceur actif, et la paramétrisation sous-maille pour la vorticité agit sur la vitesse. La cascade inverse d'énergie impose aux paramétrisations admissibles de conserver l'énergie. Nous montrons que la SD conserve l'énergie, et qu'elle est la seule d'une classe de modèles simples. Nous étudions numériquement les propriétés des outils introduits. Nous montrons que, contrairement à une diffusivité/hyperdiffusivité isotrope, la SD induit une diffusion bien corrélée au flux local de variance de traceur. Le filtre effectif qu'elle impose correspond au filtre gaussien à partir duquel elle est calculée. Cependant la réduction de l'erreur commise en cas d'utilisation d'une méthode spectrale et d'un filtre raide n'est pas évidente. Appliquée à la vorticité dans une situation où le forçage est à très petite échelle, la SD démontre en revanche une bien meilleure représentation des grandes échelles qu'une hyperdiffusivité. Enfin, nous analysons comparativement les propriétés de cascade de la vorticité et d'un traceur passif. Les critères de comparaison reposent sur des moyennes conditionnelles des dérivées lagrangiennes du carré du gradient du traceur. Nous mettons en évidence pour un champ aléatoire une différence cinématique entre traceur passif et vorticité, dont il subsiste une trace dans des champs turbulents.

Ces travaux de thèse concernent la conception et l'étude d'algorithmes, d'une part pourprédire les quantités thermodynamiques et la structure secondaire des ARN, d'autre part pour l'alignement de séquences.Dans une première partie, nous appliquons un algorithme de Monte-Carlo pour approximer la densité d'états d'énergie des structures secondaires d'une séquence d'ARN, ou d'une hybridation de deux molécules d'ARN données. Nous montrons d'abord que la densité estimée par notre programme est aussi bonne que la densité exacte, et le temps d'exécution de notre programme est beaucoup plus rapide. Nous calculons ensuite la température de dénaturation d'une hybridation de deux molécules d'ARN. Nous montrons que nos températures de dénaturation sont plus proches des valeurs expérimentales que celles des deux autres programmes existants.Puis, dans une deuxième partie, nous implémentons un algorithme de programmation dynamique qui engendre des structures sous-optimales, dédié principalement à la prédiction des deux structures fonctionnelles des riboswitchs. Nous appliquons d'abord notre programme sur un riboswitch TPP dans lequel nous avons réussi à détecter les deux structures fonctionnelles. Nous montrons ensuite que les structures prédites par notre programme sont plus proches de la structure réelle par rapport aux cinq autres programmes existants, sur un échantillon de riboswitch purine.Enfin, dans une troisième partie, nous présentons un algorithme de recherche des alignements sous-optimaux de séquences pour améliorer la qualité d'alignement des séquences. Nous comparons d'abord nos alignement à ceux produits par l'algorithme de Needdleman-Wunsch. Nous prédissons plus d'alignements de référrence par rapport l'algorithme de Needdleman-Wunsch. Nous calculons ensuite les fréquences des paires de bases alignées et les entropies de position spécifique dans nos alignements sous-optimaux. Nous montrons que les entropies calculées à partir de notre programme sont plus corrélées que celles des autres programmes avec les positions des paires de résidus fiablement alignées selon BAliBASE. / This thesis concerns the design and study of algorithms, on the one hand to predict the thermodynamic quantities and the secondary structure of RNA, the other for sequence alignment.In the first part, we apply a Monte Carlo algorithm to approximate the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. We first show that the density estimated by our program is as good as the exact density, and the execution time of our program is much faster. We then calculate the melting temperature for a hybridization of two RNA sequences. We show that our melting temperatures are closer to experimental values than the other two programs.Then in the second part, we implement a dynamic programming algorithm that generates sub-optimal structures, mainly dedicated to the prediction of functional structures of riboswitchs. We first apply our program on a TPP riboswitch in which we were able to detect both functional structures. We then show that the structures predicted by our program are closer to the real structure compared to five other existing programs, on a sample of purine riboswitch.Finally, in the third part, we present a novel algorithm to produce sub-optimal pairwise alignments. We first compare our alignments to those produced by the algorithm of Needdleman-Wunsch. We predict more reference alignments than the algorithm of Needdleman-Wunsch. We then calculate the frequencies and position-specific entropies from our sub-optimal alignments. We show that entropies calculated from our program are more correlated than other programs with locations in the core block of BAliBASE reference alignments.