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.

ASYM20: a program for force constant and normal coordinate calculations, with a critical review of the theory involved

The theory of harmonic force constant refinement calculations is reviewed, and a general-purpose program for force constant and normal coordinate calculations is described. The program, called ASYM20. is available through Quantum Chemistry Program Exchange. It will work on molecules of any symmetry containing up to 20 atoms and will produce results on a series of isotopomers as desired. The vibrational secular equations are solved in either nonredundant valence internal coordinates or symmetry coordinates. As well as calculating the (harmonic) vibrational wavenumbers and normal coordinates, the program will calculate centrifugal distortion constants, Coriolis zeta constants, harmonic contributions to the α′s. root-mean-square amplitudes of vibration, and other quantities related to gas electron-diffraction studies and thermodynamic properties. The program will work in either a predict mode, in which it calculates results from an input force field, or in a refine mode, in which it refines an input force field by least squares to fit observed data on the quantities mentioned above. Predicate values of the force constants may be included in the data set for a least-squares refinement. The program is written in FORTRAN for use on a PC or a mainframe computer. Operation is mainly controlled by steering indices in the input data file, but some interactive control is also implemented.

Change in the effect of constant photoperiods on the rate of sexual maturation in modern genotypes of domestic pullet

1. Data for modern egg-type hybrids reared on constant daylengths show that, as expected, they mature more quickly than earlier genotypes. However, the constant photoperiod which gives earliest sexual maturity has not changed as a result of selection and is 10 h for both early and modern genotypes. 2. Further analysis showed that the rate of delay in sexual maturity for constant photoperiods above 10 h is similar for modern and for early hybrids ( +0.29 d for each incremental one hour of photoperiod), the response of modern hybrids below 10 h ( +4.22 d for each one-hour reduction in photoperiod) is more than double that of early hybrids ( +1.71 d/h).

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.

Modelling heterotachy in phylogenetic inference by reversible-jump Markov chain Monte Carlo

The rate at which a given site in a gene sequence alignment evolves over time may vary. This phenomenon-known as heterotachy-can bias or distort phylogenetic trees inferred from models of sequence evolution that assume rates of evolution are constant. Here, we describe a phylogenetic mixture model designed to accommodate heterotachy. The method sums the likelihood of the data at each site over more than one set of branch lengths on the same tree topology. A branch-length set that is best for one site may differ from the branch-length set that is best for some other site, thereby allowing different sites to have different rates of change throughout the tree. Because rate variation may not be present in all branches, we use a reversible-jump Markov chain Monte Carlo algorithm to identify those branches in which reliable amounts of heterotachy occur. We implement the method in combination with our 'pattern-heterogeneity' mixture model, applying it to simulated data and five published datasets. We find that complex evolutionary signals of heterotachy are routinely present over and above variation in the rate or pattern of evolution across sites, that the reversible-jump method requires far fewer parameters than conventional mixture models to describe it, and serves to identify the regions of the tree in which heterotachy is most pronounced. The reversible-jump procedure also removes the need for a posteriori tests of 'significance' such as the Akaike or Bayesian information criterion tests, or Bayes factors. Heterotachy has important consequences for the correct reconstruction of phylogenies as well as for tests of hypotheses that rely on accurate branch-length information. These include molecular clocks, analyses of tempo and mode of evolution, comparative studies and ancestral state reconstruction. The model is available from the authors' website, and can be used for the analysis of both nucleotide and morphological data.

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 vibrational spectrum and ultimate modulus of polyethylene

We have performed the first completely ab initio lattice dynamics calculation of the full orthorhombic cell of polyethylene using periodic density functional theory in the local density approximation (LDA) and the generalized gradient approximation (GGA). Contrary to current perceptions, we show that LDA accurately describes the structure whereas GGA fails. We emphasize that there is no parametrization of the results. We then rigorously tested our calculation by computing the phonon dispersion curves across the entire Brillouin zone and comparing them to the vibrational spectra, in particular the inelastic neutron scattering (INS) spectra, of polyethylene (both polycrystalline and aligned) and perdeuteriopolyethylene. The F-point frequencies (where the infrared and Raman active modes occur) are in good agreement with the latest low temperature data. The near-perfect reproduction of the INS spectra, gives confidence in the results and allows Lis to deduce a number of physical properties including the elastic moduli, parallel and perpendicular to the chain. We find that the Young's modulus for an infinitely long, perfectly crystalline polyethylene is 360.2 GPa at 0 K. The highest experimental value is 324 GPa, indicating that current high modulus fibers are similar to 90% of their maximum possible strength.

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.

