A5068419408- Constraint Satisfaction and Optimization
- Advanced Graph Theory Research
- Data Management and Algorithms
- Complexity and Algorithms in Graphs
- Logic, Reasoning, and Knowledge
- Advanced Algebra and Logic
- Evolution and Genetic Dynamics
- Evolutionary Algorithms and Applications
- Advanced Database Systems and Queries
- Formal Methods in Verification
- Model-Driven Software Engineering Techniques
- Metaheuristic Optimization Algorithms Research
- Computational Geometry and Mesh Generation
- semigroups and automata theory
- Scheduling and Optimization Algorithms
- Optimization and Search Problems
- Evolutionary Game Theory and Cooperation
- Logic, programming, and type systems
- Error Correcting Code Techniques
- Computability, Logic, AI Algorithms
- Machine Learning and Algorithms
- DNA and Biological Computing
- Cryptography and Data Security
- Bioinformatics and Genomic Networks
- Pharmacogenetics and Drug Metabolism
University of Oxford
2012-2021
Science Oxford
2013
Computing Center
2011
University of London
1994-2002
Royal Holloway University of London
1993-1999
Universidad de Londres
1995
Transnational University Limburg
1994
University College London
1994
Universities UK
1994
John Radcliffe Hospital
1987
Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of is known to NP-complete in general, but certain restrictions on the form constraints ensure tractability. Here we show that any set relations used specify allowed forms associated with a finite universal algebra and explore how computational complexity corresponding problem connected properties this algebra. Hence, completely translate classifying restricted into language We introduce...
Many combinatorial search problems can be expressed as “constraint satisfaction problems” and this class of is known to NP-complete in general. In paper, we investigate the subclasses that arise from restricting possible constraint types. We first show any set constraints does not give rise an must satisfy a certain type algebraic closure condition. then all different forms property, establish which these are sufficient ensure tractability. As examples, classes tractable over finite domains...
Abstract Antibiotic resistance represents a growing health crisis that necessitates the immediate discovery of novel treatment strategies. One such strategy is identification collateral sensitivities, wherein evolution under first drug induces susceptibility to second. Here, we report sequential regimens derived from in vitro experiments may have overstated therapeutic benefit, predicting collaterally sensitive response where cross-resistance ultimately occurs. We quantify likelihood this...
The increasing rate of antibiotic resistance and slowing discovery novel treatments presents a growing threat to public health. Here, we consider simple model evolution in asexually reproducing populations which considers adaptation as biased random walk on fitness landscape. This associates the global properties landscape with algebraic Markov chain transition matrix allows us derive general results non-commutativity irreversibility natural selection well cycling strategies. Using this...
Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides final step in classification complexity satisfiability problems over constraints expressed this algebra. When are chosen from full algebra, form problem known to be NP-complete. However, eighteen tractable subalgebras have previously been identified; we show here that these include all possible subsets In other words, contains exactly maximal subalgebras, and reasoning any...
Cancers are complex dynamic systems that undergo evolution and selection. Personalized medicine approaches in the clinic increasingly rely on predictions of tumour response to one or more therapies; these complicated by inevitable tumour. Despite enormous amounts data mutational status cancers numerous therapies developed recent decades target mutations, many treatments fail after a time due development resistance The emergence resistant phenotypes is not easily predicted from genomic data,...
Many combinatorial search problems can be expressed as "constraint satisfaction problems" using an appropriate language", that is, a set of relations over some fixed finite values. It is well-known there trade-off between the expressive power constraint language and complexity it express. In present paper we systematically study all maximal languages, languages whose just weaker than constraints. Using algebraic invariance properties constraints, exhibit strong necessary condition for...
Discrete optimization problems arise in many different areas and are studied under names. In such the quantity to be optimized can expressed as a sum of functions restricted form. Here we present unifying theory complexity for this kind. We show that finite-domain discrete problem is determined by certain algebraic properties objective function, which call weighted polymorphisms. define Galois connection between sets rational-valued polymorphisms how closed characterized. These results...
Nongenetic variation in phenotypes, or bet-hedging, has been observed as a driver of drug resistance both bacterial infections and cancers. Here, we study how bet-hedging emerges genotype-phenotype (GP) mapping through simple interaction model: molecular switch. We use chemical reaction networks to implement stochastic switches that map gene products investigate the impact structurally distinct mappings on evolution phenotypic heterogeneity. Bet-hedging naturally within this model, is robust...
Many combinatorial search problems can be expressed as 'constraint satisfaction problems'. This class of is known to NP-hard in general, but a number restricted constraint classes have been identified which ensure tractability. paper presents the first general results on combining tractable obtain larger, more classes. We give examples show that many classes, from wide variety different contexts, constructed simpler using method. also construct several new not previously identified.