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.

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.

The postfusion structure of baculovirus gp64 supports a unified view of viral fusion machines

Viral fusion proteins mediate the merger of host and viral membranes during cell entry for all enveloped viruses. Baculovirus glycoprotein gp64 (gp64) is unusual in promoting entry into both insect and mammalian cells and is distinct from established class I and class II fusion proteins. We report the crystal structure of its postfusion form, which explains a number of gp64's biological properties including its cellular promiscuity, identifies the fusion peptides and shows it to be the third representative of a new class (III) of fusion proteins with unexpected structural homology with vesicular stomatitis virus G and herpes simplex virus type 1 gB proteins. We show that domains of class III proteins have counterparts in both class I and II proteins, suggesting that all these viral fusion machines are structurally more related than previously thought.

Protein-disulfide isomerase-mediated reduction of two disulfide bonds of HIV envelope glycoprotein 120 occurs post-CXCR4 binding and is required for fusion

The human immunodeficiency virus (HIV) envelope (Env) glycoprotein (gp) 120 is a highly disulfide-bonded molecule that attaches HIV to the lymphocyte surface receptors CD4 and CXCR4. Conformation changes within gp120 result from binding and trigger HIV/cell fusion. Inhibition of lymphocyte surface-associated protein-disulfide isomerase (PDI) blocks HIV/cell fusion, suggesting that redox changes within Env are required. Using a sensitive assay based on a thiol reagent, we show that (i) the thiol content of gp120, either secreted by mammalian cells or bound to a lymphocyte surface enabling CD4 but not CXCR4 binding, was 0.5-1 pmol SH/pmol gp120 (SH/gp120), whereas that of gp120 after its interaction with a surface enabling both CD4 and CXCR4 binding was raised to 4 SH/gp120; (ii) PDI inhibitors prevented this change; and (iii) gp120 displaying 2 SH/gp120 exhibited CD4 but not CXCR4 binding capacity. In addition, PDI inhibition did not impair gp120 binding to receptors. We conclude that on average two of the nine disulfides of gp120 are reduced during interaction with the lymphocyte surface after CXCR4 binding prior to fusion and that cell surface PDI catalyzes this process. Disulfide bond restructuring within Env may constitute the molecular basis of the post-receptor binding conformational changes that induce fusion competence.

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.

Pharmacological analysis of a dopamine D-2Short: G(alpha o) fusion protein expressed in Sf9 cells

A dopamine D-2Short receptor:G(alphao) fusion protein was expressed in Sf9 cells using the baculovirus expression system. [H-3]Spiperone bound to D-2Short:G(alphao) with a pK(d) approximate to 10. Dopamine stimulated the binding of [S-35]guanosine-5'-O-(3-thio)triphosphate (GTPgammaS) to D-2Short:G(alphao) expressed with Gbeta(1)gamma(2) (E-max > 460%; pEC(50) 5.43 +/- 0.06). Most of the putative D-2 antagonists behaved as inverse agonists (suppressing basal [S-35]GTPgammaS binding) at D-2Short:G(alphao)/Gbeta(1)gamma(2) although (-)-suipiride and ziprasidone were neutral antagonists. Competition of [H-3]spiperone binding by dopamine and 10,11-dihydroxy-N-n-propylnorapo-morphine revealed two, binding sites of different affinities, even in the presence of GTP (100 muM). The D-2Short:G(alphao) fusion protein is therefore a good model for characterising D-2 receptors. (C) 2003 Published by Elsevier Science B.V. on behalf of the Federation of European Biochemical Societies.

Amino terminal interaction in the prion protein identified using fusion to green fluorescent protein

In contrast to the well-characterized carboxyl domain, the amino terminal half of the mature cellular prion protein has no defined structure. Here, following fusion of mouse prion protein fragments to green fluorescence protein as a reporter of protein stability, we report extreme variability in fluorescence level that is dependent on the prion fragment expressed. In particular, exposure of the extreme amino terminus in the context of a truncated prion protein molecule led to rapid degradation, whereas the loss of only six amino terminal residues rescued high level fluorescence. Study of the precise endpoints and residue identity associated with high fluorescence suggested a domain within the amino terminal half of the molecule defined by a long-range intramolecular interaction between 23KKRPKP28 and 143DWED146 and dependent upon the anti-parallel beta-sheet ending at residue 169 and normally associated with the structurally defined carboxyl terminal domain. This previously unreported interaction may be significant for understanding prion bioactivity and for structural studies aimed at the complete prion structure.

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.