La conjecture de partitionnement des chemins

Soit G = (V, E) un graphe simple fini. Soit (a, b) un couple d’entiers positifs. On note par τ(G) le nombre de sommets d’un chemin d’ordre maximum dans G. Une partition (A,B) de V(G) est une (a,b)−partition si τ(⟨A⟩) ≤ a et τ(⟨B⟩) ≤ b. Si G possède une (a, b)−partition pour tout couple d’entiers positifs satisfaisant τ(G) = a+b, on dit que G est τ−partitionnable. La conjecture de partitionnement des chemins, connue sous le nom anglais de Path Partition Conjecture, cherche à établir que tout graphe est τ−partitionnable. Elle a été énoncée par Lovász et Mihók en 1981 et depuis, de nombreux chercheurs ont tenté de démontrer cette conjecture et plusieurs y sont parvenus pour certaines classes de graphes. Le présent mémoire rend compte du statut de la conjecture, en ce qui concerne les graphes non-orientés et ceux orientés.

Systems biology of plants : from intraspecific genome variation to computational morphodynamics

Recently, the introduction of second generation sequencing and further advance-ments in confocal microscopy have enabled system-level studies for the functional characterization of genes. The degree of complexity intrinsic to these approaches needs the development of bioinformatics methodologies and computational models for extracting meaningful biological knowledge from the enormous amount of experi¬mental data which is continuously generated. This PhD thesis presents several novel bioinformatics methods and computational models to address specific biological questions in Plant Biology by using the plant Arabidopsis thaliana as a model system. First, a spatio-temporal qualitative analysis of quantitative transcript and protein profiles is applied to show the role of the BREVIS RADIX (BRX) protein in the auxin- cytokinin crosstalk for root meristem growth. Core of this PhD work is the functional characterization of the interplay between the BRX protein and the plant hormone auxin in the root meristem by using a computational model based on experimental evidence. Hyphotesis generated by the modelled to the discovery of a differential endocytosis pattern in the root meristem that splits the auxin transcriptional response via the plasma membrane to nucleus partitioning of BRX. This positional information system creates an auxin transcriptional pattern that deviates from the canonical auxin response and is necessary to sustain the expression of a subset of BRX-dependent auxin-responsive genes to drive root meristem growth. In the second part of this PhD thesis, we characterized the genome-wide impact of large scale deletions on four divergent Arabidopsis natural strains, through the integration of Ultra-High Throughput Sequencing data with data from genomic hybridizations on tiling arrays. Analysis of the identified deletions revealed a considerable portion of protein coding genes affected and supported a history of genomic rearrangements shaped by evolution. In the last part of the thesis, we showed that VIP3 gene in Arabidopsis has an evo-lutionary conserved role in the 3' to 5' mRNA degradation machinery, by applying a novel approach for the analysis of mRNA-Seq data from random-primed mRNA. Altogether, this PhD research contains major advancements in the study of natural genomic variation in plants and in the application of computational morphodynamics models for the functional characterization of biological pathways essential for the plant. - Récemment, l'introduction du séquençage de seconde génération et les avancées dans la microscopie confocale ont permis des études à l'échelle des différents systèmes cellulaires pour la caractérisation fonctionnelle de gènes. Le degrés de complexité intrinsèque à ces approches ont requis le développement de méthodologies bioinformatiques et de modèles mathématiques afin d'extraire de la masse de données expérimentale générée, des information biologiques significatives. Ce doctorat présente à la fois des méthodes bioinformatiques originales et des modèles mathématiques pour répondre à certaines questions spécifiques de Biologie Végétale en utilisant la plante Arabidopsis thaliana comme modèle. Premièrement, une analyse qualitative spatio-temporelle de profiles quantitatifs de transcripts et de protéines est utilisée pour montrer le rôle de la protéine BREVIS RADIX (BRX) dans le dialogue entre l'auxine et les cytokinines, des phytohormones, dans la croissance du méristème racinaire. Le noyau de ce travail de thèse est la caractérisation fonctionnelle de l'interaction entre la protéine BRX et la phytohormone auxine dans le méristème de la racine en utilisant des modèles informatiques basés sur des preuves expérimentales. Les hypothèses produites par le modèle ont mené à la découverte d'un schéma différentiel d'endocytose dans le méristème racinaire qui divise la réponse transcriptionnelle à l'auxine par le partitionnement de BRX de la membrane plasmique au noyau de la cellule. Cette information positionnelle crée une réponse transcriptionnelle à l'auxine qui dévie de la réponse canonique à l'auxine et est nécessaire pour soutenir l'expression d'un sous ensemble de gènes répondant à l'auxine et dépendant de BRX pour conduire la croissance du méristème. Dans la seconde partie de cette thèse de doctorat, nous avons caractérisé l'impact sur l'ensemble du génome des délétions à grande échelle sur quatre souches divergentes naturelles d'Arabidopsis, à travers l'intégration du séquençage à ultra-haut-débit avec l'hybridation génomique sur puces ADN. L'analyse des délétions identifiées a révélé qu'une proportion considérable de gènes codant était affectée, supportant l'idée d'un historique de réarrangement génomique modelé durant l'évolution. Dans la dernière partie de cette thèse, nous avons montré que le gène VÏP3 dans Arabidopsis a conservé un rôle évolutif dans la machinerie de dégradation des ARNm dans le sens 3' à 5', en appliquant une nouvelle approche pour l'analyse des données de séquençage d'ARNm issue de transcripts amplifiés aléatoirement. Dans son ensemble, cette recherche de doctorat contient des avancées majeures dans l'étude des variations génomiques naturelles des plantes et dans l'application de modèles morphodynamiques informatiques pour la caractérisation de réseaux biologiques essentiels à la plante. - Le développement des plantes est écrit dans leurs codes génétiques. Pour comprendre comment les plantes sont capables de s'adapter aux changements environnementaux, il est essentiel d'étudier comment leurs gènes gouvernent leur formation. Plus nous essayons de comprendre le fonctionnement d'une plante, plus nous réalisons la complexité des mécanismes biologiques, à tel point que l'utilisation d'outils et de modèles mathématiques devient indispensable. Dans ce travail, avec l'utilisation de la plante modèle Arabidopsis thalicinci nous avons résolu des problèmes biologiques spécifiques à travers le développement et l'application de méthodes informatiques concrètes. Dans un premier temps, nous avons investigué comment le gène BREVIS RADIX (BRX) régule le développement de la racine en contrôlant la réponse à deux hormones : l'auxine et la cytokinine. Nous avons employé une analyse statistique sur des mesures quantitatives de transcripts et de produits de gènes afin de démontrer que BRX joue un rôle antagonisant dans le dialogue entre ces deux hormones. Lorsque ce-dialogue moléculaire est perturbé, la racine primaire voit sa longueur dramatiquement réduite. Pour comprendre comment BRX répond à l'auxine, nous avons développé un modèle informatique basé sur des résultats expérimentaux. Les simulations successives ont mené à la découverte d'un signal positionnel qui contrôle la réponse de la racine à l'auxine par la régulation du mouvement intracellulaire de BRX. Dans la seconde partie de cette thèse, nous avons analysé le génome entier de quatre souches naturelles d'Arabidopsis et nous avons trouvé qu'une grande partie de leurs gènes étaient manquant par rapport à la souche de référence. Ce résultat indique que l'historique des modifications génomiques conduites par l'évolution détermine une disponibilité différentielle des gènes fonctionnels dans ces plantes. Dans la dernière partie de ce travail, nous avons analysé les données du transcriptome de la plante où le gène VIP3 était non fonctionnel. Ceci nous a permis de découvrir le rôle double de VIP3 dans la régulation de l'initiation de la transcription et dans la dégradation des transcripts. Ce rôle double n'avait jusqu'alors été démontrée que chez l'homme. Ce travail de doctorat supporte le développement et l'application de méthodologies informatiques comme outils inestimables pour résoudre la complexité des problèmes biologiques dans la recherche végétale. L'intégration de la biologie végétale et l'informatique est devenue de plus en plus importante pour l'avancée de nos connaissances sur le fonctionnement et le développement des plantes.

