An evolutionary approach to the design of experiments for combinatorial optimization with an application to enzyme engineering

In a large number of problems the high dimensionality of the search space, the vast number of variables and the economical constrains limit the ability of classical techniques to reach the optimum of a function, known or unknown. In this thesis we investigate the possibility to combine approaches from advanced statistics and optimization algorithms in such a way to better explore the combinatorial search space and to increase the performance of the approaches. To this purpose we propose two methods: (i) Model Based Ant Colony Design and (ii) Naïve Bayes Ant Colony Optimization. We test the performance of the two proposed solutions on a simulation study and we apply the novel techniques on an appplication in the field of Enzyme Engineering and Design.

Geometric and Combinatorial Aspects of NonEquilibrium Statistical Mechanics

Non-Equilibrium Statistical Mechanics is a broad subject. Grossly speaking, it deals with systems which have not yet relaxed to an equilibrium state, or else with systems which are in a steady non-equilibrium state, or with more general situations. They are characterized by external forcing and internal fluxes, resulting in a net production of entropy which quantifies dissipation and the extent by which, by the Second Law of Thermodynamics, time-reversal invariance is broken. In this thesis we discuss some of the mathematical structures involved with generic discrete-state-space non-equilibrium systems, that we depict with networks in all analogous to electrical networks. We define suitable observables and derive their linear regime relationships, we discuss a duality between external and internal observables that reverses the role of the system and of the environment, we show that network observables serve as constraints for a derivation of the minimum entropy production principle. We dwell on deep combinatorial aspects regarding linear response determinants, which are related to spanning tree polynomials in graph theory, and we give a geometrical interpretation of observables in terms of Wilson loops of a connection and gauge degrees of freedom. We specialize the formalism to continuous-time Markov chains, we give a physical interpretation for observables in terms of locally detailed balanced rates, we prove many variants of the fluctuation theorem, and show that a well-known expression for the entropy production due to Schnakenberg descends from considerations of gauge invariance, where the gauge symmetry is related to the freedom in the choice of a prior probability distribution. As an additional topic of geometrical flavor related to continuous-time Markov chains, we discuss the Fisher-Rao geometry of nonequilibrium decay modes, showing that the Fisher matrix contains information about many aspects of non-equilibrium behavior, including non-equilibrium phase transitions and superposition of modes. We establish a sort of statistical equivalence principle and discuss the behavior of the Fisher matrix under time-reversal. To conclude, we propose that geometry and combinatorics might greatly increase our understanding of nonequilibrium phenomena.

Neurons derived from P19 embryonic carcinoma cells as a platform for biosensor applications - optimisation and characterisation

P19 is a mouse-derived embryonal carcinoma cell line capable of differentiation toward ectodermal, mesodermal and endodermal lineages and could thus be differentiated into neurons. Different culture conditions were tested to optimise and increase the efficiency of neuronal differentiation since the population of P19-derived neurons was reported to be heterogeneous with respect to the morphology and neurotransmitters they synthesise. P19-derived neurons were cultured on microelectrode arrays as cell aggregates and as dissociated cells. Improved neuronal maturation was shown by the presence of microtubule associated protein 2, neurofilament and synaptophysin formation when initiation of neuronal differentiation was prolonged. High initial cell density cultures and coating of surfaces with polyethylenimine-laminin further improved neuronal maturation of differentiated P19 cells. Increased spontaneous activities of the P19-derived neurons were correspondingly recorded. Two to three hours recordings were performed between 17 and 25 days when extracellular signals were stabilised. It was found that P19-derived neurons developed network properties as partially synchronised network activities. P19-derived neurons appeared to give inhomogenous response to the 2 major neurotransmitters, -aminobutyric acid (GABA) and glutamate. The P19-derived neuronal networks obtained from optimised protocol in this thesis were predominantly GABAergic. The reproducible long term extracellular recordings performed showed that neurons derived from P19 embryonal carcinoma cells could be applied as a model for cell based biosensor in corporation with microelectrode arrays.

A multi-objective genetic algorithm optimisation using variable speed pumps in water distribution systems

