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.

Preparation and properties of gallaborane, GaBH6: structure of the gaseous molecule H2Ga(μ-H)2BH2 as determined by vibrational, electron diffraction, and ab initio studies, and structure of the crystalline solid at 110 K as determined by x-ray diffraction``

Gallaborane (GaBH6, 1), synthesized by the metathesis of LiBH4 with [H2GaCl]n at ca. 250 K, has been characterized by chemical analysis and by its IR and 1H and 11B NMR spectra. The IR spectrum of the vapor at low pressure implies the presence of only one species, viz. H2Ga(μ-H)2BH2, with a diborane-like structure conforming to C2v symmetry. The structure of this molecule has been determined by gas-phase electron diffraction (GED) measurements afforced by the results of ab initio molecular orbital calculations. Hence the principal distances (rα in Å) and angles ( α in deg) are as follows: r(Ga•••B), 2.197(3); r(Ga−Ht), 1.555(6); r(Ga−Hb), 1.800(6); r(B−Ht), 1.189(7); r(B−Hb), 1.286(7); Hb−Ga−Hb, 71.6(4); and Hb−B−Hb, 110.0(5) (t = terminal, b = bridging). Aggregation of the molecules occurs in the condensed phases. X-ray crystallographic studies of a single crystal at 110 K reveal a polymeric network with helical chains made up of alternating pseudotetrahedral GaH4 and BH4 units linked through single hydrogen bridges; the average Ga•••B distance is now 2.473(7) Å. The compound decomposes in the condensed phases at temperatures exceeding ca. 240 K with the formation of elemental Ga and H2 and B2H6. The reactions with NH3, Me3N, and Me3P are also described.

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.

Barley oxalate oxidase is a hexameric protein related to seed storage proteins: evidence from X-ray crystallography

The oxalate oxidase enzyme expressed in barley roots is a thermostable, protease-resistant enzyme that generates H2O2. It has great medical importance because of its use to assay plasma and urinary oxalate, and it has also been used to generate transgenic, pathogen-resistant crops. This protein has now been purified and three types of crystals grown. X-ray analysis shows that the symmetry present in these crystals is consistent with a hexameric arrangement of subunits, probably a trimer of dimers. This structure may be similar to that found in the related seed storage proteins.

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.

Overproduction, purification and preliminary X-ray diffraction analysis of YncE, an iron-regulated Sec-dependent periplasmic protein from Escherichia coli

The yncE gene of Escherichia coli encodes a predicted periplasmic protein of unknown function. The gene is de-repressed under iron restriction through the action of the global iron regulator Fur. This suggests a role in iron acquisition, which is supported by the presence of the adjacent yncD gene encoding a potential TonB-dependent outer-membrane transporter. Here, the preliminary crystallographic structure of YncE is reported, revealing that it consists of a seven-bladed beta-propeller which resembles the corresponding domain of the `surface-layer protein' of Methanosarcina mazei. A full structure determination is under way in order to provide insight into the function of this protein.

Preliminary X-ray diffraction analysis of YcdB from Escherichia coli: a novel haem-containing and Tat-secreted periplasmic protein with a potential role in iron transport

YcdB is a periplasmic haem-containing protein from Escherichia coli that has a potential role in iron transport. It is currently the only reported haem-containing Tat-secreted substrate. Here, the overexpression, purification, crystallization and structure determination at 2.0 angstrom resolution are reported for the apo form of the protein. The apo-YcdB structure resembles those of members of the haem-dependent peroxidase family and thus confirms that YcdB is also a member of this family. Haem-soaking experiments with preformed apo-YcdB crystals have been optimized to successfully generate haem-containing YcdB crystals that diffract to 2.9 angstrom. Completion of model building and structure refinement are under way.

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.

Capillary flow behavior of worm-like micelles studied by small-angle X-ray scattering and small angle light scattering

A novel capillary flow device has been developed and applied to study the orientation of worm-like micelles, among other systems. Small-angle X-ray scattering (SAXS) data from micelles formed by a Pluronic block copolymer in aqueous salt solution provides evidence for the formation of worm-like micelles, which align under flow. A transition from a rod-like form factor to a less persistent conformation is observed under flow. Flow alignment of worm-like micelles formed by the low molar mass amphiphile system cetyl pyridinium chloride+sodium salicylate is studied for comparative purposes. Here, inhomogenous flow at the micron scale is revealed by streaks in the small-angle light scattering pattern perpendicular to the flow direction. Copyright (c) 2006 John Wiley & Sons, Ltd.

Crystal and molecular structure of the thioether-analogue of PEEK from X-ray powder data and diffraction-modelling

Analysis of X-ray powder data for the melt-crystallisable aromatic poly(thioether thioether ketone) [-S-Ar-S-Ar-CO-Ar](n), ('PTTK', Ar= 1,4-phenylene), reveals that it adopts a crystal structure very different from that established for its ether-analogue PEEK. Molecular modelling and diffraction-simulation studies of PTTK show that the structure of this polymer is analogous to that of melt-crystallised poly(thioetherketone) [-SAr-CO-Ar](n) in which the carbonyl linkages in symmetry-related chains are aligned anti-parallel to one another. and that these bridging units are crystallographically interchangeable. The final model for the crystal structure of PTTK is thus disordered, in the monoclinic space group 121a (two chains per unit cell), with cell dimensions a = 7.83, b = 6.06, c = 10.35 angstrom, beta = 93.47 degrees. (c) 2005 Elsevier Ltd. All rights reserved.

First structural analysis of a naphthalene-based poly(ether ketone): Crystal and molecular simulation from X-ray powder data and diffraction modeling

Polycondensation of 2,6-dihydroxynaphthalene with 4,4'-bis(4"-fluorobenzoyl)biphenyl affords a novel, semicrystalline poly(ether ketone) with a melting point of 406 degreesC and glass transition temperature (onset) of 168 degreesC. Molecular modeling and diffraction-simulation studies of this polymer, coupled with data from the single-crystal structure of an oligomer model, have enabled the crystal and molecular structure of the polymer to be determined from X-ray powder data. This structure-the first for any naphthalene-containing poly(ether ketone)-is fully ordered, in monoclinic space group P2(1)/b, with two chains per unit cell. Rietveld refinement against the experimental powder data gave a final agreement factor (R-wp) of 6.7%.

A pressure-jump time-resolved x-ray diffraction study of cubic-cubic transition kinetics in monoolein

In the past two decades, the geometric pathways involved in the transformations between inverse bicontinuous cubic phases in amphiphilic systems have been extensively theoretically modeled. However, little experimental data exists on the cubic-cubic transformation in pure lipid systems. We have used pressure-jump time-resolved X-ray diffraction to investigate the transition between the gyroid Q(II)(G) and double-diamond Q(II)(D) phases in mixtures of 1-monoolein in 30 wt% water. We find for this system that the cubic-cubic transition occurs without any detectable intermediate structures. In addition, we have determined the kinetics of the transition, in both the forward and reverse directions, as a function of pressure-jump amplitude, temperature, and water content. A recently developed model allows (at least in principle) the calculation of the activation energy for lipid phase transitions from such data. The analysis is applicable only if kinetic reproducibility is achieved, at least within one sample, and achievement of such kinetic reproducibility is shown here, by carrying out prolonged pressure-cycling. The rate of transformation shows clear and consistent trends with pressure-jump amplitude, temperature, and water content, all of which are shown to be in agreement with the effect of the shift in the position of the cubic-cubic phase boundary following a change in the thermodynamic parameters.