Elemental and isotopic zoning in natural alpine quartz

THESIS ABSTRACT : Stable isotope geochemistry is used to help resolve a large number of geological questions. In order to do this, it is essential to understand the different mechanisms that govern isotopic fractionation processes between different phases and to identify the conditions required to reach equilibrium fractionation. However, at low temperatures, these processes are poorly constrained and many factors can induce differential partitioning of the isotopes between sectors of a mineral species and the fluid during mineral growth. This can result in so-called 'sector zoning' of a mineral species. The aim of this thesis is to evaluate the occurrence of sector zoning of the oxygen isotopes and trace elements in natural α-quartz crystals and to identify the reasons for such zoning. The implications for the fluid-mineral interactions are studied in the context of the Alpine metamorphism. The approach chosen has focused on examining the crystal structure, cathodoluminescence appearance (CL), and on relating elemental (e.g. Li, Na, Al, P, K, Ca, Ge, Ti, Fe) to stable oxygen isotope compositions between and along different growth sectors. Low temperature quartz samples were selected from Alpine veins in different localities, where growth conditions have already been well constrained. The mineralogy as well as the isotopic compositions of the host rocks were also investigated, in order to interpret the variations obtained between the different growth stages in the framework of fluid-rock interaction during Alpine metamorphism. Depending on the growth conditions, most of the studied quartz is strongly zoned in CL, and it reveals corresponding zonations in the trace element content (e.g. growth zoning). Aluminium, substituting for Si in the lattice, was found in concentrations up to 1000's ppma, and its distribution is strongly related to Li and H and to a lesser extent, to Ge. Elemental sector zoning is evident from the distribution of these three elements since they exhibit differences in their respective concentrations between faces for distinct growth zones, with prismatic faces having the lowest Al contents. Quartz from veins in magmatic rocks, for example, tend to have lower Al concentrations and similar concentrations of Li and Ti suggesting also a contribution of these elements from the host rock. The relationship between Al and Li is still correlated. Only Alpine crystals grown at higher temperatures (~400°C) without any CL zoning feature are free of these impurities and do not show such zoning characteristics. Differences in the δ18O values were measured between different faces principally in the AIenriched growth zones or stages. These results were confirmed by the means of two different methods (in situ/non in situ). However, it was determined that the Al concentrations do not affect significantly oxygen isotope fractionations at 300°C. The results altogether suggest that the presence of sector zoning in quartz crystals is real, but not universal, and henceforth should be taken into consideration for any use of these systems. The occurrence of disequilibrium partitioning has been enhanced and is possibly related to kinetic processes as well as structural effects that do not affect similarly trace element incorporation and isotopic fractionation. In situ measurements also revealed fine scale δ18O zonations along growth paths that are useful to constrain fluid-rock interactions during Alpine metamorphism. Variations in the δ18O values present along growth vectors indicate changes in the fluid composition and origin. Association with oxygen isotope composition of the host rock allows for the deduction of interactions between rocks, veins and consequently fluids, as well as fluid regimes. RESUME DE LA THESE : A basses températures, (i.e. <400°C) les différents mécanismes qui régissent le fractionnement isotopique ainsi que les conditions nécessaires pour établir un état d'équilibre sont peu connus et nombre de paramètres peuvent entraîner un partitionnement chimique différentiel entre différents secteurs d'un minéral et le fluide en contact. Ainsi, ce travail de thèse a pour but d'évaluer la possible présence de zonages sectoriels en isotopes de l'oxygène mais aussi en éléments traces dans des cristaux naturels de quartz-α de basses températures, ainsi que les raisons d'un tel phénomène et enfin ses implications sur les interactions fluide-roche, principalement dans le cadre du métamorphisme Alpin. La structure et l'apparence en cathodoluminescence (CL) des échantillons ont été caractérisées avant de retracer en détail les compositions en élément traces (Li, Na, Al, P, K, Ca, Ge, Ti, Fe) et en isotopes de l'oxygène, le long et entre différents secteurs. Les échantillons de quartz sélectionnés proviennent majoritairement de veines Alpine de différentes localités, où les conditions de croissance ont été déjà bien caractérisées. Les compositions minéralogiques et isotopiques de la roche encaissante ont aussi été examinées, pour contraindre les variations obtenues dans un contexte Alpin. Selon leurs conditions de croissance, la plupart des cristaux étudiés sont fortement zonés, ce qui est souligné par un zonage des concentrations en éléments traces (e.g. zonage de croissance). L'Aluminium, qui peut se substituer à la Silice dans le réseau cristallin, a été retrouvé jusqu'en très grandes concentrations dans certaines zones (plusieurs milliers de ppma). De plus, la distribution en Al est fortement liée à celles de Li et H, ainsi que dans une moindre mesure à Ge. La présence de zonage sectoriel est évidente au niveau de ces éléments qui montrent de larges différences de concentrations entre différentes faces pour une même zone de croissance, avec les concentrations les plus basses retrouvées dans les faces prismatiques. Les quartz de veines situées dans des roches magmatiques par exemple possèdent des concentrations en Li et Ti de même ordre de grandeur, confirmant le rôle de la composition de la roche encaissante. La relation Li/Al est toujours fortement présente, mais ce rapport est fonction de la face mesurée. Seuls les cristaux Alpins de plus hautes températures (400°C) ne possédant pas de zones en CL ne présentent aucune de ces caractéristiques. Des différences dans les valeurs de δ18O de zones identiques enrichies en Al ont clairement été mesurées entre les différentes faces r, z, et m, mais aussi au sein d'une même seule zone, indiquant que le fractionnement a probablement eu lieu en déséquilibre. Il a été déterminé que la présence d'Al dans ces teneurs n'avait qu'un faible effet sur le fractionnement isotopique de l'oxygène. L'utilisation de deux méthodes différentes a permis d'obtenir des résultats in situ et non in situ concordants. La comparaison des résultats obtenus permet de démontrer que le zonage sectoriel est bien présent dans certains cristaux de quartz, et dépend des conditions de formation. La présence d'un partitionnement différentiel des éléments traces peut être due à des effets cinétiques aussi bien que structuraux, alors que le zonage sectoriel des isotopes de l'oxygène aurait d'autres origines. Il est alors évident que la possibilité de zonage sectoriel doit être désormais pris en considération avant toute interprétations de données isotopiques de cristaux zonés. Les mesures in situ ont de plus permis de distinguer de fines variations des valeurs δ18O au cours de la croissance, qui peuvent aider à retracer la circulations des fluides dans les Alpes durant cette période. En association avec les compositions des roches encaissantes, ii est possible de déduire les interactions entre roches, veines, et par conséquent fluides, au cours de différentes étapes. RESUME GRAND PUBLIC : La géochimie des isotopes stables a pris beaucoup d'importance depuis ces dernières années pour aider à résoudre nombre de questions géologiques, en se basant sur les caractéristiques du fractionnement isotopiques pour différents systèmes. Il est donc nécessaire d'avoir une connaissance approfondie des mécanismes qui s'appliquent au fractionnement isotopique entre les minéraux et les fluides à partir desquels ils se forment. Ces mécanismes ont été bien approchés par différents types de calibrations pour des systèmes à hautes températures, cependant cela n'est pas aussi évident pour les systèmes à des températures inférieures à 400-500°C. Ce travail de thèse a pour but d'aider à la description et la compréhension des phénomènes qui peuvent affecter le fractionnement isotopique à basses températures, ainsi que leurs implications, à partir de l'étude de cristaux de quartz. Le choix des échantillons s'est porté sur des cristaux naturels formés à des températures inférieures ou égales à 400°C, provenant majoritairement de fissures hydrothermales Alpines dont les conditions de formation ont déjà été déterminées. L'étude des cristaux Alpin permet de plus de replacer les résultats obtenus dans le contexte du métamorphisme Alpin au cours du Miocène (21-13 Ma). Après examen de la structure et de la morphologie des cristaux, et leur caractérisation par cathodoluminescence (CL), des analyses chimiques détaillées sur les éléments en traces pouvant entrer dans le réseau cristallin du quartz comme impuretés (i.e. Li, Na, Al, P, K, Ca, Ge, Ti), et des isotopes stables de l'oxygène, ont été menées. En fonction des conditions de croissance, la plupart des cristaux présentent des zonations, qui peuvent être facilement reliées à la distribution des éléments traces analysés par microsonde électronique, sonde ionique (SIMS) et LA-ICPMS. De fortes concentrations d'Aluminium (plusieurs milliers de parties par million atomique) ont pu être observées dans les zones les plus externes des cristaux. De plus, les concentrations en Al et en Li sont toujours corrélées; la présence d'Hydrogène déduite à partir d'analyses par FTIR suit cette même tendance. Les différentes faces des cristaux présentent des concentrations distinctes d'Al, Li et H pour des mêmes zones de croissance, avec par exemple les concentrations les plus faibles dans les zones des faces prismatiques. Cela implique la présence d'un zonage sectoriel, qui a déjà été observé principalement dans des carbonates mais jamais décrit auparavant pour des quartz. Seuls les cristaux alpins homogènes en CL dont la croissance s'est faite à plus haute température (400°C) ne présentent aucune de ces caractéristiques. Par analogie avec le zonage sectoriel en Al, élément qui se substitue au Si dans le réseau cristallin du quartz, il est possible de penser qu'un zonage sectoriel pourrait aussi s'appliquer aux isotopes de l'oxygène. Des précédentes études avaient en effet émis cette hypothèse. Nos résultats ont été obtenus à partir d'analyses à la fois in- situ par SIMS, et par extraction assistée par laser-CO2 sur des parties de quartz soigneusement séparées, et sont en accord entre les deux méthodes. Un zonage sectoriel est en effet bien présent pour les cristaux alpins, mais principalement au niveau des zones très riches en Aluminium. Cependant, il a été déterminé que la présence d'Al dans ces teneurs avait un effet plus que minimal sur le fractionnement isotopique de l'oxygène. Des différences importantes ont été observées entre les faces r & z mais aussi au sein d'une même et seule zone, indiquant que le fractionnement a pu avoir lieu en déséquilibre, ce qui est aussi visible au niveau des valeurs totalement opposées entre faces pour la dernière phase de croissance de certains cristaux. Ainsi l'association de ces résultats laisse suggérer que la présence d'un zonage sectoriel peut être liée à différents paramètres tels que le taux de croissance ou la structure de surface du cristal, mais qui n'affectent pas de la même façon l'incorporation des éléments traces et le fractionnement isotopique. La possibilité d'un zonage sectoriel est importante à prendre en compte lors de toute interprétation de données isotopiques. Les analyses des isotopes de l'oxygène effectuées par SIMS ont aussi permis de distinguer des variations importantes à petite échelle au cours de la croissance. Des mesures faites par laser CO2 sur certaines roches encaissantes, ont permis distinguer plusieurs étapes dans la croissance des minéraux et de déduire le rôle de l'encaissant et le type de fluide. En association avec de précédentes études, il a été ainsi possible de mieux contraindre la formation de ces cristaux dans le contexte alpin et la circulation de fluide au cours du métamorphisme alpin durant le Miocène.

