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.

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.

Simultaneous observations of reconnection pulses at Cluster and their effects on the cusp aurora seen at Chinese Yellow River Station

While the Cluster spacecraft were located near the high-latitude magnetopause, between 10:10 and 10:40 UT on 16 January 2004, three typical flux transfer event (FTE) signatures were observed. During this interval, simultaneous and conjugated all-sky camera measurements, recorded at Yellow River Station, Svalbard, are available at 630.0 and 557.7nm that show poleward-moving auroral forms (PMAFs), consistent with magnetic reconnection at dayside magnetopause. Simultaneous FTEs seen at the magnetopause mainly move northward, but having duskward (eastward) and tailward velocity components, roughly consistent with the observed direction of motion of the PMAFs in all-sky images. Between the PMAFs meridional keograms, extracted from the all-sky images, show intervals of lower intensity aurora which migrate equatorward just before the PMAFs intensify. This is strong evidence for an equatorward eroding and poleward moving open-closed boundary (OCB) associated with a variable magnetopause reconnection rate under variable IMF conditions. From the durations of the PMAFs we infer that the evolution time of FTEs is 5-11 minutes from its origin on magnetopause to its addition to the polar cap.

Modeling based on the structure of vicilins predicts a histidine cluster in the active site of oxalate oxidase

It is known that germin, which is a marker of the onset of growth in germinating wheat, is an oxalate oxidase, and also that germins possess sequence similarity with legumin and vicilin seed storage proteins. These two pieces of information have been combined in order to generate a 3D model of germin based on the structure of vicilin and to examine the model with regard to a potential oxalate oxidase active site. A cluster of three histidine residues has been located within the conserved beta-barrel structure. While there is a relatively low level of overall sequence similarity between the model and the vicilin structures, the conservation of amino acids important in maintaining the scaffold of the beta-barrel lends confidence to the juxtaposition of the histidine residues. The cluster is similar structurally to those found in copper amine oxidase and other proteins, leading to the suggestion that it defines a metal-binding location within the oxalate oxidase active site. It is also proposed that the structural elements involved in intermolecular interactions in vicilins may play a role in oligomer formation in germin/oxalate oxidase.

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.

Mixture models for capture-recapture count data

The contribution investigates the problem of estimating the size of a population, also known as the missing cases problem. Suppose a registration system is targeting to identify all cases having a certain characteristic such as a specific disease (cancer, heart disease, ...), disease related condition (HIV, heroin use, ...) or a specific behavior (driving a car without license). Every case in such a registration system has a certain notification history in that it might have been identified several times (at least once) which can be understood as a particular capture-recapture situation. Typically, cases are left out which have never been listed at any occasion, and it is this frequency one wants to estimate. In this paper modelling is concentrating on the counting distribution, e.g. the distribution of the variable that counts how often a given case has been identified by the registration system. Besides very simple models like the binomial or Poisson distribution, finite (nonparametric) mixtures of these are considered providing rather flexible modelling tools. Estimation is done using maximum likelihood by means of the EM algorithm. A case study on heroin users in Bangkok in the year 2001 is completing the contribution.

Use of a novel Hill-climbing genetic algorithm in protein folding simulations

We have developed a novel Hill-climbing genetic algorithm (GA) for simulation of protein folding. The program (written in C) builds a set of Cartesian points to represent an unfolded polypeptide's backbone. The dihedral angles determining the chain's configuration are stored in an array of chromosome structures that is copied and then mutated. The fitness of the mutated chain's configuration is determined by its radius of gyration. A four-helix bundle was used to optimise simulation conditions, and the program was compared with other, larger, genetic algorithms on a variety of structures. The program ran 50% faster than other GA programs. Overall, tests on 100 non-redundant structures gave comparable results to other genetic algorithms, with the Hill-climbing program running from between 20 and 50% faster. Examples including crambin, cytochrome c, cytochrome B and hemerythrin gave good secondary structure fits with overall alpha carbon atom rms deviations of between 5 and 5.6 Angstrom with an optimised hydrophobic term in the fitness function. (C) 2003 Elsevier Ltd. All rights reserved.

The syntheses, structures and redox properties of phosphine-gold(I) and triruthenium-carbonyl cluster derivatives of tolans

The syntheses of several ethynyl-gold(I) phosphine substituted tolans (1,2-diaryl acetylenes) of general form [Au(C=CC6H4C=CC6H4X)(PPh3)] are described [X = Me (2a), OMe (2b), CO2Me (2c), NO2 (2d), CN (2e)]. These complexes react readily with [Ru-3(CO) 10(mu-dppm)] to give the heterometallic clusters [Ru3(mu-AuPPh3)(mu-eta(1), eta(2)-C2C6H4C, CC6H4X)(CO)(7)(mu-dppm)] (3a-e). The crystallographically determined molecular structures of 2b, 2d, 2e and 3a-e are reported here, that of 2a having been described on a previous occasion. Structural, spectroscopic and electrochemical studies were conducted and have revealed little electronic interaction between the remote substituent and the organometallic end-caps. (C) 2007 Elsevier B. V. All rights reserved.

Synthesis of a Mn-6 cluster and its self-assembly of an azido-bridged polymer

A rare mu(6)-oxo-centered Mn-6 mixed-valent cluster (1) is prepared and used as a secondary building unit for the self-assembly of its azido-bridged polymeric analogue (2) in a systematic way with the retention of the Mn-6 core of (1). Both complexes are characterized by X-ray single-crystal structure determination. The complex 1 was crystallized in a monoclinic system, space group P2(1), a = 11.252(5) A, b = 20.893(9) A, c = 12.301(6) A, and beta = 115.853(7)degrees, whereas the polymeric analogue was crystallized in an orthorhombic system, space group P2(1)2(1)2(1), a = 13.1941(8) A, b = 14.9897(9) A, and c = 27.8746(14) A. Variable-temperature magnetic behavior showed the presence of strong antiferromagnetic interaction in both cases.

Chromatographic alignment of LC-MS and LC-MS/MS datasets by genetic algorithm feature extraction

Liquid chromatography-mass spectrometry (LC-MS) datasets can be compared or combined following chromatographic alignment. Here we describe a simple solution to the specific problem of aligning one LC-MS dataset and one LC-MS/MS dataset, acquired on separate instruments from an enzymatic digest of a protein mixture, using feature extraction and a genetic algorithm. First, the LC-MS dataset is searched within a few ppm of the calculated theoretical masses of peptides confidently identified by LC-MS/MS. A piecewise linear function is then fitted to these matched peptides using a genetic algorithm with a fitness function that is insensitive to incorrect matches but sufficiently flexible to adapt to the discrete shifts common when comparing LC datasets. We demonstrate the utility of this method by aligning ion trap LC-MS/MS data with accurate LC-MS data from an FTICR mass spectrometer and show how hybrid datasets can improve peptide and protein identification by combining the speed of the ion trap with the mass accuracy of the FTICR, similar to using a hybrid ion trap-FTICR instrument. We also show that the high resolving power of FTICR can improve precision and linear dynamic range in quantitative proteomics. The alignment software, msalign, is freely available as open source.