The research presented in this thesis is aimed at developing reliable information systems through the application of model-driven and formal techniques. These are techniques in which a precise, formal model of system behaviour is exploited as source code. As such a model may be more abstract, and more concise, than source code written in a conventional programming language, it should be easier and more economical to create, to analyse, and to change. The quality of the model of the system can be ensured through certain kinds of formal analysis and fixed accordingly if necessary. Most valuably, the model serves as the basis for the automated generation or configuration of a working system. This thesis provides four research contributions. The first involves the analysis of a proposed modelling language targeted at the model-driven development of information systems. Logical properties of the language are derived, as are properties of its compiled form---a guarded substitution notation. The second involves the extension of this language, and its semantics, to permit the description of workflows on information systems. Workflows described in this way may be analysed to determine, in advance of execution, the extent to which their concurrent execution may introduce the possibility of deadlock or blocking: a condition that, in this context, is synonymous with a failure to achieve the specified outcome. The third contribution concerns the validation of models written in this language by adapting existing techniques of software testing to the analysis of design models. A methodology is presented for checking model consistency, on the basis of a generated test suite, against the intended requirements. The fourth and final contribution is the presentation of an implementation strategy for the language, targeted at standard, relational databases, and an argument for its correctness, based on a simple, set-theoretic semantics for structure and operations.

Hepatitis C infection is a global disease that causes an estimated 399,000 deaths per year. Treatment has improved dramatically in recent years through the development of direct acting antivirals that target specific regions of the Hepatitis C virus (HCV). Unfortunately the virus can have a preexisting resistance or become resistant to these drugs by mutations in the genes that code for the target proteins. These mutations are called resistance-associated substitutions (RASs). Since RASs can cause treatment failure for patients, resistance detection is performed in clinical practice to select the ideal regimen. Currently RASs are detected by using Sanger sequencing and a partly manual workflow that can discriminate the presence of a RAS if it is present in 15-20% of viruses in a patients blood. A new method with the capacity to detect lower ratios of RASs in HCV sequences was developed, which utilizes Pacific Biosciences’ (PacBio’s) sequencing and a bioinformatics analysis software called CLAMP. To validate this new approach, 123 HCV patient samples were sequenced with both methods and then analyzed. The RASs detected with the new method were congruent to what was found with the Sanger-based workflow. The new approach was also shown to correctly genotype the virus samples, identify any co-existing mutations on the same sequences, and detect if there were any mixed genotype infections in the samples. The new procedure was found to be a valid replacement for the Sanger based workflow, with the possibility to perform additional analyses and perform automated and time efficient RAS detection.

In recent years, combinatorial properties of finite and infinite words have become increasingly important in fields of physics, biology, mathematics, and computer science. In particular, the fascinating family of Sturmian words has become an extremely active subject of research. These infinite binary sequences have numerous applications in various fields of mathematics, such as symbolic dynamics, the study of continued fraction expansion, and also in some domains of physics ( quasicrystal modelling ) and computer science ( pattern recognition, digital straightness ). There has also been a recent surge of interest in a natural generalization of Sturmian words to more than two letters - the so - called episturmian words, which include the well - known Arnoux - Rauzy sequences. This thesis represents a significant contribution to the study of Sturmian and episturmian words, and related objects such as generalized Thue - Morse words and substitutions on a finite alphabet. Specifically, we prove some new properties of certain palindromic factors of the infinite Fibonacci word; establish generalized ' singular ' decompositions of suffixes of certain morphic Sturmian words; completely describe where palindromes occur in characteristic Sturmian words; explicitly determine all integer powers occurring in a certain class of k-strict episturmian words ( including the k-bonacci word ) ; and prove that certain episturmian and generalized Thue - Morse continued fractions are transcendental. Lastly, we begin working towards a proof of a characterization of invertible substitutions on a finite alphabet, which generalizes the fact that invertible substitutions on two letters are exactly the Sturmian morphisms. / Thesis (Ph.D.)--School of Mathematical Sciences, 2006.

