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.

Distributed mining of molecular fragments

In real world applications sequential algorithms of data mining and data exploration are often unsuitable for datasets with enormous size, high-dimensionality and complex data structure. Grid computing promises unprecedented opportunities for unlimited computing and storage resources. In this context there is the necessity to develop high performance distributed data mining algorithms. However, the computational complexity of the problem and the large amount of data to be explored often make the design of large scale applications particularly challenging. In this paper we present the first distributed formulation of a frequent subgraph mining algorithm for discriminative fragments of molecular compounds. Two distributed approaches have been developed and compared on the well known National Cancer Institute’s HIV-screening dataset. We present experimental results on a small-scale computing environment.

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.

Accessing biodiversity resources in computational environments from workflow applications

In the Biodiversity World (BDW) project we have created a flexible and extensible Web Services-based Grid environment for biodiversity researchers to solve problems in biodiversity and analyse biodiversity patterns. In this environment, heterogeneous and globally distributed biodiversity-related resources such as data sets and analytical tools are made available to be accessed and assembled by users into workflows to perform complex scientific experiments. One such experiment is bioclimatic modelling of the geographical distribution of individual species using climate variables in order to predict past and future climate-related changes in species distribution. Data sources and analytical tools required for such analysis of species distribution are widely dispersed, available on heterogeneous platforms, present data in different formats and lack interoperability. The BDW system brings all these disparate units together so that the user can combine tools with little thought as to their availability, data formats and interoperability. The current Web Servicesbased Grid environment enables execution of the BDW workflow tasks in remote nodes but with a limited scope. The next step in the evolution of the BDW architecture is to enable workflow tasks to utilise computational resources available within and outside the BDW domain. We describe the present BDW architecture and its transition to a new framework which provides a distributed computational environment for mapping and executing workflows in addition to bringing together heterogeneous resources and analytical tools.

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.

Design, synthesis and computational modelling of aromatic tweezer-molecules as models for chain-folding polymer blends

Novel 'tweezer-type' complexes that exploit the interactions between pi-electron-rich pyrenyl groups and pi-electron deficient diimide units have been designed and synthesised. The component molecules leading to complex formation were accessed readily from commercially available starting materials through short and efficient syntheses. Analysis of the resulting complexes, using the visible charge-transfer band, revealed association constants that increased sequentially from 130 to 11,000 M-1 as increasing numbers of pi-pi-stacking interactions were introduced into the systems. Computational modelling was used to analyse the structures of these complexes, revealing low-energy chain-folded conformations for both components, which readily allow close, multiple pi-pi-stacking and hydrogen bonding to be achieved. In this paper, we give details of our initial studies of these complexes and outline how their behaviour could provide a basis for designing self-healing polymer blends for use in adaptive coating systems. (C) 2008 Elsevier Ltd. All rights reserved.

Geometrical isomers of [TEAH][Co(L-Se)(2)]center dot xH(2)O: synthesis, structural, spectroscopic and computational studies

Trans-1, [HNEt3][Co-III(L-Se)(2)]center dot H2O and cis-1, [HNEt3][Co-III(L-Se)(2)]center dot 3H(2)O have been synthesized and characterized by single-crystal X-ray studies. The counter ion Et3NH+ plays a crucial role in the crystal packing leading to the formation of two distinctly different supramolecular assemblies in the two complexes. In trans-1, Co-bisphenolate units and triethylamine molecules are arranged in a linear fashion leading to a supramolecular columnar assembly along the crystallographic a-axis. In this assembly, triethylammonium ions are sandwiched between successive Co-bisphenolate units and act as gluing agents joining Co-bisphenolate units on either side through C-H center dot center dot center dot pi interactions. In sharp contrast to trans-1, Co-bisphenolate units and triethylammonium ions in cis-1 are arranged in a helical supramolecular assembly through similar C-H center dot center dot center dot pi interactions along the crystallographic b-axis. The Se center dot center dot center dot Se van der Waals interactions may be responsible for the predominant occurrence of the cis-isomer. The cyclic voltammetric studies showed quasi-reversible waves for the cobalt(III) -> cobalt(II) reductions with E-1/2 = 0.635 and 0.628 V vs. Ag/AgCl for cis-1 (at similar to 5 degrees C) and trans-1 (at similar to 25 degrees C), respectively. DFT calculations show that the trans-form is the thermodynamic product with higher stability than the cis-one, which is consistent with the variable temperature H-1 NMR studies

Discovery of three polymorphs of 7-fluoroisatin reveals challenges in using computational crystal structure prediction as a complement to experimental screening

A combined computational and experimental polymorph search was undertaken to establish the crystal forms of 7-fluoroisatin, a simple molecule with no reported crystal structures, to evaluate the value of crystal structure prediction studies as an aid to solid form discovery. Three polymorphs were found in a manual crystallisation screen, as well as two solvates. Form I ( P2(1)/c, Z0 1), found from the majority of solvent evaporation experiments, corresponded to the most stable form in the computational search of Z0 1 structures. Form III ( P21/ a, Z0 2) is probably a metastable form, which was only found concomitantly with form I, and has the same dimeric R2 2( 8) hydrogen bonding motif as form I and the majority of the computed low energy structures. However, the most thermodynamically stable polymorph, form II ( P1 , Z0 2), has an expanded four molecule R 4 4( 18) hydrogen bonding motif, which could not have been found within the routine computational study. The computed relative energies of the three forms are not in accord with experimental results. Thus, the experimental finding of three crystalline polymorphs of 7- fluoroisatin illustrates the many challenges for computational screening to be a tool for the experimental crystal engineer, in contrast to the results for an analogous investigation of 5- fluoroisatin.

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.

C-H...O hydrogen bonding in 4-phenyl-benzaldehyde: a comprehensive crystallographic, spectroscopic and computational study

The crystal structure of 4-phenyl-benzaldehyde reveals the presence of a dimer linked by the C=O and C( 9)-H groups of adjacent molecules. In the liquid phase, the presence of C-(HO)-O-... bonded forms is revealed by both vibrational and NMR spectroscopy. A Delta H value of - 8.2 +/- 0.5 kJ mol(-1) for the dimerisation equilibrium is established from the temperature-dependent intensities of the bands assigned to the carbonyl-stretching modes. The NMR data suggest the preferential engagement of the C(2,6)-H and C(10/12)/C(11)-H groups as hydrogen bond donors, instead of the C(9)-H group. While ab initio calculations for the isolated dimers are unable to corroborate these NMR results, the radial distribution functions obtained from molecular dynamics simulations show a preference for C(2,6)-H and C(10/12)/C(11)-(HO)-O-... contacts relative to the C(9)-(HO)-O-... ones.