Nous étudions, dans cette thèse, le modèle de branchement avec duplication des trajectoires d'abord introduit pour l'étude des événements rares destiné à accélérer la simulation. Dans cette technique, les échantillons sont dupliqués en $R$ copies à différents niveaux pendant la simulation. L'optimisation de l'algorithme à coût fixé suggère de prendre les probabilités de transition entre les niveaux égales à une constante et de dupliquer un nombre égal à l'inverse de cette constante, nombre qui peut être non entier. Nous étudions d'abord la sensibilité de l'erreur relative entre la probabilité d'intérêt $\mathbb{P}(A)$ et <br />son estimateur en fonction de la stratégie adoptée pour avoir des nombres de retirage entiers. <br />Ensuite, puisqu'en pratique les probabilités de transition sont généralement inconnues (et de même pour <br />les nombres de retirages), nous proposons un algorithme en deux étapes pour contourner ce problème. <br />Des applications numériques et comparaisons avec d'autres modèles sont proposés.

Cette thèse porte sur des classes d'objets combinatoires, qui modélisent des données en bio-informatique. Nous étudions notamment deux méthodes de mutation des gènes à l'intérieur du génome : la duplication et l'inversion. Nous étudions d'une part le problème de la duplication-miroir complète avec perte aléatoire en termes de permutations à motifs exclus. Nous démontrons que la classe de permutations obtenue avec cette méthode après p duplications à partir de l'identité est la classe de permutations qui évite les permutations alternées de longueur 2p + 1. Nous énumérons également le nombre de duplications nécessaires et suffisantes pour obtenir une permutation quelconque de longueur n à partir de l'identité. Nous proposons également deux algorithmes efficaces permettant de reconstituer deux chemins différents entre l'identité et une permutation déterminée. Nous donnons enfin des résultats connexes sur d'autres classes proches. La restriction de la relation d'ordre < induite par le code de Gray réfléchi à l'ensemble des compositions et des compositions bornées induit de nouveaux codes de Gray pour ces ensembles. La relation d'ordre < restreinte à l'ensemble des compositions bornées d'un intervalle fournit encore un code de Gray. L'ensemble des ncompositions bornées d'un intervalle généralise simultanément l'ensemble produit et l'ensemble des compositions d'un entier et donc la relation < définit de façon unifiée tous ces codes de Gray. Nous réexprimons les codes de Gray de Walsh et Knuth pour les compositions (bornées) d'un entier à l'aide d'une unique relation d'ordre. Alors, le code de Gray deWalsh pour des classes de compositions et de permutations devient une sous-liste de celui de Knuth, lequel est à son tour une sous-liste du code de Gray réfléchi.