Implantation des futures sur un système distribué par passage de messages

Ce mémoire présente une implantation de la création paresseuse de tâches desti- née à des systèmes multiprocesseurs à mémoire distribuée. Elle offre un sous-ensemble des fonctionnalités du Message-Passing Interface et permet de paralléliser certains problèmes qui se partitionnent difficilement de manière statique grâce à un système de partitionnement dynamique et de balancement de charge. Pour ce faire, il se base sur le langage Multilisp, un dialecte de Scheme orienté vers le traitement parallèle, et implante sur ce dernier une interface semblable à MPI permettant le calcul distribué multipro- cessus. Ce système offre un langage beaucoup plus riche et expressif que le C et réduit considérablement le travail nécessaire au programmeur pour pouvoir développer des programmes équivalents à ceux en MPI. Enfin, le partitionnement dynamique permet de concevoir des programmes qui seraient très complexes à réaliser sur MPI. Des tests ont été effectués sur un système local à 16 processeurs et une grappe à 16 processeurs et il offre de bonnes accélérations en comparaison à des programmes séquentiels équiva- lents ainsi que des performances acceptables par rapport à MPI. Ce mémoire démontre que l’usage des futures comme technique de partitionnement dynamique est faisable sur des multiprocesseurs à mémoire distribuée.

