A parallel genetic algorithm for the Steiner Problem in Networks

This paper presents a parallel genetic algorithm to the Steiner Problem in Networks. Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the characteristics of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to build a comparison term for validating deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. On the other hand, the large dimensions of our sample networks require the adoption of a parallel implementation of the Steiner GA, which is able to deal with such large problem instances.

Calibrating flood inundation models: identifying and addressing uncertainty in satellite observed flood extents

Improvements in the resolution of satellite imagery have enabled extraction of water surface elevations at the margins of the flood. Comparison between modelled and observed water surface elevations provides a new means for calibrating and validating flood inundation models, however the uncertainty in this observed data has yet to be addressed. Here a flood inundation model is calibrated using a probabilistic treatment of the observed data. A LiDAR guided snake algorithm is used to determine an outline of a flood event in 2006 on the River Dee, North Wales, UK, using a 12.5m ERS-1 image. Points at approximately 100m intervals along this outline are selected, and the water surface elevation recorded as the LiDAR DEM elevation at each point. With a planar water surface from the gauged upstream to downstream water elevations as an approximation, the water surface elevations at points along this flooded extent are compared to their ‘expected’ value. The pattern of errors between the two show a roughly normal distribution, however when plotted against coordinates there is obvious spatial autocorrelation. The source of this spatial dependency is investigated by comparing errors to the slope gradient and aspect of the LiDAR DEM. A LISFLOOD-FP model of the flood event is set-up to investigate the effect of observed data uncertainty on the calibration of flood inundation models. Multiple simulations are run using different combinations of friction parameters, from which the optimum parameter set will be selected. For each simulation a T-test is used to quantify the fit between modelled and observed water surface elevations. The points chosen for use in this T-test are selected based on their error. The criteria for selection enables evaluation of the sensitivity of the choice of optimum parameter set to uncertainty in the observed data. This work explores the observed data in detail and highlights possible causes of error. The identification of significant error (RMSE = 0.8m) between approximate expected and actual observed elevations from the remotely sensed data emphasises the limitations of using this data in a deterministic manner within the calibration process. These limitations are addressed by developing a new probabilistic approach to using the observed data.

Synthesis of a systolic array genetic algorithm

The paper presents a design for a hardware genetic algorithm which uses a pipeline of systolic arrays. These arrays have been designed using systolic synthesis techniques which involve expressing the algorithm as a set of uniform recurrence relations. The final design divorces the fitness function evaluation from the hardware and can process chromosomes of different lengths, giving the design a generic quality. The paper demonstrates the design methodology by progressively re-writing a simple genetic algorithm, expressed in C code, into a form from which systolic structures can be deduced. This paper extends previous work by introducing a simplification to a previous systolic design for the genetic algorithm. The simplification results in the removal of 2N 2 + 4N cells and reduces the time complexity by 3N + 1 cycles.

The systolic array genetic algorithm, an example of systolic arrays as a reconfigurable design methodology

We advocate the use of systolic design techniques to create custom hardware for Custom Computing Machines. We have developed a hardware genetic algorithm based on systolic arrays to illustrate the feasibility of the approach. The architecture is independent of the lengths of chromosomes used and can be scaled in size to accommodate different population sizes. An FPGA prototype design can process 16 million genes per second.

Time patterns in UK demand for alcohol and tobacco: an application of the EM algorithm

Capturing the pattern of structural change is a relevant task in applied demand analysis, as consumer preferences may vary significantly over time. Filtering and smoothing techniques have recently played an increasingly relevant role. A dynamic Almost Ideal Demand System with random walk parameters is estimated in order to detect modifications in consumer habits and preferences, as well as changes in the behavioural response to prices and income. Systemwise estimation, consistent with the underlying constraints from economic theory, is achieved through the EM algorithm. The proposed model is applied to UK aggregate consumption of alcohol and tobacco, using quarterly data from 1963 to 2003. Increased alcohol consumption is explained by a preference shift, addictive behaviour and a lower price elasticity. The dynamic and time-varying specification is consistent with the theoretical requirements imposed at each sample point. (c) 2005 Elsevier B.V. All rights reserved.

Adaptive approximate Bayesian computation

Sequential techniques can enhance the efficiency of the approximate Bayesian computation algorithm, as in Sisson et al.'s (2007) partial rejection control version. While this method is based upon the theoretical works of Del Moral et al. (2006), the application to approximate Bayesian computation results in a bias in the approximation to the posterior. An alternative version based on genuine importance sampling arguments bypasses this difficulty, in connection with the population Monte Carlo method of Cappe et al. (2004), and it includes an automatic scaling of the forward kernel. When applied to a population genetics example, it compares favourably with two other versions of the approximate algorithm.

Mapping the immune response to the outer domain of a human immunodeficiency virus-1 clade C gp120

The outer domain (OD) of human immunodeficiency virus (HIV)-1 gp120 represents an attractive, if difficult, target for a beneficial immune response to HIV infection. Unlike the entire gp120, the OD is structurally stable and contains the surfaces that interact with both the primary and secondary cellular receptors. The primary strain-specific neutralizing target, the V3 loop, lies within the OD, as do epitopes for two cross-reactive neutralizing monoclonal antibodies (mAbs), b12 and 2G12, and the contact sites for a number of inhibitory lectins. The OD is poorly immunogenic, at least in the context of complete gp120, but purposeful OD immunization can lead to a substantial antibody response. Here, we map the antibody generated following immunization with a clade C OD. In contrast to published data for the clade B OD, the majority of the polyclonal response to the complete clade C OD is to the V3 loop; deletion of the loop substantially reduces immunogenicity. When the loop sequence was substituted for the epitope for 2F5, a well-characterized human cross-neutralizing mAb, a polyclonal response to the epitope was generated. A panel of mAbs against the clade C OD identified two mAbs that reacted with the loop and were neutralizing for clade C but not B isolates. Other mAbs recognized both linear and conformational epitopes in the OD. We conclude that, as for complete gp120, V3 immunodominance is a property of OD immunogens, that the responses can be neutralizing and that it could be exploited for the presentation of other epitopes.

Immunogenicity of the outer domain of a HIV-1 clade C gp120

Background: The possibility that a sub domain of a C clade HIV-1 gp120 could act as an effective immunogen was investigated. To do this, the outer domain ( OD) of gp120(CN54) was expressed and characterized in a construct marked by a re-introduced conformational epitope for MAb 2G12. The expressed sequence showed efficient epitope retention on the isolated ODCN54 suggesting authentic folding. To facilitate purification and subsequent immunogenicity ODCN54 was fused to the Fc domain of human IgGl. Mice were immunised with the resulting fusion proteins and also with gp120(CN54)-Fc and gp120 alone. Results: Fusion to Fc was found to stimulate antibody titre and Fc tagged ODCN54 was substantially more immunogenic than non-tagged gp120. Immunogenicity appeared the result of Fc facilitated antigen processing as immunisation with an Fc domain mutant that reduced binding to the FcR lead to a reduction in antibody titre when compared to the parental sequence. The breadth of the antibody response was assessed by serum reaction with five overlapping fragments of gp120(CN54) expressed as GST fusion proteins in bacteria. A predominant anti-inner domain and anti-V3C3 response was observed following immunisation with gp120(CN54)-Fc and an anti-V3C3 response to the ODCN54-Fc fusion. Conclusion: The outer domain of gp120(CN54) is correctly folded following expression as a C terminal fusion protein. Immunogenicity is substantial when targeted to antigen presenting cells but shows V3 dominance in the polyvalent response. The gp120 outer domain has potential as a candidate vaccine component.