The most abundant organic compound produced by plants is cellulose, however it has long been accepted that animals do not secrete the hydrolytic enzymes required for its degradation, but rely instead on cellulases produced by symbiotic microbes. The recent discovery of an endogenous cDNA transcript encoding a putative GHF9 endoglucanase in the parastacid crayfish Cherax quadricarinatus (Byrne et al., 1999) suggests that similar cellulase genes may have been inherited by a range of crustacean taxa. In this study, the evolutionary history of the C. quadricarinatus endoglucanase gene and the presence of additional GHF9 genes in other decapod species were investigated. The activity of endoglucanase and endoxylanase enzymes within several cultured decapod species were also compared. The evolutionary history of the C. quadricarinatus endoglucanase gene was assessed by comparing intron/exon structure with that of other invertebrate and plant GHF9 genes. The coding region of the gene was found to be interrupted by eleven introns ranging in size from 102-902 bp, the position of which was largely conserved in both termite and abalone GHF9 genes. These structural similarities suggest GHF9 genes in crustaceans and other invertebrate taxa share a common ancestry. In addition, two introns were observed to share similar positions in plant GHF9 genes, which indicates this enzyme class may have been present in ancient eukaryote organisms. The presence of GHF9 genes in C. quadricarinatus and various other decapod species was then explored via degenerate primer PCR. Two distinct GHF9 gene fragments were determined for C. quadricarinatus and several other Cherax and Euastacus parastacid freshwater crayfish species, and a single GHF9 gene fragment was also determined for the palaemonid freshwater prawn Macrobrachium lar. Phylogenetic analyses of these fragments confirmed the presence of two endoglucanase genes within the Parastacidae, termed EG-1 and EG-2. The duplication event that produced these two genes appears to have occurred prior to the evolution of freshwater crayfish. In addition, EG-2 genes appear to have duplicated more recently within the Cherax lineage. The presence of multiple GHF9 endoglucanase enzymes within the digestive tract of some decapod species may enable more efficient processing of cellulose substrates present in dietary plant material. Endoglucanase and endoxylanase enzyme activities were compared in several parastacid crayfish and penaeid prawn species using dye-linked substrates. Endoglucanase activity levels were higher in crayfish compared with prawn species, which corresponds with the known dietary preferences of these taxa. Endoglucanase temperature and pH profiles were found to be very similar for all species examined, with optimum activity occurring at 60°C and pH 5.0. These results suggest endoglucanase activity in penaeid prawns may also be derived from endogenous sources. Additional in vitro studies further demonstrated crayfish and prawn species liberate comparable amounts of glucose from carboxymethyl-cellulose, which indicates both taxa may utilise cellulose substrates as a source of energy. Endoxylanase temperature and pH profiles were also similar for all crayfish species examined, with optimal activity occurring at 50°C and pH 5.0. These results suggest xylanase activity in crayfish may originate from endogenous enzymes, although it is unclear whether this activity is derived from GHF9 enzymes or a different xylanase enzyme class. In contrast, no endoxylanase activity was detected in the three prawn species examined. Together, these findings suggest a wide range of decapod crustacean species may possess endogenous GHF9 endoglucanase genes and enzymes. Endoglucanases may be secreted by various decapod species in order to digest soluble or amorphous cellulose substrates present in consumed plant material. Further biochemical studies may confirm the presence and functional attributes of additional endoglucanase genes and enzymes in decapods, which may ultimately assist in the design of optimal plant based crustacean aquaculture feeds.

À la fois procédé artistico-littéraire et réflexion intellectuelle, la mise en abyme est une des stratégies de création favorites du romancier Umberto Eco. Certains auteurs ont utilisé cette technique uniquement pour de créer de « simples » jeux de miroirs (comme c’est le cas des Nouveaux Romanciers). Chez Umberto Eco, la mise en abyme est destinée à faire saillir aussi bien l’intelligibilité que la structuration de l’oeuvre. Elle est un principe récursif de la génération de figures et de formes narratives fractales : elle est pour ainsi dire le raisonnement servant comme base dans la création d’un univers romanesque par excellence autoréflexif. Selon une représentation très succincte (mais essentielle), la mise en abyme est ce dispositif narratif consistant à insérer un (ou plusieurs) récit(s) dans le Récit, qui, en reproduisant les caractéristiques de ce dernier va (vont) l’illustrer, l’expliquer et mettre en évidence le/les thème(s) de l’oeuvre. / An artistic and literary procedure and, at the same time, an intellectual reflexion, mise en abyme is one of the favorite strategies of creation of the novelist U. Eco. Certain authors have used this technique just to create "simple" games of mirrors (such as the French writers called "Nouveaux Romanciers"). In the case of Umberto Eco, mise en abyme is destined to emphasize both the intelligibility of his work, as well as its being structured in multiple layers of narrativity. We reckon that this is the recursive principle, serving at the generating of fractal shapes and characters: this is therefore the reasoning laying at the foundation of creating a fictional universe self-reflective par excellence. If we want a very concise (but essential) representation, we will say that the mise en abyme is that device consisting of the insertion of one or many more stories into The Story, which, by reproducing the characteristics of the latter, provides us with an explanation and will shed light on the theme / themes of the work.