Annotation syntaxico-sémantique des actants en corpus spécialisé

L’annotation en rôles sémantiques est une tâche qui permet d’attribuer des étiquettes de rôles telles que Agent, Patient, Instrument, Lieu, Destination etc. aux différents participants actants ou circonstants (arguments ou adjoints) d’une lexie prédicative. Cette tâche nécessite des ressources lexicales riches ou des corpus importants contenant des phrases annotées manuellement par des linguistes sur lesquels peuvent s’appuyer certaines approches d’automatisation (statistiques ou apprentissage machine). Les travaux antérieurs dans ce domaine ont porté essentiellement sur la langue anglaise qui dispose de ressources riches, telles que PropBank, VerbNet et FrameNet, qui ont servi à alimenter les systèmes d’annotation automatisés. L’annotation dans d’autres langues, pour lesquelles on ne dispose pas d’un corpus annoté manuellement, repose souvent sur le FrameNet anglais. Une ressource telle que FrameNet de l’anglais est plus que nécessaire pour les systèmes d’annotation automatisé et l’annotation manuelle de milliers de phrases par des linguistes est une tâche fastidieuse et exigeante en temps. Nous avons proposé dans cette thèse un système automatique pour aider les linguistes dans cette tâche qui pourraient alors se limiter à la validation des annotations proposées par le système. Dans notre travail, nous ne considérons que les verbes qui sont plus susceptibles que les noms d’être accompagnés par des actants réalisés dans les phrases. Ces verbes concernent les termes de spécialité d’informatique et d’Internet (ex. accéder, configurer, naviguer, télécharger) dont la structure actancielle est enrichie manuellement par des rôles sémantiques. La structure actancielle des lexies verbales est décrite selon les principes de la Lexicologie Explicative et Combinatoire, LEC de Mel’čuk et fait appel partiellement (en ce qui concerne les rôles sémantiques) à la notion de Frame Element tel que décrit dans la théorie Frame Semantics (FS) de Fillmore. Ces deux théories ont ceci de commun qu’elles mènent toutes les deux à la construction de dictionnaires différents de ceux issus des approches traditionnelles. Les lexies verbales d’informatique et d’Internet qui ont été annotées manuellement dans plusieurs contextes constituent notre corpus spécialisé. Notre système qui attribue automatiquement des rôles sémantiques aux actants est basé sur des règles ou classificateurs entraînés sur plus de 2300 contextes. Nous sommes limités à une liste de rôles restreinte car certains rôles dans notre corpus n’ont pas assez d’exemples annotés manuellement. Dans notre système, nous n’avons traité que les rôles Patient, Agent et Destination dont le nombre d’exemple est supérieur à 300. Nous avons crée une classe que nous avons nommé Autre où nous avons rassemblé les autres rôles dont le nombre d’exemples annotés est inférieur à 100. Nous avons subdivisé la tâche d’annotation en sous-tâches : identifier les participants actants et circonstants et attribuer des rôles sémantiques uniquement aux actants qui contribuent au sens de la lexie verbale. Nous avons soumis les phrases de notre corpus à l’analyseur syntaxique Syntex afin d’extraire les informations syntaxiques qui décrivent les différents participants d’une lexie verbale dans une phrase. Ces informations ont servi de traits (features) dans notre modèle d’apprentissage. Nous avons proposé deux techniques pour l’identification des participants : une technique à base de règles où nous avons extrait une trentaine de règles et une autre technique basée sur l’apprentissage machine. Ces mêmes techniques ont été utilisées pour la tâche de distinguer les actants des circonstants. Nous avons proposé pour la tâche d’attribuer des rôles sémantiques aux actants, une méthode de partitionnement (clustering) semi supervisé des instances que nous avons comparée à la méthode de classification de rôles sémantiques. Nous avons utilisé CHAMÉLÉON, un algorithme hiérarchique ascendant.

