Computing explanations for interactive constraint-based systems

Constraint programming has emerged as a successful paradigm for modelling combinatorial problems arising from practical situations. In many of those situations, we are not provided with an immutable set of constraints. Instead, a user will modify his requirements, in an interactive fashion, until he is satisfied with a solution. Examples of such applications include, amongst others, model-based diagnosis, expert systems, product configurators. The system he interacts with must be able to assist him by showing the consequences of his requirements. Explanations are the ideal tool for providing this assistance. However, existing notions of explanations fail to provide sufficient information. We define new forms of explanations that aim to be more informative. Even if explanation generation is a very hard task, in the applications we consider, we must manage to provide a satisfactory level of interactivity and, therefore, we cannot afford long computational times. We introduce the concept of representative sets of relaxations, a compact set of relaxations that shows the user at least one way to satisfy each of his requirements and at least one way to relax them, and present an algorithm that efficiently computes such sets. We introduce the concept of most soluble relaxations, maximising the number of products they allow. We present algorithms to compute such relaxations in times compatible with interactivity, achieving this by indifferently making use of different types of compiled representations. We propose to generalise the concept of prime implicates to constraint problems with the concept of domain consequences, and suggest to generate them as a compilation strategy. This sets a new approach in compilation, and allows to address explanation-related queries in an efficient way. We define ordered automata to compactly represent large sets of domain consequences, in an orthogonal way from existing compilation techniques that represent large sets of solutions.

Identifying sources of global contention in constraint satisfaction search

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.

Systematic delay-driven power optimisation and power-driven delay optimisation of combinational circuits

With the proliferation of mobile wireless communication and embedded systems, the energy efficiency becomes a major design constraint. The dissipated energy is often referred as the product of power dissipation and the input-output delay. Most of electronic design automation techniques focus on optimising only one of these parameters either power or delay. Industry standard design flows integrate systematic methods of optimising either area or timing while for power consumption optimisation one often employs heuristics which are characteristic to a specific design. In this work we answer three questions in our quest to provide a systematic approach to joint power and delay Optimisation. The first question of our research is: How to build a design flow which incorporates academic and industry standard design flows for power optimisation? To address this question, we use a reference design flow provided by Synopsys and integrate in this flow academic tools and methodologies. The proposed design flow is used as a platform for analysing some novel algorithms and methodologies for optimisation in the context of digital circuits. The second question we answer is: Is possible to apply a systematic approach for power optimisation in the context of combinational digital circuits? The starting point is a selection of a suitable data structure which can easily incorporate information about delay, power, area and which then allows optimisation algorithms to be applied. In particular we address the implications of a systematic power optimisation methodologies and the potential degradation of other (often conflicting) parameters such as area or the delay of implementation. Finally, the third question which this thesis attempts to answer is: Is there a systematic approach for multi-objective optimisation of delay and power? A delay-driven power and power-driven delay optimisation is proposed in order to have balanced delay and power values. This implies that each power optimisation step is not only constrained by the decrease in power but also the increase in delay. Similarly, each delay optimisation step is not only governed with the decrease in delay but also the increase in power. The goal is to obtain multi-objective optimisation of digital circuits where the two conflicting objectives are power and delay. The logic synthesis and optimisation methodology is based on AND-Inverter Graphs (AIGs) which represent the functionality of the circuit. The switching activities and arrival times of circuit nodes are annotated onto an AND-Inverter Graph under the zero and a non-zero-delay model. We introduce then several reordering rules which are applied on the AIG nodes to minimise switching power or longest path delay of the circuit at the pre-technology mapping level. The academic Electronic Design Automation (EDA) tool ABC is used for the manipulation of AND-Inverter Graphs. We have implemented various combinatorial optimisation algorithms often used in Electronic Design Automation such as Simulated Annealing and Uniform Cost Search Algorithm. Simulated Annealing (SMA) is a probabilistic meta heuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. We used SMA to probabilistically decide between moving from one optimised solution to another such that the dynamic power is optimised under given delay constraints and the delay is optimised under given power constraints. A good approximation to the global optimum solution of energy constraint is obtained. Uniform Cost Search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. We have used Uniform Cost Search Algorithm to search within the AIG network, a specific AIG node order for the reordering rules application. After the reordering rules application, the AIG network is mapped to an AIG netlist using specific library cells. Our approach combines network re-structuring, AIG nodes reordering, dynamic power and longest path delay estimation and optimisation and finally technology mapping to an AIG netlist. A set of MCNC Benchmark circuits and large combinational circuits up to 100,000 gates have been used to validate our methodology. Comparisons for power and delay optimisation are made with the best synthesis scripts used in ABC. Reduction of 23% in power and 15% in delay with minimal overhead is achieved, compared to the best known ABC results. Also, our approach is also implemented on a number of processors with combinational and sequential components and significant savings are achieved.