Embedded and automated tests reduce maintenance costs for embedded systems installed in remote locations. Testing multiple components of an embedded system, connected on a scan chain, using deterministic test patterns stored in a system provide high fault coverage but require large system memory. This thesis presents an approach to reduce test data memory requirements by the use of a test controller program, utilizing the observation of that there are multiple components of the same type in a system. The program use deterministic test patterns specific to every component type, which is stored in system memory, to create fully defined test patterns when needed. By storing deterministic test patterns specific to every component type, the program can use the test patterns for multiple tests and several times within the same test. The program also has the ability to test parts of a system without affecting the normal functional operation of the rest of the components in the system and without an increase of test data memory requirements. Two experiments were conducted to determine how much test data memory requirements are reduced using the approach presented in this thesis. The results for the experiments show up to 26.4% reduction of test data memory requirements for ITC´02 SOC test benchmarks and in average 60% reduction of test data memory requirements for designs generated to gain statistical data.

La connaissance inter-entreprises permet à chaque société de se renseigner sur ses clients, ses fournisseurs et de développer son activité tout en limitant le risque lié à la solvabilité ou retard de paiement de ses partenaires. Avec les tensions de trésorerie, la nécessité de la croissance et l'augmentation de la concurrence, ce domaine devient plus que jamais stratégique aussi bien pour les PME que pour les grands groupes. La quantité de données traitée dans ce domaine, les exigences de qualité et de fraîcheur, la nécessité de croiser ces données pour déduire des nouvelles informations et indicateurs, posent plusieurs problèmes pour lesquels l'optimisation en général et l'optimisation combinatoire en particulier peuvent apporter des solutions efficaces. Dans cette thèse, nous utilisons l'optimisation combinatoire, l'algorithmique du texte et la théorie des graphes pour résoudre efficacement des problèmes issus du domaine de la connaissance inter-entreprises et posés par Altares D&B. Dans un premier temps, nous nous intéressons à la qualité de la base de données des dirigeants. Ce problème combine la détection et suppression des doublons dans une base de données et la détection d'erreurs dans une chaîne de caractères. Nous proposons une méthode de résolution basée sur la normalisation des données et l'algorithmique de texte et de comparaison syntaxique entre deux chaînes de caractères. Les résultats expérimentaux montrent non seulement que cette méthode est pertinente dans la détection et la suppression des doublons mais aussi qu'elle est efficace de point du vue temps de traitement. Nous nous focalisons par la suite sur les données des liens capitalistiques et nous considérons le problème de calcul des liens indirects et l'identification des têtes des groupes. Nous présentons une méthode de résolution basée sur la théorie des graphes. Nous testons cette méthode sur plusieurs instances réelles. Nous prouvons l'efficacité de cette méthode par son temps de traitement et par l'espace de calcul qu'elle utilise. Enfin, nous remarquons que le temps de calcul de celui-ci augmente de façon logarithmique en fonction de la taille d'instance. Enfin, nous considérons le problème de l'identification des réseaux d'influence. Nous formalisons ce problème en termes de graphes et nous le ramenons à un problème de partitionnement de graphe qui est NP-difficile dans ce cas général. Nous proposons alors une formulation en programme linéaire en nombre entier pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires pour que ces contraintes définissent des facettes et discutons des algorithmes de séparations de ces contraintes. En utilisant les résultats polyédraux obtenus, nous développons un algorithme de coupes et branchements. Enfin, nous donnons quelques résultats expérimentaux qui montrent l'efficacité de notre algorithme de coupes et branchements / The inter-companies knowledge allows to every partner to learn about its customers, its suppliers and to develop its activity. Also this permits to limit the risk related to the creditworthiness, or the late payment of its partners. With the cash flow pressures, the need for growth and increased competition, this area becomes more strategic than ever, for both small (PME) and large groups. The amount of data processed in this domain, the requirements of quality and freshness, the need to cross these data to obtain new information and indicators, yield several optimization problems for which the recent techniques and computational tools can bring effective solutions. In this thesis, we use combinatorial optimization, text algorithms as well as graph theory to solve efficiently problems arising in the field of inter-companies knowledge. In particular, such problems was encountered in Altares D&B. First, we focus on the quality of the managers database. This problem combines the detection and removal of duplicates in a database, as well as the error detection in a string. We propose a method for solving this problem, based on data normalization, text algorithms and syntactic comparison between two strings. Our experimental results show that this method is relevant for the detection and removal of duplicates, and it is also very efficient in terms of processing time. In a second part of the thesis, we address a problem related to the data of ownership links. We compute the indirect links, and identify the group heads. We propose a method for solving this problem using graph theory and combinatorial optimization. We then perform a set of experiments on several real-world instances. The computational results show the effectiveness of our method in terms of CPU-time and resource allocation. In fact, the CPU time for computation increases logarithmically with the size of the instances. Finally, we consider the problem of identifying influence networks. We give a description of this problem in terms of graphs, and show that it can reduce to a graph partitioning problem. The latter is NP-hard. We then propose an integer linear programming formulation to model the problem. We investigate the associated polyhedron and describe several classes of valid inequalities. We give some necessaryand sufficient conditions for these inequalities to define facets of the considered polyhedron, and we discuss the related separation problems. Based on the obtained polyhedral results, we devise a Branch-and-Cut algorithm to solve the problem. Some numerical results are presented to show the efficiency of our algorithm.