Une architecture parallèle distribuée et tolérante aux pannes pour le protocole interdomaine BGP au cœur de l’Internet

L’augmentation du nombre d’usagers de l’Internet a entraîné une croissance exponentielle dans les tables de routage. Cette taille prévoit l’atteinte d’un million de préfixes dans les prochaines années. De même, les routeurs au cœur de l’Internet peuvent facilement atteindre plusieurs centaines de connexions BGP simultanées avec des routeurs voisins. Dans une architecture classique des routeurs, le protocole BGP s’exécute comme une entité unique au sein du routeur. Cette architecture comporte deux inconvénients majeurs : l’extensibilité (scalabilité) et la fiabilité. D’un côté, la scalabilité de BGP est mesurable en termes de nombre de connexions et aussi par la taille maximale de la table de routage que l’interface de contrôle puisse supporter. De l’autre côté, la fiabilité est un sujet critique dans les routeurs au cœur de l’Internet. Si l’instance BGP s’arrête, toutes les connexions seront perdues et le nouvel état de la table de routage sera propagé tout au long de l’Internet dans un délai de convergence non trivial. Malgré la haute fiabilité des routeurs au cœur de l’Internet, leur résilience aux pannes est augmentée considérablement et celle-ci est implantée dans la majorité des cas via une redondance passive qui peut limiter la scalabilité du routeur. Dans cette thèse, on traite les deux inconvénients en proposant une nouvelle approche distribuée de BGP pour augmenter sa scalabilité ainsi que sa fiabilité sans changer la sémantique du protocole. L’architecture distribuée de BGP proposée dans la première contribution est faite pour satisfaire les deux contraintes : scalabilité et fiabilité. Ceci est accompli en exploitant adéquatement le parallélisme et la distribution des modules de BGP sur plusieurs cartes de contrôle. Dans cette contribution, les fonctionnalités de BGP sont divisées selon le paradigme « maître-esclave » et le RIB (Routing Information Base) est dupliqué sur plusieurs cartes de contrôle. Dans la deuxième contribution, on traite la tolérance aux pannes dans l’architecture élaborée dans la première contribution en proposant un mécanisme qui augmente la fiabilité. De plus, nous prouvons analytiquement dans cette contribution qu’en adoptant une telle architecture distribuée, la disponibilité de BGP sera augmentée considérablement versus une architecture monolithique. Dans la troisième contribution, on propose une méthode de partitionnement de la table de routage que nous avons appelé DRTP pour diviser la table de BGP sur plusieurs cartes de contrôle. Cette contribution vise à augmenter la scalabilité de la table de routage et la parallélisation de l’algorithme de recherche (Best Match Prefix) en partitionnant la table de routage sur plusieurs nœuds physiquement distribués.