Due to its practical importance and inherent complexity, the optimisation of distribution networks for supplying drinking water has been the subject of extensive study for the past 30 years. The optimization is governed by sizing the pipes in the water distribution network (WDN) and / or optimises specific parts of the network such as pumps, tanks etc. or try to analyse and optimise the reliability of a WDN. In this thesis, the author has analysed two different WDNs (Anytown City and Cabrera city networks), trying to solve and optimise a multi-objective optimisation problem (MOOP). The main two objectives in both cases were the minimisation of Energy Cost (€) or Energy consumption (kWh), along with the total Number of pump switches (TNps) during a day. For this purpose, a decision support system generator for Multi-objective optimisation used. Its name is GANetXL and has been developed by the Center of Water System in the University of Exeter. GANetXL, works by calling the EPANET hydraulic solver, each time a hydraulic analysis has been fulfilled. The main algorithm used, was a second-generation algorithm for multi-objective optimisation called NSGA_II that gave us the Pareto fronts of each configuration. The first experiment that has been carried out was the network of Anytown city. It is a big network with a pump station of four fixed speed parallel pumps that are boosting the water dynamics. The main intervention was to change these pumps to new Variable speed driven pumps (VSDPs), by installing inverters capable to diverse their velocity during the day. Hence, it’s been achieved great Energy and cost savings along with minimisation in the number of pump switches. The results of the research are thoroughly illustrated in chapter 7, with comments and a variety of graphs and different configurations. The second experiment was about the network of Cabrera city. The smaller WDN had a unique FS pump in the system. The problem was the same as far as the optimisation process was concerned, thus, the minimisation of the energy consumption and in parallel the minimisation of TNps. The same optimisation tool has been used (GANetXL).The main scope was to carry out several and different experiments regarding a vast variety of configurations, using different pump (but this time keeping the FS mode), different tank levels, different pipe diameters and different emitters coefficient. All these different modes came up with a large number of results that were compared in the chapter 8. Concluding, it should be said that the optimisation of WDNs is a very interested field that has a vast space of options to deal with. This includes a large number of algorithms to choose from, different techniques and configurations to be made and different support system generators. The researcher has to be ready to “roam” between these choices, till a satisfactory result will convince him/her that has reached a good optimisation point.

Many-core Algorithms for Combinatorial Optimization

Combinatorial Optimization is becoming ever more crucial, in these days. From natural sciences to economics, passing through urban centers administration and personnel management, methodologies and algorithms with a strong theoretical background and a consolidated real-word effectiveness is more and more requested, in order to find, quickly, good solutions to complex strategical problems. Resource optimization is, nowadays, a fundamental ground for building the basements of successful projects. From the theoretical point of view, Combinatorial Optimization rests on stable and strong foundations, that allow researchers to face ever more challenging problems. However, from the application point of view, it seems that the rate of theoretical developments cannot cope with that enjoyed by modern hardware technologies, especially with reference to the one of processors industry. In this work we propose new parallel algorithms, designed for exploiting the new parallel architectures available on the market. We found that, exposing the inherent parallelism of some resolution techniques (like Dynamic Programming), the computational benefits are remarkable, lowering the execution times by more than an order of magnitude, and allowing to address instances with dimensions not possible before. We approached four Combinatorial Optimization’s notable problems: Packing Problem, Vehicle Routing Problem, Single Source Shortest Path Problem and a Network Design problem. For each of these problems we propose a collection of effective parallel solution algorithms, either for solving the full problem (Guillotine Cuts and SSSPP) or for enhancing a fundamental part of the solution method (VRP and ND). We endorse our claim by presenting computational results for all problems, either on standard benchmarks from the literature or, when possible, on data from real-world applications, where speed-ups of one order of magnitude are usually attained, not uncommonly scaling up to 40 X factors.

Optimisation of chemical lysis protocol for point-of-care leukocyte differentiation

The full blood cell (FBC) count is the most common indicator of diseases. At present hematology analyzers are used for the blood cell characterization, but, recently, there has been interest in using techniques that take advantage of microscale devices and intrinsic properties of cells for increased automation and decreased cost. Microfluidic technologies offer solutions to handling and processing small volumes of blood (2-50 uL taken by finger prick) for point-of-care(PoC) applications. Several PoC blood analyzers are in use and may have applications in the fields of telemedicine, out patient monitoring and medical care in resource limited settings. They have the advantage to be easy to move and much cheaper than traditional analyzers, which require bulky instruments and consume large amount of reagents. The development of miniaturized point-of-care diagnostic tests may be enabled by chip-based technologies for cell separation and sorting. Many current diagnostic tests depend on fractionated blood components: plasma, red blood cells (RBCs), white blood cells (WBCs), and platelets. Specifically, white blood cell differentiation and counting provide valuable information for diagnostic purposes. For example, a low number of WBCs, called leukopenia, may be an indicator of bone marrow deficiency or failure, collagen- vascular diseases, disease of the liver or spleen. The leukocytosis, a high number of WBCs, may be due to anemia, infectious diseases, leukemia or tissue damage. In the laboratory of hybrid biodevices, at the University of Southampton,it was developed a functioning micro impedance cytometer technology for WBC differentiation and counting. It is capable to classify cells and particles on the base of their dielectric properties, in addition to their size, without the need of labeling, in a flow format similar to that of a traditional flow cytometer. It was demonstrated that the micro impedance cytometer system can detect and differentiate monocytes, neutrophils and lymphocytes, which are the three major human leukocyte populations. The simplicity and portability of the microfluidic impedance chip offer a range of potential applications in cell analysis including point-of-care diagnostic systems. The microfluidic device has been integrated into a sample preparation cartridge that semi-automatically performs erythrocyte lysis before leukocyte analysis. Generally erythrocytes are manually lysed according to a specific chemical lysis protocol, but this process has been automated in the cartridge. In this research work the chemical lysis protocol, defined in the patent US 5155044 A, was optimized in order to improve white blood cell differentiation and count performed by the integrated cartridge.

