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.

Juvenile-mature wood transition in pine: correlation between wood properties and candidate gene expression profiles

There is a strong desire to exploit transcriptomics data from model species for the genetic improvement of non-model crops. Here, we use gene expression profiles from the commercial model Pinus taeda to identify candidate genes implicated in juvenile-mature wood transition in the non-model relative, P. sylvestris. Re-analysis of 'public domain' SAGE data from xylem tissues of P. taeda revealed 283 mature-abundant and 396 juvenile-abundant tags (P < 0.01), of which 70 and 137, respectively matched to genes with known function. Based on sequence similarity, we then isolated 16 putative homologues of genes that in P. taeda exhibited widest divergence in expression between juvenile and mature samples. Candidate expression levels in P. sylvestris were almost invariably differential between juvenile and mature woody tissue samples among two cohorts of five trees collected from the same seed source and selected for genetic uniformity by genetic distance analysis. However, the direction of differential expression was not always consistent with that described in the original P. taeda SAGE data. Correlation was observed between gene expression and juvenile-mature wood anatomical characteristics by OPLS analysis. Four candidates (alpha-tubulin, porin MIP1, lipid transfer protein and aquaporin like protein) apparently had greatest influence on the wood traits measured. Speculative function of these genes in relation to juvenile-mature wood transition is briefly explored. Thus, we demonstrate the feasibility of exploiting SAGE data from a model species to identify consistently differentially expressed candidates in a related non-model species.

GeneMCL in microarray analysis

Accurately and reliably identifying the actual number of clusters present with a dataset of gene expression profiles, when no additional information on cluster structure is available, is a problem addressed by few algorithms. GeneMCL transforms microarray analysis data into a graph consisting of nodes connected by edges, where the nodes represent genes, and the edges represent the similarity in expression of those genes, as given by a proximity measurement. This measurement is taken to be the Pearson correlation coefficient combined with a local non-linear rescaling step. The resulting graph is input to the Markov Cluster (MCL) algorithm, which is an elegant, deterministic, non-specific and scalable method, which models stochastic flow through the graph. The algorithm is inherently affected by any cluster structure present, and rapidly decomposes a graph into cohesive clusters. The potential of the GeneMCL algorithm is demonstrated with a 5730 gene subset (IGS) of the Van't Veer breast cancer database, for which the clusterings are shown to reflect underlying biological mechanisms. (c) 2005 Elsevier Ltd. All rights reserved.

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.

Linkage disequilibrium assessment via log-linear modeling of SNP haplotype frequencies

Analyses of high-density single-nucleotide polymorphism (SNP) data, such as genetic mapping and linkage disequilibrium (LD) studies, require phase-known haplotypes to allow for the correlation between tightly linked loci. However, current SNP genotyping technology cannot determine phase, which must be inferred statistically. In this paper, we present a new Bayesian Markov chain Monte Carlo (MCMC) algorithm for population haplotype frequency estimation, particulary in the context of LD assessment. The novel feature of the method is the incorporation of a log-linear prior model for population haplotype frequencies. We present simulations to suggest that 1) the log-linear prior model is more appropriate than the standard coalescent process in the presence of recombination (>0.02cM between adjacent loci), and 2) there is substantial inflation in measures of LD obtained by a "two-stage" approach to the analysis by treating the "best" haplotype configuration as correct, without regard to uncertainty in the recombination process. Genet Epidemiol 25:106-114, 2003. (C) 2003 Wiley-Liss, Inc.

13C-2H correlation NMR spectroscopy studies of the in vivo transformations of natural products from Artemisia annua

13C-2H correlation NMR spectroscopy (13C-2H COSY) permits the identification of 13C and 2H nuclei which are connected to one another by a single chemical bond via the sizeable 1JCD coupling constant. The practical development of this technique is described using a 13C-2H COSY pulse sequence which is derived from the classical 13C-1H correlation experiment. An example is given of the application of 13C-2H COSY to the study of the biogenesis of natural products from the anti-malarial plant Artemisia annua, using a doubly-labelled precursor molecule. Although the biogenesis of artemisinin, the anti-malarial principle from this species, has been extensively studied over the past twenty years there is still no consensus as to the true biosynthetic route to this important natural product – indeed, some published experimental results are directly contradictory. One possible reason for this confusion may be the ease with which some of the metabolites from A. annua undergo spontaneous autoxidation, as exemplified by our recent in vitro studies of the spontaneous autoxidation of dihydroartemisinic acid, and the application of 13C-2H COSY to this biosynthetic problem has been important in helping to mitigate against such processes. In this in vivo application of 13C-2H COSY, [15-13C2H3]-dihydroartemisinic acid (the doubly-labelled analogue of the natural product from this species which was obtained through synthesis) was fed to A. annua plants and was shown to be converted into several natural products which have been described previously, including artemisinin. It is proposed that all of these transformations occurred via a tertiary hydroperoxide intermediate, which is derived from dihyroartemisinic acid. This intermediate was observed directly in this feeding experiment by the 13C-2H COSY technique; its observation by more traditional procedures (e.g., chromatographic separation, followed by spectroscopic analysis of the purified product) would have been difficult owing to the instability of the hydroperoxide group (as had been established previously by our in vitro studies of the spontaneous autoxidation of dihydroartemisinic acid). This same hydroperoxide has been reported as the initial product of the spontaneous autoxidation of dihydroartemisinic acid in our previous in vitro studies. Its observation in this feeding experiment by the 13C-2H COSY technique, a procedure which requires the minimum of sample manipulation in order to achieve a reliable identification of metabolites (based on both 13C and 2H chemical shifts at the 15-position), provides the best possible evidence for its status as a genuine biosynthetic intermediate, rather than merely as an artifact of the experimental procedure.