Les substitutions explicites ont été introduites comme un raffinement du lambda-calcul, celui-ci étant le<br />formalisme utilisé pour étudier la sémantique des langages de programmation. L'objet de cette thèse<br />est l'étude de leurs propriétés de normalisation forte et de préservation de la normalisation forte. Ce<br />manuscrit rend compte de plusieurs travaux autour de ces propriétés de normalisation, regroupés en<br />trois volets.<br /><br />Le premier d'entre eux formalise une technique générale de preuve de normalisation forte utilisant<br />la préservation de la normalisation forte. On applique cette technique à un spectre assez large de calculs<br />avec substitutions explicites afin de mesurer les limites de son utilisation. Grâce à cette technique, on<br />prouve un résultat nouveau : la normalisation forte du lambda-upsilon-calcul simplement typé.<br /><br />Le deuxième travail est l'étude de la normalisation d'un calcul symétrique non-déterministe issu de<br />la logique classique formulée dans le calcul des séquents, auquel est ajouté des substitutions explicites.<br />La conjonction des problèmes posés par les calculs symétriques et ceux posés par les substitutions<br />explicites semble vouer à l'échec l'utilisation de preuves par réductibilité. On utilise alors la technique<br />formalisée dans le premier travail, ce qui nous demande de prouver tout d'abord la préservation de la<br />normalisation forte. A cette fin, on utilise un fragment de la théorie de la perpétuité dans les systèmes<br />de réécriture.<br /><br />La définition d'une nouvelle version du lambda-ws-calcul avec nom, le lambda-wsn-calcul, constitue le troisième<br />volet de la thèse. Pour prouver sa normalisation forte par traduction et simulation dans les réseaux<br />de preuve, on enrichit l'élimination des coupures de ceux-ci avec une nouvelle règle, ce qui nous oblige<br />à prouver que cette nouvelle notion de réduction est fortement normalisante.

Cette thèse étudie les propriétés calculatoires des présentations d'opérades, ou systèmes de réécriture de diagrammes de Penrose, et leurs liens avec divers types de systèmes de réécriture classiques. Grâce à des nouveaux critères pour la terminaison et la confluence, on démontre la conjecture sur la convergence de la présentation L(Z2) des Z/2Z-espaces vectoriels, une théorie équationnelle commutative. On montre que les présentations d'opérades sont des généralisations des systèmes de réécriture de mots et des réseaux de Petri et qu'elles fournissent un calcul de gestion explicite des ressources pour les systèmes de réécriture de termes linéaires à gauche. Enfin, on étudie les obstructions à ce même résultat concernant le lambda-calcul. Des annexes présentent les liens entre les opérades et d'autres structures de l'algèbre universelle, ainsi qu'un calcul de substitutions explicites.

The study of bacterial evolution is fundamental for addressing current problems of antibiotic resistance and emerging infectious diseases and lays a solid foundation for successful and rational design in biotechnology and synthetic biology. The main aim of this thesis is to test evolutionary hypotheses, largely based on theoretical considerations and sequence analysis, by designing scenarios in a laboratory setting to obtain experimental data. Paper I examines how genomic GC-content can be reduced following a change in mutation rate and spectrum. Transcription-related biases in mutation location were found, but no replicative bias was detected. Paper II explores the distribution of fitness effects of random substitutions in two ribosomal protein genes using a highly sensitive fitness assay. The substitutions had a weakly deleterious effect, with low frequencies of both neutral and inactivating mutations. The surprising finding that synonymous and non-synonymous substitutions have very similar distribution of fitness effects suggests that, at least for these genes, fitness constraints are present mainly on the level of mRNA instead of protein. Paper III examines selective barriers to inter-species gene transfer by constructing mutants with a native gene replaced by an orthologue from another species. Results suggest that the fitness costs of these gene replacements are large enough to provide a barrier to this kind of horizontal gene transfer in nature. The paper also examines possible compensatory mechanisms that can reduce the cost of the poorly functioning alien genes and found that gene amplification acts as a first step to improve the selective contribution after transfer. Paper IV investigates the fitness constraints on horizontal gene transfer by inserting DNA from other species into the Salmonella chromosome. Results suggest that insertion of foreign DNA often is neutral and the manuscript provides new experimental data for theoretical analysis of interspecies genome variation and horizontal gene transfer between species.