Biodiscovery of natural products from microbes associated with Irish coastal sponges

Marine sponges have been an abundant source of new metabolites in recent years. The symbiotic association between the bacteria and the sponge has enabled scientists to access the bacterial diversity present within the bacterial/sponge ecosystem. This study has focussed on accessing the bacterial diversity in two Irish coastal marine sponges, namely Amphilectus fucorum and Eurypon major. A novel species from the genus Aquimarina has been isolated from the sponge Amphilectus fucorum. The study has also resulted in the identification of an α–Proteobacteria, Pseudovibrio sp. as a potential producer of antibiotics. Thus a targeted based approach to specifically cultivate Pseudovibrio sp. may prove useful for the development of new metabolites from this particular genus. Bacterial isolates from the marine sponge Haliclona simulans were screened for anti–fungal activity and one isolate namely Streptomyces sp. SM8 displayed activity against all five fungal strains tested. The strain was also tested for anti–bacterial activity and it showed activity against both against B. subtilis and P. aeruginosa. Hence a combinatorial approach involving both biochemical and genomic approaches were employed in an attempt to identify the bioactive compounds with these activities which were being produced by this strain. Culture broths from Streptomyces sp. SM8 were extracted and purified by various techniques such as reverse–phase HPLC, MPLC and ash chromatography. Anti–bacterial activity was observed in a fraction which contained a hydroxylated saturated fatty acid and also another compound with a m/z 227 but further structural elucidation of these compounds proved unsuccessful. The anti–fungal fractions from SM8 were shown to contain antimycin–like compounds, with some of these compounds having different retention times from that of an antimycin standard. A high–throughput assay was developed to screen for novel calcineurin inhibitors using yeast as a model system and three putative bacterial extracts were found to be positive using this screen. One of these extracts from SM8 was subsequently analysed using NMR and the calcineurin inhibition activity was con rmed to belong to a butenolide type compound. A H. simulans metagenomic library was also screened using the novel calcineurin inhibitor high–throughput assay system and eight clones displaying putative calcineurin inhibitory activity were detected. The clone which displayed the best inhibitory activity was subsequently sequenced and following the use of other genetic based approaches it became clear that the inhibition was being caused by a hypothetical protein with similarity to a hypothetical Na+/Ca2+ exchanger protein. The Streptomyces sp. SM8 genome was sequenced from a fragment library using Roche 454 pyrosequencing technology to identify potential secondary metabolism clusters. The draft genome was annotated by IMG/ER using the Prodigal pipeline. The Whole Genome Shotgun project has been deposited at DDBJ/EMBL/GenBank under the accession AMPN00000000. The genome contains genes which appear to encode for several polyketide synthases (PKS), non–ribosomal peptide synthetases (NRPS), terpene and siderophore biosynthesis and ribosomal peptides. Transcriptional analyses led to the identification of three hybrid clusters of which one is predicted to be involved in the synthesis of antimycin, while the functions of the others are as yet unknown. Two NRPS clusters were also identified, of which one may be involved in gramicidin biosynthesis and the function of the other is unknown. A Streptomyces sp. SM8 NRPS antC gene knockout was constructed and extracts from the strain were shown to possess a mild anti–fungal activity when compared to the SM8 wild–type. Subsequent LCMS analysis of antC mutant extracts confirmed the absence of the antimycin in the extract proving that the observed anti–fungal activity may involve metabolite(s) other than antimycin. Anti–bacterial activity in the antC gene knockout strain against P. aeruginosa was reduced when compared to the SM8 wild–type indicating that antimycin may be contributing to the observed anti–bacterial activity in addition to the metabolite(s) already identified during the chemical analyses. This is the first report of antimycins exhibiting anti–bacterial activity against P. aeruginosa. One of the hybrid clusters potentially involved in secondary metabolism in SM8 that displayed high and consistent levels of gene–expression in RNA studies was analysed in an attempt to identify the metabolite being produced by the pathway. A number of unusual features were observed following bioinformatics analysis of the gene sequence of the cluster, including a formylation domain within the NRPS cluster which may add a formyl group to the growing chain. Another unusual feature is the lack of AT domains on two of the PKS modules. Other unusual features observed in this cluster is the lack of a KR domain in module 3 of the cluster and an aminotransferase domain in module 4 for which no clear role has been hypothesised.

Simplified decoding techniques for linear block codes