Correlation-type structure activity relationships for the kinetics of gas-phase RO2 self-reactions and reaction with HO2

Structure activity relationships (SARs) are presented for the gas-phase reactions of RO2 with HO2, and the self- and cross-reactions of RO2. For RO2+HO2 the SAR is based upon a correlation between the logarithm of the measured rate coefficient and a calculated ionisation potential for the molecule R-CH=CH2, R being the same group in both the radical and molecular analogue. The correlation observed is strong and only for one RO2 species does the measured rate coefficient deviate by more than a factor of two from the linear least-squares regression line. For the self- and cross-reactions of RO2 radicals, the SAR is based upon a correlation between the logarithm of the measured rate coefficient and the calculated electrostatic potential (ESP) at the equivalent carbon atom in the RH molecule to which oxygen is attached in RO2, again R being the same group in the molecule and the radical. For cases where R is a simple alkyl-group, a strong linear correlation observed. For RO2 radicals which contain lone pair-bearing substituents and for which the calculated ESP<-0.05 self-reaction rate coefficients appear to be insensitive to the value of the ESP. For RO2 of this type with ESP>-0.05 a linear relationship between log k and the ESP is again observed. Using the relationships, 84 out of the 85 rate coefficients used to develop the SARs are predicted to within a factor of three of their measured values. A relationship is also presented that allows the prediction of the Arrhenius parameters for the self-reactions of simple alkyl RO2 radicals. On the basis of the correlations, predictions of room-temperature rate coefficients are made for a number of atmospherically important peroxyl-peroxyl radical reactions. (C) 2003 Elsevier Ltd. All rights reserved.

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.

Drug interaction and location in liposomes: correlation with polar surface areas

An important step in liposome characterization is to determine the location of a drug within the liposome. This work thus investigated the interaction of dipalmitoylphosphatidylcholine liposomes with drugs of varied water solubility, polar surface area (PSA) and partition coefficient using high sensitivity differential scanning calorimetry. Lipophilic estradiol (ES) interacted strongest with the acyl chains of the lipid membrane, followed by the somewhat polar 5-fluorouracil (5-FU). Strongly hydrophilic mannitol (MAN) showed no evidence of interaction but water soluble polymers inulin (IN) and an antisense oligonucleotide (OLG), which have very high PSAs, interacted with the lipid head groups. Accordingly, the drugs could be classified as: hydrophilic ones situated in the aqueous core and which may interact with the head groups; those located at the water-bilayer interface with some degree of penetration into the lipid bilayer; those lipophilic drugs constrained within the bilayer. (c) 2004 Elsevier B.V. All rights reserved.

Variable step LMS algorithm using the accumulated instantaneous error concept

The convergence speed of the standard Least Mean Square adaptive array may be degraded in mobile communication environments. Different conventional variable step size LMS algorithms were proposed to enhance the convergence speed while maintaining low steady state error. In this paper, a new variable step LMS algorithm, using the accumulated instantaneous error concept is proposed. In the proposed algorithm, the accumulated instantaneous error is used to update the step size parameter of standard LMS is varied. Simulation results show that the proposed algorithm is simpler and yields better performance than conventional variable step LMS.

Unsupervised genetic algorithm deployed for intrusion detection

This paper represents the first step in an on-going work for designing an unsupervised method based on genetic algorithm for intrusion detection. Its main role in a broader system is to notify of an unusual traffic and in that way provide the possibility of detecting unknown attacks. Most of the machine-learning techniques deployed for intrusion detection are supervised as these techniques are generally more accurate, but this implies the need of labeling the data for training and testing which is time-consuming and error-prone. Hence, our goal is to devise an anomaly detector which would be unsupervised, but at the same time robust and accurate. Genetic algorithms are robust and able to avoid getting stuck in local optima, unlike the rest of clustering techniques. The model is verified on KDD99 benchmark dataset, generating a solution competitive with the solutions of the state-of-the-art which demonstrates high possibilities of the proposed method.

A new algorithm for OFDM joint data detection and phase noise cancellation

This paper proposes a new iterative algorithm for OFDM joint data detection and phase noise (PHN) cancellation based on minimum mean square prediction error. We particularly highlight the problem of "overfitting" such that the iterative approach may converge to a trivial solution. Although it is essential for this joint approach, the overfitting problem was relatively less studied in existing algorithms. In this paper, specifically, we apply a hard decision procedure at every iterative step to overcome the overfitting. Moreover, compared with existing algorithms, a more accurate Pade approximation is used to represent the phase noise, and finally a more robust and compact fast process based on Givens rotation is proposed to reduce the complexity to a practical level. Numerical simulations are also given to verify the proposed algorithm.

A sparse kernel density estimation algorithm using forward constrained regression

Using the classical Parzen window (PW) estimate as the target function, the sparse kernel density estimator is constructed in a forward constrained regression manner. The leave-one-out (LOO) test score is used for kernel selection. The jackknife parameter estimator subject to positivity constraint check is used for the parameter estimation of a single parameter at each forward step. As such the proposed approach is simple to implement and the associated computational cost is very low. An illustrative example is employed to demonstrate that the proposed approach is effective in constructing sparse kernel density estimators with comparable accuracy to that of the classical Parzen window estimate.