Dans cette thèse, nous questionnons l'impact du terrorisme international et des mesures de sûreté sur le comportement des usagers du réseau de transport aérien mondial. A l'aide d'un modèle économétrique, nous analysons une base de données inédite, AirNetTerror, composée de l'ensemble des vols internationaux à destination des Etats-Unis de 1990 à 2006, et des données du terrorisme international par pays sur cette période. La pertinence de notre travail est double. D'une part, nos interrogations sur les comportements des voyageurs et leurs éventuelles substitutions d'itinéraires en lien avec le terrorisme international n'ont, à notre connaissance, jamais été traitées. D'autre part, en abordant le transport aérien sous l'angle du réseau, nous proposons une vision dynamique des répercussions des comportements des usagers en lien avec la menace terroriste et les mesures de sûreté. En particulier, la prise en compte de la situation de sûreté interdépendante régissant le réseau aérien mondial nous permet de questionner l'existence de failles dans les mesures de sûreté. Nos résultats soulignent l'impact avéré et significatif des événements du terrorisme international, mais aussi des mesures de sûreté sur le réseau de transport aérien mondial. De plus, nous observons localement des substitutions d'itinéraires des voyageurs aériens en lien avec ces phénomènes. Ainsi, l'effet combiné de la menace terroriste internationale et des mesures de sûreté semble être à l'origine de ruptures d'équilibre, certes limitées mais réelles, des flux de passagers du réseau de transport aérien mondial. Notre thèse, parce qu'elle place le comportement du voyageur au centre des interactions stratégiques entre les acteurs de la sûreté et les terroristes, permet d'apporter une vision inédite de l'impact du terrorisme international sur le transport aérien.

We review the construction of three Smale spaces associated to a unimodular Pisot substitution on d letters: a subshift of finite type (SFT), a substitution tiling space, and a hyperbolic toral automorphism on the Euclidean d-torus. By considering an SFT whose elements are biinfinite, rather than infinite, paths in the graph associated to the substitution, we modify a well-known map to obtain a factor map between our SFT and the hyperbolic toral automorphism on the d-torus given by the incidence matrix of the substitution. We prove that if the tiling substitution forces its border, then this factor map is the composition of an s-resolving factor map from the SFT to a one-dimensional substitution tiling space and a u-resolving factor map from the tiling space to the d-torus.

We review the construction of three Smale spaces associated to a unimodular Pisot substitution on d letters: a subshift of finite type (SFT), a substitution tiling space, and a hyperbolic toral automorphism on the Euclidean d-torus. By considering an SFT whose elements are biinfinite, rather than infinite, paths in the graph associated to the substitution, we modify a well-known map to obtain a factor map between our SFT and the hyperbolic toral automorphism on the d-torus given by the incidence matrix of the substitution. We prove that if the tiling substitution forces its border, then this factor map is the composition of an s-resolving factor map from the SFT to a one-dimensional substitution tiling space and a u-resolving factor map from the tiling space to the d-torus.

Les produits appartenant à la famille des pyridopyrimidines sont caractérisés par leur intense utilisation dans le domaine pharmacologique, ce qui a poussé différentes équipes de recherche, de par le monde, à les étudier chimiquement et biologiquement. Dans ce travail, nous nous sommes intéressés au groupe des pyridopyrimidines et, plus particulièrement, à l’isomère le moins décrit dans la littérature, à savoir les pyrido[3,2-d]pyrimidines. Les composés ciblés sont synthétisés à partir de la 2,7-dichloropyrido[3,2-d]pyrimidine, via des substitutions nucléophiles aromatiques et des couplages pallado-catalysés et ce, dans le but d’obtenir de puissants inhibiteurs de kinases. Ce but a été atteint puisqu’en effet plusieurs des molécules élaborées inhibent les kinases testées avec des concentrations de l’ordre du nanomolaire. Des résultats pharmacologiques aussi concluants nous ont amenés à étendre nos études à d’autres pyridopyrimidines, à savoir les pyrido[2,3-d]pyrimidines ainsi qu’à d’autres types de bicycles polyazotés, en l’occurrence les imidazo[1,2-a]pyridines et les imidazo[1,2-b]pyridazines. / Products belonging to the pyridopyrimidine family are characterized by their intense use in pharmacology. The increase of interest for this heterocyclic scaffold prompted different research teams around the world to study their chemically and biologically properties. In this work, we are interested in the functionalization of pyridopyrimidines and, more specifically, of the less described regioisomer, namely pyrido[3,2-d]pyrimidines. The target compounds were synthesized from 2,7-dichloropyrido[3,2-d]pyrimidine via nucleophilic aromatic substitution and palladium-catalyzed couplings and, in order to obtain potent kinases inhibitors. Our goal has been achieved with several elaborate molecules. These bioactive compounds inhibit kinases such as Cyclin Dependant Kinases (CDK), Glycogen Synthase 3 (GSK3) or Dual specificity tYRosine-phosphorylation-regulated Kinase 1A (DYRK1A) in the nanomolar range. These biological targets are mainly involved in degenerative process or down syndrome. These pharmacological results led us to extend our studies to other pyridopyrimidines, namely pyrido[2,3-d]pyrimidines as well as other types of polynitrogenated bicycles, namely imidazo[1,2- a]pyridine and imidazo[1,2-b]pyridazine.