Clustering algorithms and shape factor methods to discriminate among small GTPase phenotypes using DIC image analysis.

Naïvement perçu, le processus d’évolution est une succession d’événements de duplication et de mutations graduelles dans le génome qui mènent à des changements dans les fonctions et les interactions du protéome. La famille des hydrolases de guanosine triphosphate (GTPases) similaire à Ras constitue un bon modèle de travail afin de comprendre ce phénomène fondamental, car cette famille de protéines contient un nombre limité d’éléments qui diffèrent en fonctionnalité et en interactions. Globalement, nous désirons comprendre comment les mutations singulières au niveau des GTPases affectent la morphologie des cellules ainsi que leur degré d’impact sur les populations asynchrones. Mon travail de maîtrise vise à classifier de manière significative différents phénotypes de la levure Saccaromyces cerevisiae via l’analyse de plusieurs critères morphologiques de souches exprimant des GTPases mutées et natives. Notre approche à base de microscopie et d’analyses bioinformatique des images DIC (microscopie d’interférence différentielle de contraste) permet de distinguer les phénotypes propres aux cellules natives et aux mutants. L’emploi de cette méthode a permis une détection automatisée et une caractérisation des phénotypes mutants associés à la sur-expression de GTPases constitutivement actives. Les mutants de GTPases constitutivement actifs Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V ont été analysés avec succès. En effet, l’implémentation de différents algorithmes de partitionnement, permet d’analyser des données qui combinent les mesures morphologiques de population native et mutantes. Nos résultats démontrent que l’algorithme Fuzzy C-Means performe un partitionnement efficace des cellules natives ou mutantes, où les différents types de cellules sont classifiés en fonction de plusieurs facteurs de formes cellulaires obtenus à partir des images DIC. Cette analyse démontre que les mutations Cdc42 Q61L, Rho5 Q91H, Ras1 Q68L et Rsr1 G12V induisent respectivement des phénotypes amorphe, allongé, rond et large qui sont représentés par des vecteurs de facteurs de forme distincts. Ces distinctions sont observées avec différentes proportions (morphologie mutante / morphologie native) dans les populations de mutants. Le développement de nouvelles méthodes automatisées d’analyse morphologique des cellules natives et mutantes s’avère extrêmement utile pour l’étude de la famille des GTPases ainsi que des résidus spécifiques qui dictent leurs fonctions et réseau d’interaction. Nous pouvons maintenant envisager de produire des mutants de GTPases qui inversent leur fonction en ciblant des résidus divergents. La substitution fonctionnelle est ensuite détectée au niveau morphologique grâce à notre nouvelle stratégie quantitative. Ce type d’analyse peut également être transposé à d’autres familles de protéines et contribuer de manière significative au domaine de la biologie évolutive.

Approches bio-informatiques appliquées aux technologies émergentes en génomique

Les études génétiques, telles que les études de liaison ou d’association, ont permis d’acquérir une plus grande connaissance sur l’étiologie de plusieurs maladies affectant les populations humaines. Même si une dizaine de milliers d’études génétiques ont été réalisées sur des centaines de maladies ou autres traits, une grande partie de leur héritabilité reste inexpliquée. Depuis une dizaine d’années, plusieurs percées dans le domaine de la génomique ont été réalisées. Par exemple, l’utilisation des micropuces d’hybridation génomique comparative à haute densité a permis de démontrer l’existence à grande échelle des variations et des polymorphismes en nombre de copies. Ces derniers sont maintenant détectables à l’aide de micropuce d’ADN ou du séquençage à haut débit. De plus, des études récentes utilisant le séquençage à haut débit ont permis de démontrer que la majorité des variations présentes dans l’exome d’un individu étaient rares ou même propres à cet individu. Ceci a permis la conception d’une nouvelle micropuce d’ADN permettant de déterminer rapidement et à faible coût le génotype de plusieurs milliers de variations rares pour un grand ensemble d’individus à la fois. Dans ce contexte, l’objectif général de cette thèse vise le développement de nouvelles méthodologies et de nouveaux outils bio-informatiques de haute performance permettant la détection, à de hauts critères de qualité, des variations en nombre de copies et des variations nucléotidiques rares dans le cadre d’études génétiques. Ces avancées permettront, à long terme, d’expliquer une plus grande partie de l’héritabilité manquante des traits complexes, poussant ainsi l’avancement des connaissances sur l’étiologie de ces derniers. Un algorithme permettant le partitionnement des polymorphismes en nombre de copies a donc été conçu, rendant possible l’utilisation de ces variations structurales dans le cadre d’étude de liaison génétique sur données familiales. Ensuite, une étude exploratoire a permis de caractériser les différents problèmes associés aux études génétiques utilisant des variations en nombre de copies rares sur des individus non reliés. Cette étude a été réalisée avec la collaboration du Wellcome Trust Centre for Human Genetics de l’University of Oxford. Par la suite, une comparaison de la performance des algorithmes de génotypage lors de leur utilisation avec une nouvelle micropuce d’ADN contenant une majorité de marqueurs rares a été réalisée. Finalement, un outil bio-informatique permettant de filtrer de façon efficace et rapide des données génétiques a été implémenté. Cet outil permet de générer des données de meilleure qualité, avec une meilleure reproductibilité des résultats, tout en diminuant les chances d’obtenir une fausse association.