Dhaka city and Bangladesh is unique in many ways. The country profile is most definitely an interesting case to study through the lenses of disaster management. In this thesis a framework or theories encompassing collaborative governance and coordination crisis- management networks is applied to the challenging context of Bangladesh. The study looks at themes such as ‘history of conflicts’, ‘trust building’, ‘power imbalances’, ‘comprehensive overview’ and crisis network variables like ‘complexity’ and ‘familiarity‘. The theory block is foremost gathered from Michael Hillyard, Naim Kapucu and Alison Gash and Chris Ansell. The study is based on interviews from individuals representing different types of organizations that have connections to coordination avenues. A thematic analysis approach is used to apply the theories on the empirics. Three research questions encapsulates the core of the study; what components stimulate collaborative governance theoretically and how does part- takers of disaster management in Dhaka perceive collaborative governance and coordination under disaster preparedness? Finally, how does the presented theories conform to the practises focused on coordination and collaborative governance when preparing for disasters in Dhaka, Bangladesh?    The study finds that the establishment of coordination avenues are evident in Dhaka and that the development of various parts of coordination activities is moving rather strong. The study show that many organizations are project- based in Dhaka and that competition over intellectual property and funding can work in both directions for coordination and collaborative governance. Either lowering the ambition for collaborations or increasing it. The study also confirms findings of previous coordination studies in Bangladesh that suggest that the institutional approach is very much individualistic which can, to some degree, hamper coordination activities. The study suggest that the system for coordination and its reach appears to be more established horizontally on a strategic level than on the vertical level. Coordination activities and collaborative governance also operates simultaneously in Dhaka, both vertically and horizontally. In closure the experiences of DM- employees in Dhaka suggest that earthquakes and droughts, or combinations of quakes and flooding may pose a serious challenge to the disaster management relief resources of Dhaka city.

