This thesis is devoted to the study and application of constraint-based metabolic models. The objective was to find simple ways to handle the difficulties that arise in practice due to uncertainty (knowledge is incomplete, there is a lack of measurable variables, and those available are imprecise). With this purpose, tools have been developed to model, analyse, estimate and predict the metabolic behaviour of cells. The document is structured in three parts. First, related literature is revised and summarised. This results in a unified perspective of several methodologies that use constraint-based representations of the cell metabolism. Three outstanding methods are discussed in detail, network-based pathways analysis (NPA), metabolic flux analysis (MFA), and flux balance analysis (FBA). Four types of metabolic pathways are also compared to clarify the subtle differences among them. The second part is devoted to interval methods for constraint-based models. The first contribution is an interval approach to traditional MFA, particularly useful to estimate the metabolic fluxes under data scarcity (FS-MFA). These estimates provide insight on the internal state of cells, which determines the behaviour they exhibit at given conditions. The second contribution is a procedure for monitoring the metabolic fluxes during a cultivation process that uses FS-MFA to handle uncertainty. The third part of the document addresses the use of possibility theory. The main contribution is a possibilistic framework to (a) evaluate model and measurements consistency, and (b) perform flux estimations (Poss-MFA). It combines flexibility on the assumptions and computational efficiency. Poss-MFA is also applied to monitoring fluxes and metabolite concentrations during a cultivation, information of great use for fault-detection and control of industrial processes. Afterwards, the FBA problem is addressed. / Llaneras Estrada, F. (2011). Interval and Possibilistic Methods for Constraint-Based Metabolic Models [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/10528 / Palancia

Le calcul de motifs dans de grandes relations binaires a été très étudié. Un succès emblématique concerne la découverte d'ensembles fréquents et leurs post-traitements pour en dériver des règles d'association. Il s'agit de calculer des motifs dans des relations binaires qui enregistrent quelles sont les propriétés satisfaites par des objets. En fait, de nombreux jeux de données se présentent naturellement comme des relations n-aires (avec n > 2). Par exemple, avec l'ajout de dimensions spatiales et/ou temporelles (lieux et/ou temps où les propriétés sont enregistrées), la relation binaire Objets x Propriétés est étendue à une relation 4-aire Objets x Propriétés x Lieux x Temps. Nous avons généralisé le concept de règle d'association dans un tel contexte multi-dimensionnel. Contrairement aux règles usuelles qui n'impliquent que des sous-ensembles d'un seul domaine de la relation, les prémisses et les conclusions de nos règles peuvent impliquer des sous-ensembles arbitraires de certains domaines. Nous avons conçu des mesures de fréquence et de confiance pour définir la sémantique de telles règles et c'est une contribution significative de cette thèse. Le calcul exhaustif de toutes les règles qui ont des fréquences et confiances suffisantes et l'élimination des règles redondantes ont été étudiés. Nous proposons ensuite d'introduire des disjonctions dans les conclusions des règles, ce qui nécessite de retravailler les définitions des mesures d'intérêt et les questions de redondance. Pour ouvrir un champ d'application original, nous considérons la découverte de règles dans des graphes relationnels dynamiques qui peuvent être codés dans des relations n-aires (n ≥ 3). Une application à l'analyse des usages de bicyclettes dans le système Vélo'v (système de Vélos en libre-service du Grand Lyon) montre quelques usages possibles des règles que nous savons calculer avec nos prototypes logiciels. / Pattern discovery in large binary relations has been extensively studied. An emblematic success in this area concerns frequent itemset mining and its post-processing that derives association rules. In this case, we mine binary relations that encode whether some properties are satisfied or not by some objects. It is however clear that many datasets correspond to n-ary relations where n > 2. For example, adding spatial and/or temporal dimensions (location and/or time when the properties are satisfied by the objects) leads to the 4-ary relation Objects x Properties x Places x Times. Therefore, we study the generalization of association rule mining within arbitrary n-ary relations: the datasets are now Boolean tensors and not only Boolean matrices. Unlike standard rules that involve subsets of only one domain of the relation, in our setting, the head and the body of a rule can include arbitrary subsets of some selected domains. A significant contribution of this thesis concerns the design of interestingness measures for such generalized rules: besides a frequency measures, two different views on rule confidence are considered. The concept of non-redundant rules and the efficient extraction of the non-redundant rules satisfying the minimal frequency and minimal confidence constraints are also studied. To increase the subjective interestingness of rules, we then introduce disjunctions in their heads. It requires to redefine the interestingness measures again and to revisit the redundancy issues. Finally, we apply our new rule discovery techniques to dynamic relational graph analysis. Such graphs can be encoded into n-ary relations (n ≥ 3). Our use case concerns bicycle renting in the Vélo'v system (self-service bicycle renting in Lyon). It illustrates the added-value of some rules that can be computed thanks to our software prototypes.

À l’issue de ce travail de thèse, je propose une approche basée sur le formalisme des modèles à base de contraintes, pour étudier la dynamique d’un système métabolique. En associant l’échantillonnage de l’espace des solutions avec l’utilisation d’une contrainte de « faisabilité » entre les périodes de temps considérées, cette approche permet de modéliser la dynamique d’un système métabolique en prenant en compte la variabilité des mesures expérimentales. La contrainte de faisabilité entre les périodes permet de garantir que chaque « trajectoire solution » correspond à une succession de cartes de flux qui conduit à des cinétiques de concentrations cohérentes avec les mesures expérimentales. Les populations de trajectoires solutions générées autorisent différents types d’analyses. D’une part, les répartitions de flux prédites peuvent être utilisées afin d’estimer les répartitions de flux les plus plausibles au sein du réseau étudié. D’autre part, la distribution des concentrations prédites permet d’évaluer le modèle utilisé pour étudier le réseau métabolique. Le fait que cette approche soit basée sur le formalisme de la modélisation à base de contraintes permet, moyennant l’utilisation de l’hypothèse d’état stationnaire du système, d’étudier des réseaux métaboliques de taille relativement grande, et d’utiliser des données expérimentales qui sont aisément mesurables, par exemple les concentrations en biomasse et en métabolites extracellulaires. Cette approche par « trajectoires solutions » a été utilisée afin d’étudier la dynamique du métabolisme de Corynebacterium glutamicum, lorsqu’elle est cultivée en condition de limitation en biotine. Les résultats obtenus ont permis d’une part d’attester du fonctionnement de la méthode, et d’autre part de proposer plusieurs hypothèses quant aux phénomènes biologiques qui ont lieu pendant cette condition particulière de croissance. / In this thesis, I propose an approach based on the formalism of constraint-based models to study the dynamics of a metabolic system. By combining the sampling of the solutions space and the use of a "feasibility" constraint between the considered time periods, this approach allows to model the dynamic of a metabolic system taking into account the variability of experimental measurements. The feasibility constraint between time periods ensures that each "solution trajectory" corresponds to a succession of flux maps which leads to some kinetics of concentrations that are consistent with the experimental measurements. The generation of a population of solution trajectories allows several analyses. On the one hand, the predicted flux maps can be used to estimate the most plausible flux within the network studied. On the other hand, the distribution of predicted concentrations enables to assess the model used for studying the metabolic network. The fact that this approach is based on the formalism of constraint-based modeling allows, using the steady-state assumption of the system, to study metabolic networks of relatively large size, and to use experimental data that are easily measurable, such as biomass concentration and extracellular metabolites concentration. This approach by "solution trajectories" has been used to study the dynamics of the metabolism of Corynebacterium glutamicum, when grown under biotin-limited condition. The results allowed, first, to attest the functioning of the method, and second, to propose several hypotheses about biological phenomena that take place during this particular growth condition.

Combinatorial problems are ubiquitous in our society and solving such problems efficiently is often crucial. One technique for solving combinatorial problems is constraint-based local search. Its compositional nature together with its efficiency on large problem instances have made this technique particularly attractive. In this thesis we contribute to simplifying the solving of combinatorial problems using constraint-based local search. To provide higher-level modelling options, we introduce set variables and set constraints in local search by extending relevant local search concepts. We also propose a general scheme to follow in order to define what we call natural and balanced constraint measures, and accordingly define such measures for over a dozen set constraints. However, defining such measures for a new constraint is time-consuming and error-prone. To relieve the user from this, we provide generic measures for any set constraint modelled in monadic existential second-order logic. We also theoretically relate these measures to our proposed general scheme, and discuss implementation issues such as incremental algorithms and their worst-case complexities. To enable higher-level search algorithms, we introduce constraint-directed neighbourhoods in local search by proposing new constraint primitives for representing such neighbourhoods. Based on a constraint, possibly modelled in monadic existential second-order logic, these primitives return neighbourhoods with moves that are known in advance to achieve a decrease (or preservation, or increase) of the constraint measures, without the need to iterate over any other moves. We also present a framework for constraint-based local search where one can model and solve combinatorial problems with set variables and set constraints, use any set constraint modelled in monadic existential second-order logic, as well as use constraint-directed neighbourhoods. Experimental results on three real-life problems show the usefulness in practice of our theoretical results: our running times are comparable to the current state-of-the-art approaches to solving the considered problems.

Lors de cette thèse, je me suis intéressée à la modélisation du métabolisme des micro-organismes. Nous nous sommes focalisé sur le métabolisme des petites molécules qui ne prend pas en compte les réactions associées aux macromolécules, telle que la synthèse des protéines.Nous avons ainsi utilisé différents formalismes de modélisation.Tout d'abord, nous avons développé TOTORO où les réseaux métaboliques sont représentés par des hypergraphes dirigés et qui permet d'identifier les réactions ayant participé à une transition métabolique. TOTORO a été utilisé sur un jeu de données sur la levure en présence de cadmium. Nous avons pu montrer que nous retrouvons les mécanismes connus de désintoxication.Ensuite, en utilisant une méthode de modélisation par contraintes, nous discutons d'un développement en cours, KOTOURA, qui propose d'utiliser les connaissances actuelles de concentrations de métabolites entre différentes conditions pour inférer de manière quantitative les possibles asynchronies des réactions lors du passage d'un état stable à un autre. Nous avons testé son implémentation sur des données simulées.Enfin, nous proposons MULTIPUS, une méthode d'extraction d'(hyper)-arbres de Steiner dirigés qui permet de sélectionner les voies métaboliques pour la production de composés au sein d'une communauté bactérienne. Les réseaux métaboliques sont modélisés en utilisant des hypergraphes dirigés et pondérés. Nous proposons un algorithme de programmation dynamique paramétré ainsi qu'une formulation utilisant la programmation par ensemble réponse. Ces deux propositions sont ensuite comparées dans deux cas d'applications / In this PhD work, we proposed to model metabolism. Our focus was to develop generic models, that are not specific to one organism or condition, but are instead based on general assumptions that we tried to validate using data from the literature.We first present TOTORO that uses a qualitative measurement of concentrations in two steady-states to infer the reaction changes that lead to differences in metabolite pools in both conditions.TOTORO enumerates all sub-(hyper)graphs that represent a sufficient explanation for the observed differences in concentrations. We exploit a dataset of Yeast (Saccharomyces cerevisiae) exposed to cadmium and show that we manage to retrieve the known pathways used by the organisms. We then address the same issue, but using a constraint-based programming framework, called KOTOURA, that allows to infer more quantitatively the reaction changes during the perturbed state. We use in this case exact concentration measurements and the stoichiometric matrix, and show on simulated datasets that the overall variations of reaction fluxes can be captured by our formulation.Finally, we propose MULTIPUS, a method to infer microbial communities and metabolic roads to produce specific target compounds from a set of defined substrates. We use in this case a weighted directed hypergraph. We apply MULTIPUS to the production of antibiotics using a consortium composed of an archae and an actinobacteria and show hat their metabolic capacities are complementary. We then infer for another community the excretion of an inhibitory product (acetate) by a 1,3-propanediol (PDO) producer and its consumption by a methanogene archae

Dissertation / This dissertation proposes a generic methodology for evaluating intelligent tutoring systems (ITSs), and applies it to the evaluation of the SQL-Tutor, an ITS for the database language SQL. An examination of the historical development, theory and architecture of intelligent tutoring systems, as well as the theory, architecture and behaviour of the SQL-Tutor sets the context for this study. The characteristics and criteria for evaluating computer-aided instruction (CAl) systems are considered as a background to an in-depth investigation of the characteristics and criteria appropriate for evaluating ITSs. These criteria are categorised along internal and external dimensions with the internal dimension focusing on the intrinsic features and behavioural aspects of ITSs, and the external dimension focusing on its educational impact. Several issues surrounding the evaluation of ITSs namely, approaches, methods, techniques and principles are examined, and integrated within a framework for assessing the added value of ITS technology for instructional purposes. / Educational Studies / M. Sc. (Information Systems)

Cette thèse s'est déroulée dans le cadre du projet ANR FOSTER, "FOuille de données Spatio-Temporelles : application à la compréhension et à la surveillance de l'ERosion" (ANR-2010-COSI-012-02, 2011-2014). Dans ce contexte, nous nous sommes intéressés à la modélisation de données spatio-temporelles dans des graphes enrichis de sorte que des calculs de motifs sur de telles données permettent de formuler des hypothèses intéressantes sur les phénomènes à comprendre. Plus précisément, nous travaillons sur la fouille de motifs dans des graphes relationnels (chaque noeud est identifié de fa\c con unique), attribués (chaque noeud du graphe est décrit par des attributs qui sont ici numériques), et dynamiques (les valeurs des attributs et les relations entre les noeuds peuvent évoluer dans le temps). Nous proposons un nouveau domaine de motifs nommé motifs de co-évolution. Ce sont des triplets d'ensembles de noeuds, d'ensembles de pas de temps et d'ensembles d'attributs signés, c'est à dire des attributs associés à une tendance (croissance,décroissance). L'intérêt de ces motifs est de décrire un sous-ensemble des données qui possède un comportement spécifique et a priori intéressant pour conduire des analyses non triviales. Dans ce but, nous définissons deux types de contraintes, une contrainte sur la structure du graphe et une contrainte sur la co-évolution de la valeur des attributs portés par les noeuds. Pour confirmer la spécificité du motif par rapport au reste des données, nous définissons trois mesures de densité qui tendent à répondre à trois questions. À quel point le comportement des noeuds en dehors du motif est similaire à celui des noeuds du motif ? Quel est le comportement du motif dans le temps, est-ce qu'il apparaît soudainement ? Est-ce que les noeuds du motif ont un comportement similaire seulement sur les attributs du motif ou aussi en dehors ? Nous proposons l'utilisation d'une hiérarchie sur les attributs comme connaissance à priori de l'utilisateur afin d'obtenir des motifs plus généraux et adaptons l'ensemble des contraintes à l'utilisation de cette hiérarchie. Finalement, pour simplifier l'utilisation de l'algorithme par l'utilisateur en réduisant le nombre de seuils à fixer et pour extraire uniquement l'ensemble des motifs les plus intéressants, nous utilisons le concept de ``skyline'' réintroduit récemment dans le domaine de la fouille de données. Nous proposons ainsi trois algorithmes MINTAG, H-MINTAG et Sky-H-MINTAG qui sont complets pour extraire l'ensemble de tous les motifs qui respectent les différentes contraintes. L'étude des propriétés des contraintes (anti-monotonie, monotonie/anti-monotonie par parties) nous permet de les pousser efficacement dans les algorithmes proposés et d'obtenir ainsi des extractions sur des données réelles dans des temps raisonnables. / This thesis was conducted within the project ANR FOSTER, ``Spatio-Temporal Data Mining: application to the understanding and monitoring of erosion'' (ANR-2010-COSI-012-02, 2011-2014). In this context, we are interested in the modeling of spatio- temporal data in enriched graphs so that computation of patterns on such data can be used to formulate interesting hypotheses about phenomena to understand. Specifically, we are working on pattern mining in relational graphs (each vertex is uniquely identified), attributed (each vertex of the graph is described by numerical attributes) and dynamic (attribute values and relations between vertices may change over time). We propose a new pattern domain that has been called co-evolution patterns. These are trisets of vertices, times and signed attributes, i.e., attributes associated with a trend (increasing or decreasing). The interest of these patterns is to describe a subset of the data that has a specific behaviour and a priori interesting to conduct non-trivial analysis. For this purpose, we define two types of constraints, a constraint on the structure of the graph and a constraint on the co-evolution of the value worn by vertices attributes. To confirm the specificity of the pattern with regard to the rest of the data, we define three measures of density that tend to answer to three questions. How similar is the behaviour of the vertices outside the co-evolution pattern to the ones inside it? What is the behaviour of the pattern over time, does it appear suddenly? Does the vertices of the pattern behave similarly only on the attributes of the pattern or even outside? We propose the use of a hierarchy of attributes as an a priori knowledge of the user to obtain more general patterns and we adapt the set of constraints to the use of this hierarchy. Finally, to simplify the use of the algorithm by the user by reducing the number of thresholds to be set and to extract only all the most interesting patterns, we use the concept of ``skyline'' reintroduced recently in the domain of data mining. We propose three constraint-based algorithms, called MINTAG, H-MINTAG and Sky-H-MINTAG, that are complete to extract the set of all patterns that meet the different constraints. These algorithms are based on constraints, i.e., they use the anti-monotonicity and piecewise monotonicity/anti-monotonicity properties to prune the search space and make the computation feasible in practical contexts. To validate our method, we experiment on several sets of data (graphs) created from real-world data.

Thesis submitted for the joint institutional requirements for the double-badged degree of Doctor of Philosophy and Docteur de l'Université de Provence, Spécialité : Informatique. / Thesis (PhD)--Macquarie University, Division of Information and Communication Sciences, Department of Computing, 2008. / Includes bibliography (p. 229-240) and index. / Introduction -- Background -- A model-theoretic framework for PG -- Loose constraint-based parsing -- A computational model for gradience -- Conclusion. / The grammaticality of a sentence has conventionally been treated in a binary way: either a sentence is grammatical or not. A growing body of work, however, focuses on studying intermediate levels of acceptability, sometimes referred to as gradience. To date, the bulk of this work has concerned itself with the exploration of human assessments of syntactic gradience. This dissertation explores the possibility to build a robust computational model that accords with these human judgements. -- We suggest that the concepts of Intersective Gradience and Subsective Gradience introduced by Aarts for modelling graded judgements be extended to cover deviant language. Under such a new model, the problem then raised by gradience is to classify an utterance as a member of a specific category according to its syntactic characteristics. More specifically, we extend Intersective Gradience (IG) so that it is concerned with choosing the most suitable syntactic structure for an utterance among a set of candidates, while Subsective Gradience (SG) is extended to be concerned with calculating to what extent the chosen syntactic structure is typical from the category at stake. IG is addressed in relying on a criterion of optimality, while SG is addressed in rating an utterance according to its grammatical acceptability. As for the required syntactic characteristics, which serve as features for classifying an utterance, our investigation of different frameworks for representing the syntax of natural language shows that they can easily be represented in Model-Theoretic Syntax; we choose to use Property Grammars (PG), which offers to model the characterisation of an utterance. We present here a fully automated solution for modelling syntactic gradience, which characterises any well formed or ill formed input sentence, generates an optimal parse for it, then rates the utterance according to its grammatical acceptability. -- Through the development of such a new model of gradience, the main contribution of this work is three-fold. -- First, we specify a model-theoretic logical framework for PG, which bridges the gap observed in the existing formalisation regarding the constraint satisfaction and constraint relaxation mechanisms, and how they relate to the projection of a category during the parsing process. This new framework introduces the notion of loose satisfaction, along with a formulation in first-order logic, which enables reasoning about the characterisation of an utterance. -- Second, we present our implementation of Loose Satisfaction Chart Parsing (LSCP), a dynamic programming approach based on the above mechanisms, which is proven to always find the full parse of optimal merit. Although it shows a high theoretical worst time complexity, it performs sufficiently well with the help of heuristics to let us experiment with our model of gradience. -- And third, after postulating that human acceptability judgements can be predicted by factors derivable from LSCP, we present a numeric model for rating an utterance according to its syntactic gradience. We measure a good correlation with grammatical acceptability by human judgements. Moreover, the model turns out to outperform an existing one discussed in the literature, which was experimented with parses generated manually. / Mode of access: World Wide Web. / xxviii, 283 p. ill

Dissertation / This dissertation proposes a generic methodology for evaluating intelligent tutoring systems (ITSs), and applies it to the evaluation of the SQL-Tutor, an ITS for the database language SQL. An examination of the historical development, theory and architecture of intelligent tutoring systems, as well as the theory, architecture and behaviour of the SQL-Tutor sets the context for this study. The characteristics and criteria for evaluating computer-aided instruction (CAl) systems are considered as a background to an in-depth investigation of the characteristics and criteria appropriate for evaluating ITSs. These criteria are categorised along internal and external dimensions with the internal dimension focusing on the intrinsic features and behavioural aspects of ITSs, and the external dimension focusing on its educational impact. Several issues surrounding the evaluation of ITSs namely, approaches, methods, techniques and principles are examined, and integrated within a framework for assessing the added value of ITS technology for instructional purposes. / Educational Studies / M. Sc. (Information Systems)

Le test à base de modèles des systèmes réactifs est le processus de vérifier si un système sous test (SUT) est conforme à sa spécification. Il consiste à gérer à la fois la génération des données de test et le calcul de verdicts en utilisant des modèles. Nous spécifions le comportement des systèmes réactifs à l'aide des systèmes de transitions symboliques temporisées à entrée-sortie (TIOSTS). Quand les TIOSTSs sont utilisés pour tester des systèmes avec une interface centralisée, l'utilisateur peut ordonner complètement les événements (i.e., les entrées envoyées au système et les sorties produites). Les interactions entre le testeur et le SUT consistent en des séquences d'entrées et de sortie nommées traces, pouvant être séparées par des durées dans le cadre du test temporisé, pour former ce que l'on appelle des traces temporisées. Les systèmes distribués sont des collections de composants locaux communiquant entre eux et interagissant avec leur environnement via des interfaces physiquement distribuées. Différents événements survenant à ces différentes interfaces ne peuvent plus être ordonnés. Cette thèse concerne le test de conformité des systèmes distribués où un testeur est placé à chaque interface localisée et peut observer ce qui se passe à cette interface. Nous supposons qu'il n'y a pas d’horloge commune mais seulement des horloges locales pour chaque interface. La sémantique de tels systèmes est définie comme des tuples de traces temporisées. Nous considérons une approche du test dans le contexte de la relation de conformité distribuée dtioco. La conformité globale peut être testée dans une architecture de test en utilisant des testeurs locaux sans communication entre eux. Nous proposons un algorithme pour vérifier la communication pour un tuple de traces temporisées en formulant le problème de message-passing en un problème de satisfaction de contraintes (CSP). Nous avons mis en œuvre le calcul des verdicts de test en orchestrant à la fois les algorithmes du test centralisé off-line de chacun des composants et la vérification des communications par le biais d'un solveur de contraintes. Nous avons validé notre approche sur un cas étude de taille significative. / Model-based testing of reactive systems is the process of checking if a System Under Test (SUT) conforms to its model. It consists of handling both test data generation and verdict computation by using models. We specify the behaviour of reactive systems using Timed Input Output Symbolic Transition Systems (TIOSTS) that are timed automata enriched with symbolic mechanisms to handle data. When TIOSTSs are used to test systems with a centralized interface, the user may completely order events occurring at this interface (i.e., inputs sent to the system and outputs produced from it). Interactions between the tester and the SUT are sequences of inputs and outputs named traces, separated by delays in the timed framework, to form so-called timed traces. Distributed systems are collections of communicating local components which interact with their environment at physically distributed interfaces. Interacting with such a distributed system requires exchanging values with it by means of several interfaces in the same testing process. Different events occurring at different interfaces cannot be ordered any more. This thesis focuses on conformance testing for distributed systems where a separate tester is placed at each localized interface and may only observe what happens at this interface. We assume that there is no global clock but only local clocks for each localized interface. The semantics of such systems can be seen as tuples of timed traces. We consider a framework for distributed testing from TIOSTS along with corresponding test hypotheses and a distributed conformance relation called dtioco. Global conformance can be tested in a distributed testing architecture using only local testers without any communication between them. We propose an algorithm to check communication policy for a tuple of timed traces by formulating the verification of message passing in terms of Constraint Satisfaction Problem (CSP). Hence, we were able to implement the computation of test verdicts by orchestrating both localised off-line testing algorithms and the verification of constraints defined by message passing that can be supported by a constraint solver. Lastly, we validated our approach on a real case study of a telecommunications distributed system.