Dynamique des communautés végétales et impacts des perturbations humaines sur la végétation des tourbières.

Ce mémoire visait à comprendre la dynamique temporelle et les patrons floristiques actuels de deux tourbières du sud-ouest du Québec (Small et Large Tea Field) et à identifier les facteurs anthropiques, environnementaux et spatiaux sous-jacents. Pour répondre aux objectifs, des inventaires floristiques anciens (1985) ont d’abord été comparés à des inventaires récents (2012) puis les patrons actuels et les facteurs sous-jacents ont été identifiés à l’aide d’analyses multi-variables. Mes résultats montrent d’abord qu’un boisement important s’est produit au cours des 30 dernières années dans les tourbières à l’étude, probablement en lien avec le drainage des terres agricoles avoisinantes, diminuant la hauteur de la nappe phréatique. Simultanément, les sphaignes ont proliférées dans le centre des sites s’expliquant par une recolonisation des secteurs ayant brûlés en 1983. D’autre part, mes analyses ont montré que les patrons floristiques actuels étaient surtout liés aux variables environnementales (pH et conductivité de l’eau, épaisseur des dépôts), bien que la variance associée aux activités humaines était aussi significative, notamment dans la tourbière Large (18.6%). Les patrons floristiques ainsi que les variables environnementales et anthropiques explicatives étaient aussi fortement structurés dans l’espace, notamment selon un gradient bordure-centre. Enfin, la diversité béta actuelle était surtout liée à la présence d’espèces non-tourbicoles ou exotiques. Globalement, cette étude a montré que les perturbations humaines passées et actuelles avaient un impact important sur la dynamique et la distribution de la végétation des tourbières Small et Large Tea Field.

Distributed conditional computation

L'objectif de cette thèse est de présenter différentes applications du programme de recherche de calcul conditionnel distribué. On espère que ces applications, ainsi que la théorie présentée ici, mènera à une solution générale du problème d'intelligence artificielle, en particulier en ce qui a trait à la nécessité d'efficience. La vision du calcul conditionnel distribué consiste à accélérer l'évaluation et l'entraînement de modèles profonds, ce qui est très différent de l'objectif usuel d'améliorer sa capacité de généralisation et d'optimisation. Le travail présenté ici a des liens étroits avec les modèles de type mélange d'experts. Dans le chapitre 2, nous présentons un nouvel algorithme d'apprentissage profond qui utilise une forme simple d'apprentissage par renforcement sur un modèle d'arbre de décisions à base de réseau de neurones. Nous démontrons la nécessité d'une contrainte d'équilibre pour maintenir la distribution d'exemples aux experts uniforme et empêcher les monopoles. Pour rendre le calcul efficient, l'entrainement et l'évaluation sont contraints à être éparse en utilisant un routeur échantillonnant des experts d'une distribution multinomiale étant donné un exemple. Dans le chapitre 3, nous présentons un nouveau modèle profond constitué d'une représentation éparse divisée en segments d'experts. Un modèle de langue à base de réseau de neurones est construit à partir des transformations éparses entre ces segments. L'opération éparse par bloc est implémentée pour utilisation sur des cartes graphiques. Sa vitesse est comparée à deux opérations denses du même calibre pour démontrer le gain réel de calcul qui peut être obtenu. Un modèle profond utilisant des opérations éparses contrôlées par un routeur distinct des experts est entraîné sur un ensemble de données d'un milliard de mots. Un nouvel algorithme de partitionnement de données est appliqué sur un ensemble de mots pour hiérarchiser la couche de sortie d'un modèle de langage, la rendant ainsi beaucoup plus efficiente. Le travail présenté dans cette thèse est au centre de la vision de calcul conditionnel distribué émis par Yoshua Bengio. Elle tente d'appliquer la recherche dans le domaine des mélanges d'experts aux modèles profonds pour améliorer leur vitesse ainsi que leur capacité d'optimisation. Nous croyons que la théorie et les expériences de cette thèse sont une étape importante sur la voie du calcul conditionnel distribué car elle cadre bien le problème, surtout en ce qui concerne la compétitivité des systèmes d'experts.

Échantillonnage des distributions continues non uniformes en précision arbitraire et protocole pour l'échantillonnage exact distribué des distributions discrètes quantiques

La thèse est divisée principalement en deux parties. La première partie regroupe les chapitres 2 et 3. La deuxième partie regroupe les chapitres 4 et 5. La première partie concerne l'échantillonnage de distributions continues non uniformes garantissant un niveau fixe de précision. Knuth et Yao démontrèrent en 1976 comment échantillonner exactement n'importe quelle distribution discrète en n'ayant recours qu'à une source de bits non biaisés indépendants et identiquement distribués. La première partie de cette thèse généralise en quelque sorte la théorie de Knuth et Yao aux distributions continues non uniformes, une fois la précision fixée. Une borne inférieure ainsi que des bornes supérieures pour des algorithmes génériques comme l'inversion et la discrétisation figurent parmi les résultats de cette première partie. De plus, une nouvelle preuve simple du résultat principal de l'article original de Knuth et Yao figure parmi les résultats de cette thèse. La deuxième partie concerne la résolution d'un problème en théorie de la complexité de la communication, un problème qui naquit avec l'avènement de l'informatique quantique. Étant donné une distribution discrète paramétrée par un vecteur réel de dimension N et un réseau de N ordinateurs ayant accès à une source de bits non biaisés indépendants et identiquement distribués où chaque ordinateur possède un et un seul des N paramètres, un protocole distribué est établi afin d'échantillonner exactement ladite distribution.