Salmonids are a diverse group of fishes whose common ancestor experienced an evolutionarily important whole genome duplication (WGD) event approximately 90 MYA. This event has shaped the evolutionary trajectory of salmonids, and may have contributed to a proliferation of the repeated DNA sequences known as transposable elements (TEs). In this work I characterized repeated DNA in five salmonid genomes. I found that over half of the DNA within each of these genomes was derived from repeats, a value which is amongst the highest of all vertebrates. I investigated repeats of the most abundant TE superfamily, Tc1-Mariner, and found that large proliferative bursts of this element occurred shortly after the WGD and continued during salmonid speciation, where they have produced dramatic differences in TE content among extant salmonid lineages. This work provides important resources for future studies of salmonids, and advances the understanding of two important evolutionary forces: TEs and WGDs. / Graduate / 2019-04-19

O Vírus Respiratório Sincicial Humano (HRSV) é considerado o principal causador de doenças agudas do trato respiratório inferior durante a infância, sendo o principal responsável por um elevado índice de hospitalização de crianças com até cinco anos de idade. Possui distribuição mundial, podendo acometer todas as faixas etárias, entretanto as crianças de 6 semanas a 9 meses são as que desenvolvem problemas mais sérios, como pneumonia e bronquiolite. A epidemia de HRSV apresenta uma sazonalidade bem clara, ocorrendo anualmente no período de outono tardio, inverno ou início da primavera, mas não durante o verão. No presente estudo foi realizada a análise da região G2 da glicoproteína G do HRSV. Um total de 44 amostras positivas para o HRSV do Hospital Universitário (HU) da Universidade de São Paulo (USP), nos anos de 2007-2008, foram seqüenciadas e posteriormente analisadas, sendo então comparadas com seqüências obtidas do NCBI/GeneBank. A análise filogenética mostrou que os genótipos GA2 e GA5, do grupo A, foram os predominantes nos anos de 2007 e 2008, alternando o padrão verificado nos anos anteriores, onde os genótipos do grupo B foram altamente predominantes. A comparação das mutações sinônimas e não sinônimas mostrou uma grande evidência de seleção positiva nos genótipos GA2 e GA5 do grupo A. / Human Respiratory Syncytial Virus (HRSV) is considered the most common cause of lower respiratory tract disease in infants and young children and are the main guilty for the elevated children hospitalizations rate under 5 years of age. The HRSV has a world-wide distribution, being able to attack all the ages however the 6 weeks to 9 months children of are the ones that develop more serious problems as pneumonia and bronquiolite. The HRSV outbreak presents a well defined season, occurring annually in the delayed falls period, winter or springs beginning, but not during the summer. In the present study, we performed a phylogenetic analysis from G2 region of HRSV G glycoprotein. Forty four samples positive for HRSV from University Hospital (UH) of University of Sao Paulo (USP) in 2007-2008, were submitted to sequencing by PCR and compared with GenBank sequences. Phylogenetic analysis revealed that HRSV group A genotypes GA2 and GA5 was the predominant in 2007-2008, alternating the standard verified in the previous years, where the group B genotypes had been highly predominant. Comparison of the synonymous/nonsynonymous mutation ratios showed greater evidence for positive selection pressure for group A genotypes GA2 and GA5.

Adaptive evolution of Toll-like receptors in birds Hana Velová, PhD thesis 6 Abstract Toll-like receptors (TLRs) are one of the key and presumably also evolutionary most original components of animal immune system. As Pattern recognition receptors they form the first line of innate immune defence against various pathogens. The proper receptor binding of pathogenic ligands is crucial for their correct recognition and for subsequent triggering of an appropriate immune response. Because there exists a direct interaction between the receptor surface and the pathogenic ligand, host-pathogen coevolution on molecular level can be predicted. Thus, through variability of their ligands, TLRs are exposed to extensive selective pressures that may be detected on both genetic and protein levels. Surprisingly, the variability we revealed in birds is even higher than previously expected based on the reports from other vertebrates, mainly mammals. In my doctoral thesis I summarise the results of my contribution to the avian TLR research. We were the first who experimentally verify the absence of functional TLR5 in several avian species and duplication of TLR7 in others. We finally resolved the origin of duplication in TLR1 and in TLR2 family. An important part of my research project focused on the prediction of potentially...