Development and optimisation of novel 68 Ga-folates - towards early diagnosis of ovarian cancer

Der Folsäure-basierte Radiotracer Etarfolatide (99mTc-EC 20) hat in der Vergangenheit sehr vielversprechende Ergebnisse im Bereich der frühzeitigen Diagnostik von Ovarialkarzinomen gezeigt. Einzelphotonen-Emissionscomputertomographie (SPECT) erlaubt dabei eine Visualisierung der Krankheit in einem sehr frühen Stadium – ermöglicht wird dies durch Folsäure, welche als Target Vektor dient. Um das erfolgreiche Prinzip der Radiofolate auf die Positronen-Emissionstomographie (PET) zu übertragen, welche eine noch höhere räumliche Auflösung ermöglicht, wurden in den letzten fünf Jahren bereits 18F-folate entwickelt. Deren hepatobiliären Exkretionsmuster, verursacht durch die relativ hohe Lipophilie der Strukturen, entsprachen jedoch nicht den Anforderungen. Eine optimierte Bioverteilung der Tracer in vivo kann durch eine generelle Erhöhung der Polarität erfolgen. Die Kombination aus einem polaren 68Ga-Komplex mit Folsäure als Target Vektor stellte den Fokus dieses Projektes dar. Ziel war die Entwicklung eines Radiofolates mit der Tendenz einer raschen renalen Ausscheidung und verringerter hepatobiliärer Anreicherung. Dazu wurde Folsäure regiospezifisch über ihre y-Säure an verschiedene bifunktionelle Chelatoren (BFCs) gekoppelt. Vier verschiedene Reaktionstypen wurden gewählt und durchgeführt: Cu-katalysierte sowie Cu-freie Click Reaktion, Amindbindung und Thioharnstoff Bildung. Es wurden sechs verschiedene Derivate erhalten und mit 68Ga radiomarkiert.

Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Characterisation and optimisation of the new Prompt Gamma-ray Activation Analysis (PGAA) facility at FRM II

At the research reactor Forschungs-Neutronenquelle Heinz Maier-Leibnitz (FRM II) a new Prompt Gamma-ray Activation Analysis (PGAA) facility was installed. The instrument was originally built and operating at the spallation source at the Paul Scherrer Institute in Switzerland. After a careful re-design in 2004–2006, the new PGAA instrument was ready for operation at FRM II. In this paper the main characteristics and the current operation conditions of the facility are described. The neutron flux at the sample position can reach up 6.07×1010 [cm−2 s−1], thus the optimisation of some parameters, e.g. the beam background, was necessary in order to achieve a satisfactory analytical sensitivity for routine measurements. Once the optimal conditions were reached, detection limits and sensitivities for some elements, like for example H, B, C, Si, or Pb, were calculated and compared with other PGAA facilities. A standard reference material was also measured in order to show the reliability of the analysis under different conditions at this instrument.

The Choice of Expedient Regulatory Controls on Housing Market Using Short-Term Equilibria Model

Khutoretsky dealt with the problem of maximising a linear utility function (MUF) over the set of short-term equilibria in a housing market by reducing it to a linear programming problem, and suggested a combinatorial algorithm for this problem. Two approaches to the market adjustment were considered: the funding of housing construction and the granting of housing allowances. In both cases, locally optimal regulatory measures can be developed using the corresponding dual prices. The optimal effects (with the regulation expenditures restricted by an amount K) can be found using specialised models based on MUF: a model M1 for choice of the optimum structure of investment in housing construction, and a model M2 for optimum distribution of housing allowances. The linear integer optimisation problems corresponding to these models are initially difficult but can be solved after slight modifications of the parameters. In particular, the necessary modification of K does not exceed the maximum construction cost of one dwelling (for M1) or the maximum size of one housing allowance (for M2). The result is particularly useful since slight modification of K is not essential in practice.