Young's modulus varies with differential orientation of keratin in feathers

Feathers are composed of a structure that, whilst being very light, is able to withstand the large aerodynamic forces exerted upon them during flight. To explore the contribution of molecular orientation to feather keratin mechanical properties, we have examined the nanoscopic organisation of the keratin molecules by X-ray diffraction techniques and have confirmed a link between this and the Young's modulus of the feather rachis. Our results indicate that along the rachis length, from calamus to tip, the keratin molecules become more aligned than at the calamus before returning to a state of higher mis-orientation towards the tip of the rachis. We have also confirmed the general trend of increasing Young's modulus with distance along the rachis. Furthermore, we report a distinct difference in the patterns of orientation of beta-keratin in the feathers of flying and flightless birds. The trend for increased modulus along the feathers of volant birds is absent in the flightless ostrich.

The physics of baking: rheological and polymer molecular structure-function relationships in breadmaking

Molecular size and structure of the gluten polymers that make up the major structural components of wheat are related to their rheological properties via modem polymer rheology concepts. Interactions between polymer chain entanglements and branching are seen to be the key mechanisms determining the rheology of HMW polymers. Recent work confirms the observation that dynamic shear plateau modulus is essentially independent of variations in MW amongst wheat varieties of varying baking performance and is not related to variations in baking performance, and that it is not the size of the soluble glutenin polymers, but the structural and rheological properties of the insoluble polymer fraction that are mainly responsible for variations in baking performance. The rheological properties of gas cell walls in bread doughs are considered to be important in relation to their stability and gas retention during proof and baking, in particular their extensional strain hardening properties. Large deformation rheological properties of gas cell walls were measured using biaxial extension for a number of doughs of varying breadmaking quality at constant strain rate and elevated temperatures in the range 25-60 degrees C. Strain hardening and failure strain of cell walls were both seen to decrease with temperature, with cell walls in good breadmaking doughs remaining stable and retaining their strain hardening properties to higher temperatures (60 degrees C), whilst the cell walls of poor breadmaking doughs became unstable at lower temperatures (45-50 degrees C) and had lower strain hardening. Strain hardening measured at 50 degrees C gave good correlations with baking volume, with the best correlations achieved between those rheological measurements and baking tests which used similar mixing conditions. As predicted by the Considere failure criterion, a strain hardening value of I defines a region below which gas cell walls become unstable, and discriminates well between the baking quality of a range of commercial flour blends of varying quality. This indicates that the stability of gas cell walls during baking is strongly related to their strain hardening properties, and that extensional rheological measurements can be used as predictors of baking quality. (C) 2004 Elsevier B.V. All rights reserved.

The physics of baking: rheological and polymer molecular structure-function relationships in breadmaking

Molecular size and structure of the gluten polymers that make up the major structural components of wheat are related to their rheological properties via modern polymer rheology concepts. Interactions between polymer chain entanglements and branching are seen to be the key mechanisms determining the rheology of HMW polymers. Recent work confirms the observation that dynamic shear plateau modulus is essentially independent of variations in MW amongst wheat varieties of varying baking performance and is not related to variations in baking performance, and that it is not the size of the soluble glutenin polymers, but the structural and rheological properties of the insoluble polymer fraction that are mainly responsible for variations in baking performance. The rheological properties of gas cell walls in bread doughs are considered to be important in relation to their stability and gas retention during proof and baking, in particular their extensional strain hardening properties. Large deformation rheological properties of gas cell walls were measured using biaxial extension for a number of doughs of varying breadmaking quality at constant strain rate and elevated temperatures in the range 25oC to 60oC. Strain hardening and failure strain of cell walls were both seen to decrease with temperature, with cell walls in good breadmaking doughs remaining stable and retaining their strain hardening properties to higher temperatures (60oC), whilst the cell walls of poor breadmaking doughs became unstable at lower temperatures (45oC to 50oC) and had lower strain hardening. Strain hardening measured at 50oC gave good correlations with baking volume, with the best correlations achieved between those rheological measurements and baking tests which used similar mixing conditions. As predicted by the Considere failure criterion, a strain hardening value of 1 defines a region below which gas cell walls become unstable, and discriminates well between the baking quality of a range of commercial flour blends of varying quality. This indicates that the stability of gas cell walls during baking is strongly related to their strain hardening properties, and that extensional rheological measurements can be used as predictors of baking quality.