On Space-Time Trade-Off for Montgomery Multipliers over Finite Fields

La multiplication dans le corps de Galois à 2^m éléments (i.e. GF(2^m)) est une opérations très importante pour les applications de la théorie des correcteurs et de la cryptographie. Dans ce mémoire, nous nous intéressons aux réalisations parallèles de multiplicateurs dans GF(2^m) lorsque ce dernier est généré par des trinômes irréductibles. Notre point de départ est le multiplicateur de Montgomery qui calcule A(x)B(x)x^(-u) efficacement, étant donné A(x), B(x) in GF(2^m) pour u choisi judicieusement. Nous étudions ensuite l'algorithme diviser pour régner PCHS qui permet de partitionner les multiplicandes d'un produit dans GF(2^m) lorsque m est impair. Nous l'appliquons pour la partitionnement de A(x) et de B(x) dans la multiplication de Montgomery A(x)B(x)x^(-u) pour GF(2^m) même si m est pair. Basé sur cette nouvelle approche, nous construisons un multiplicateur dans GF(2^m) généré par des trinôme irréductibles. Une nouvelle astuce de réutilisation des résultats intermédiaires nous permet d'éliminer plusieurs portes XOR redondantes. Les complexités de temps (i.e. le délais) et d'espace (i.e. le nombre de portes logiques) du nouveau multiplicateur sont ensuite analysées: 1. Le nouveau multiplicateur demande environ 25% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito lorsque GF(2^m) est généré par des trinômes irréductible et m est suffisamment grand. Le nombre de portes du nouveau multiplicateur est presque identique à celui du multiplicateur de Karatsuba proposé par Elia. 2. Le délai de calcul du nouveau multiplicateur excède celui des meilleurs multiplicateurs d'au plus deux évaluations de portes XOR. 3. Nous determinons le délai et le nombre de portes logiques du nouveau multiplicateur sur les deux corps de Galois recommandés par le National Institute of Standards and Technology (NIST). Nous montrons que notre multiplicateurs contient 15% moins de portes logiques que les multiplicateurs de Montgomery et de Mastrovito au coût d'un délai d'au plus une porte XOR supplémentaire. De plus, notre multiplicateur a un délai d'une porte XOR moindre que celui du multiplicateur d'Elia au coût d'une augmentation de moins de 1% du nombre total de portes logiques.

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.

Analysis of intrinsic cardiac neuron activity in relation to neurogenic atrial fibrillation and vagal stimulation

La fibrillation auriculaire est le trouble du rythme le plus fréquent chez l'homme. Elle conduit souvent à de graves complications telles que l'insuffisance cardiaque et les accidents vasculaires cérébraux. Un mécanisme neurogène de la fibrillation auriculaire mis en évidence. L'induction de tachyarythmie par stimulation du nerf médiastinal a été proposée comme modèle pour étudier la fibrillation auriculaire neurogène. Dans cette thèse, nous avons étudié l'activité des neurones cardiaques intrinsèques et leurs interactions à l'intérieur des plexus ganglionnaires de l'oreillette droite dans un modèle canin de la fibrillation auriculaire neurogène. Ces activités ont été enregistrées par un réseau multicanal de microélectrodes empalé dans le plexus ganglionnaire de l'oreillette droite. L'enregistrement de l'activité neuronale a été effectué continument sur une période de près de 4 heures comprenant différentes interventions vasculaires (occlusion de l'aorte, de la veine cave inférieure, puis de l'artère coronaire descendante antérieure gauche), des stimuli mécaniques (toucher de l'oreillette ou du ventricule) et électriques (stimulation du nerf vague ou des ganglions stellaires) ainsi que des épisodes induits de fibrillation auriculaire. L'identification et la classification neuronale ont été effectuées en utilisant l'analyse en composantes principales et le partitionnement de données (cluster analysis) dans le logiciel Spike2. Une nouvelle méthode basée sur l'analyse en composante principale est proposée pour annuler l'activité auriculaire superposée sur le signal neuronal et ainsi augmenter la précision de l'identification de la réponse neuronale et de la classification. En se basant sur la réponse neuronale, nous avons défini des sous-types de neurones (afférent, efférent et les neurones des circuits locaux). Leur activité liée à différents facteurs de stress nous ont permis de fournir une description plus détaillée du système nerveux cardiaque intrinsèque. La majorité des neurones enregistrés ont réagi à des épisodes de fibrillation auriculaire en devenant plus actifs. Cette hyperactivité des neurones cardiaques intrinsèques suggère que le contrôle de cette activité pourrait aider à prévenir la fibrillation auriculaire neurogène. Puisque la stimulation à basse intensité du nerf vague affaiblit l'activité neuronale cardiaque intrinsèque (en particulier pour les neurones afférents et convergents des circuits locaux), nous avons examiné si cette intervention pouvait être appliquée comme thérapie pour la fibrillation auriculaire. Nos résultats montrent que la stimulation du nerf vague droit a été en mesure d'atténuer la fibrillation auriculaire dans 12 des 16 cas malgré un effet pro-arythmique défavorable dans 1 des 16 cas. L'action protective a diminué au fil du temps et est devenue inefficace après ~ 40 minutes après 3 minutes de stimulation du nerf vague.