Error correcting codes are combinatorial objects, designed to enable reliable transmission of digital data over noisy channels. They are ubiquitously used in communication, data storage etc. Error correction allows reconstruction of the original data from received word. The classical decoding algorithms are constrained to output just one codeword. However, in the late 50’s researchers proposed a relaxed error correction model for potentially large error rates known as list decoding. The research presented in this thesis focuses on reducing the computational effort and enhancing the efficiency of decoding algorithms for several codes from algorithmic as well as architectural standpoint. The codes in consideration are linear block codes closely related to Reed Solomon (RS) codes. A high speed low complexity algorithm and architecture are presented for encoding and decoding RS codes based on evaluation. The implementation results show that the hardware resources and the total execution time are significantly reduced as compared to the classical decoder. The evaluation based encoding and decoding schemes are modified and extended for shortened RS codes and software implementation shows substantial reduction in memory footprint at the expense of latency. Hermitian codes can be seen as concatenated RS codes and are much longer than RS codes over the same aphabet. A fast, novel and efficient VLSI architecture for Hermitian codes is proposed based on interpolation decoding. The proposed architecture is proven to have better than Kötter’s decoder for high rate codes. The thesis work also explores a method of constructing optimal codes by computing the subfield subcodes of Generalized Toric (GT) codes that is a natural extension of RS codes over several dimensions. The polynomial generators or evaluation polynomials for subfield-subcodes of GT codes are identified based on which dimension and bound for the minimum distance are computed. The algebraic structure for the polynomials evaluating to subfield is used to simplify the list decoding algorithm for BCH codes. Finally, an efficient and novel approach is proposed for exploiting powerful codes having complex decoding but simple encoding scheme (comparable to RS codes) for multihop wireless sensor network (WSN) applications.

Characterisation of the role of Fas in intestinal inflammation and cancer

Background: The role of Fas (CD95) and its ligand, Fas ligand (FasL/CD95L), is poorly understood in the intestine. Whilst Fas is best studies in terms of its function in apoptosis, recent studies suggest that Fas ligation may mediate additional, non-apoptotic functions such as inflammation. Toll like Receptors (TLRs) play an important role in mediating inflammation and homeostasis in the intestine. Recent studies have shown that a level of crosstalk exists between the Fas and TLR signalling pathways but this has not yet been investigated in the intestine. Aim: The aim of this study was to evaluate potential cross-talk between TLRs and Fas/FasL system in intestinal cancer cells. Results: Treatment with TLR4 and TLR5 ligands, but not ligands for TLR2 and TLR9 increased the expression of Fas and FasL in intestinal cancer cells in vitro. Consistent with this, expression of Fas and FasL was reduced in the distal colon tissue from germ-free (GF), TLR4 and TLR5 knock-out (KO) mice but was unchanged in TLR2KO tissue, suggesting that intestinal cancer cells display a degree of specificity in their ability to upregulate Fas and FasL expression in response to TLR ligation. Expression of both Fas and FasL was significantly reduced in TRIF KO tissue, indicating that signalling via TRIF by TLR4 and TLR5 agonists may be responsible for the induction of Fas and FasL expression in intestinal cancer cells. In addition, modulating Fas signalling using agonistic anti-Fas augmented TLR4 and TLR5-mediated tumour necrosis factor alpha (TNFα) and interleukin 8 (IL)-8 production by intestinal cancer cells, suggesting crosstalk occurs between these receptors in these cells. Furthermore, suppression of Fas in intestinal cancer cells reduced the ability of the intestinal pathogens, Salmonella typhimurium and Listeria monocytogenes to induce the expression of IL-8, suggesting that Fas signalling may play a role in intestinal host defence against pathogens. Inflammation is known to be important in colon tumourigenesis and Fas signalling on intestinal cancer cells has been shown to result in the production of inflammatory mediators. Fas-mediated signalling may therefore play a role in colon cancer development. Suppression of tumour-derived Fas by 85% led to a reduction in the tumour volume and changes in tumour infiltrating macrophages and neutrophils. TLR4 signalling has been shown to play a role in colon cancer via the recruitment and activation of alternatively activated immune cells. Given the crosstalk seen between Fas and TLR4 signalling in intestinal cancer cells in vitro, suppressing Fas signalling may enhance the efficacy of TLR4 antagonism in vivo. TLR4 antagonism resulted in smaller tumours with fewer infiltrating neutrophils. Whilst Fas downregulation did not significantly augment the ability of TLR4 antagonism to reduce the final tumour volume, Fas suppression may augment the anti-tumour effects of TLR4 antagonism as neutrophil infiltration was further reduced upon combinatorial treatment. Conclusion: Together, this study demonstrates evidence of a new role for Fas in the intestinal immune response and that manipulating Fas signalling has potential anti-tumour benefit.