Dynamic load balancing for the distributed mining of molecular structures

In molecular biology, it is often desirable to find common properties in large numbers of drug candidates. One family of methods stems from the data mining community, where algorithms to find frequent graphs have received increasing attention over the past years. However, the computational complexity of the underlying problem and the large amount of data to be explored essentially render sequential algorithms useless. In this paper, we present a distributed approach to the frequent subgraph mining problem to discover interesting patterns in molecular compounds. This problem is characterized by a highly irregular search tree, whereby no reliable workload prediction is available. We describe the three main aspects of the proposed distributed algorithm, namely, a dynamic partitioning of the search space, a distribution process based on a peer-to-peer communication framework, and a novel receiverinitiated load balancing algorithm. The effectiveness of the distributed method has been evaluated on the well-known National Cancer Institute’s HIV-screening data set, where we were able to show close-to linear speedup in a network of workstations. The proposed approach also allows for dynamic resource aggregation in a non dedicated computational environment. These features make it suitable for large-scale, multi-domain, heterogeneous environments, such as computational grids.

Dynamic load balancing in parallel KD-tree k-means

One among the most influential and popular data mining methods is the k-Means algorithm for cluster analysis. Techniques for improving the efficiency of k-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting geometrical constraints and an efficient data structure, notably a multidimensional binary search tree (KD-Tree). These techniques allow to reduce the number of distance computations the algorithm performs at each iteration. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient k-Means variants in parallel computing environments. In this work, we provide a parallel formulation of the KD-Tree based k-Means algorithm for distributed memory systems and address its load balancing issue. Three solutions have been developed and tested. Two approaches are based on a static partitioning of the data set and a third solution incorporates a dynamic load balancing policy.

A dynamic causal model of the coupling between pulse stimulation and neural activity

We present a dynamic causal model that can explain context-dependent changes in neural responses, in the rat barrel cortex, to an electrical whisker stimulation at different frequencies. Neural responses were measured in terms of local field potentials. These were converted into current source density (CSD) data, and the time series of the CSD sink was extracted to provide a time series response train. The model structure consists of three layers (approximating the responses from the brain stem to the thalamus and then the barrel cortex), and the latter two layers contain nonlinearly coupled modules of linear second-order dynamic systems. The interaction of these modules forms a nonlinear regulatory system that determines the temporal structure of the neural response amplitude for the thalamic and cortical layers. The model is based on the measured population dynamics of neurons rather than the dynamics of a single neuron and was evaluated against CSD data from experiments with varying stimulation frequency (1–40 Hz), random pulse trains, and awake and anesthetized animals. The model parameters obtained by optimization for different physiological conditions (anesthetized or awake) were significantly different. Following Friston, Mechelli, Turner, and Price (2000), this work is part of a formal mathematical system currently being developed (Zheng et al., 2005) that links stimulation to the blood oxygen level dependent (BOLD) functional magnetic resonance imaging (fMRI) signal through neural activity and hemodynamic variables. The importance of the model described here is that it can be used to invert the hemodynamic measurements of changes in blood flow to estimate the underlying neural activity.

A dynamic mechanistic model of lactic acid metabolism in the rumen

Current feed evaluation systems for ruminants are too imprecise to describe diets in terms of their acidosis risk. The dynamic mechanistic model described herein arises from the integration of a lactic acid (La) metabolism module into an extant model of whole-rumen function. The model was evaluated using published data from cows and sheep fed a range of diets or infused with various doses of La. The model performed well in simulating peak rumen La concentrations (coefficient of determination = 0.96; root mean square prediction error = 16.96% of observed mean), although frequency of sampling for the published data prevented a comprehensive comparison of prediction of time to peak La accumulation. The model showed a tendency for increased La accumulation following feeding of diets rich in nonstructural carbohydrates, although less-soluble starch sources such as corn tended to limit rumen La concentration. Simulated La absorption from the rumen remained low throughout the feeding cycle. The competition between bacteria and protozoa for rumen La suggests a variable contribution of protozoa to total La utilization. However, the model was unable to simulate the effects of defaunation on rumen La metabolism, indicating a need for a more detailed description of protozoal metabolism. The model could form the basis of a feed evaluation system with regard to rumen La metabolism.

Arable crop rotations under abiotic stress: a dynamic economic model

Break crops and multi-crop rotations are common in arable farm management, and the soil quality inherited from a previous crop is one of the parameters that determine the gross margin that is achieved with a given crop from a given parcel of land. In previous work we developed a dynamic economic model to calculate the potential yield and gross margin of a set of crops grown in a selection of typical rotation scenarios, and we reported use of the model to calculate coexistence costs for GM maize grown in a crop rotation. The model predicts economic effects of pest and weed pressures in monthly time steps. Validation of the model in respect of specific traits is proceeding as data from trials with novel crop varieties is published. Alongside this aspect of the validation process, we are able to incorporate data representing the economic impact of abiotic stresses on conventional crops, and then use the model to predict the cumulative gross margin achievable from a sequence of conventional crops grown at varying levels of abiotic stress. We report new progress with this aspect of model validation. In this paper, we report the further development of the model to take account of abiotic stress arising from drought, flood, heat or frost; such stresses being introduced in addition to variable pest and weed pressure. The main purpose is to assess the economic incentive for arable farmers to adopt novel crop varieties having multiple ‘stacked’ traits introduced by means of various biotechnological tools available to crop breeders.

A customizable multi-agent system for distributed data mining

We present a general Multi-Agent System framework for distributed data mining based on a Peer-to-Peer model. Agent protocols are implemented through message-based asynchronous communication. The framework adopts a dynamic load balancing policy that is particularly suitable for irregular search algorithms. A modular design allows a separation of the general-purpose system protocols and software components from the specific data mining algorithm. The experimental evaluation has been carried out on a parallel frequent subgraph mining algorithm, which has shown good scalability performances.

Decentralized load balancing for highly irregular search problems

In this paper, we present a distributed computing framework for problems characterized by a highly irregular search tree, whereby no reliable workload prediction is available. The framework is based on a peer-to-peer computing environment and dynamic load balancing. The system allows for dynamic resource aggregation, does not depend on any specific meta-computing middleware and is suitable for large-scale, multi-domain, heterogeneous environments, such as computational Grids. Dynamic load balancing policies based on global statistics are known to provide optimal load balancing performance, while randomized techniques provide high scalability. The proposed method combines both advantages and adopts distributed job-pools and a randomized polling technique. The framework has been successfully adopted in a parallel search algorithm for subgraph mining and evaluated on a molecular compounds dataset. The parallel application has shown good calability and close-to linear speedup in a distributed network of workstations.

Results of a mechanistic model estimating methane in relation to methane emissions measured in dairy cows

This investigation determines the accuracy of estimation of methanogenesis by a dynamic mechanistic model with real data determined in a respiration trial, where cows were fed a wide range of different carbohydrates included in the concentrates. The model was able to predict ECM (Energy corrected milk) very well, while the NDF digestibility of fibrous feed was less well predicted. Methane emissions were predicted quite well, with the exception of one diet containing wheat. The mechanistic model is therefore a helpful tool to estimate methanogenesis based on chemical analysis and dry matter intake, but the prediction can still be improved.

A model of the hemodynamic response and oxygen delivery to brain

A recent nonlinear system by Friston et al. (2000. NeuroImage 12: 466–477) links the changes in BOLD response to changes in neural activity. The system consists of five subsystems, linking: (1) neural activity to flow changes; (2) flow changes to oxygen delivery to tissue; (3) flow changes to changes in blood volume and venous outflow; (4) changes in flow, volume, and oxygen extraction fraction to deoxyhemoglobin changes; and finally (5) volume and deoxyhemoglobin changes to the BOLD response. Friston et al. exploit, in subsystem 2, a model by Buxton and Frank coupling flow changes to changes in oxygen metabolism which assumes tissue oxygen concentration to be close to zero. We describe below a model of the coupling between flow and oxygen delivery which takes into account the modulatory effect of changes in tissue oxygen concentration. The major development has been to extend the original Buxton and Frank model for oxygen transport to a full dynamic capillary model making the model applicable to both transient and steady state conditions. Furthermore our modification enables us to determine the time series of CMRO2 changes under different conditions, including CO2 challenges. We compare the differences in the performance of the “Friston system” using the original model of Buxton and Frank and that of our model. We also compare the data predicted by our model (with appropriate parameters) to data from a series of OIS studies. The qualitative differences in the behaviour of the models are exposed by different experimental simulations and by comparison with the results of OIS data from brief and extended stimulation protocols and from experiments using hypercapnia.

Controlling nitrate pollution: an integrated approach

The introduction of the EU Water Framework Directive requires policy to address non-point source pollution as part of an overall integrated strategy to improve the ecological status of water bodies. In this paper, we combine an economic optimisation framework with a dynamic simulation model of N transport in the Kennet Catchment to link decisions taken at the farm level to reductions in nitrate concentrations in the River Kennet. We examine a variety of policies targeted at reducing fertiliser use and changing the way in which farm land is used. We find that a tax on nitrogen emerges as the best policy both in terms of cost- and environmental effectiveness. Such a policy involves a considerable reduction in fertiliser use, as well as, a restructuring of land-use away from arable towards increased use of set-aside. Budgetary implications of such a radical move towards set-aside would be huge and hence unlikely to be politically palatable given the objective of reducing the EU budgetary allocation to agriculture. Additionally, the current rise in world demand for food may also mitigate calls for increasing the proportion of land taken out of agricultural production. Although the study succeeds in establishing a link between actions on the farm and nitrate concentrations in the stream water, further work is required to explore the effect of the retention of nitrates in the unsaturated zone and groundwater on this link.

Simulating the effects of grassland management and grass ensiling on methane emission from lactating cows

A dynamic, mechanistic model of enteric fermentation was used to investigate the effect of type and quality of grass forage, dry matter intake (DMI) and proportion of concentrates in dietary dry matter (DM) on variation in methane (CH(4)) emission from enteric fermentation in dairy cows. The model represents substrate degradation and microbial fermentation processes in rumen and hindgut and, in particular, the effects of type of substrate fermented and of pH oil the production of individual volatile fatty acids and CH, as end-products of fermentation. Effects of type and quality of fresh and ensiled grass were evaluated by distinguishing two N fertilization rates of grassland and two stages of grass maturity. Simulation results indicated a strong impact of the amount and type of grass consumed oil CH(4) emission, with a maximum difference (across all forage types and all levels of DM 1) of 49 and 77% in g CH(4)/kg fat and protein corrected milk (FCM) for diets with a proportion of concentrates in dietary DM of 0.1 and 0.4, respectively (values ranging from 10.2 to 19.5 g CH(4)/kg FCM). The lowest emission was established for early Cut, high fertilized grass silage (GS) and high fertilized grass herbage (GH). The highest emission was found for late cut, low-fertilized GS. The N fertilization rate had the largest impact, followed by stage of grass maturity at harvesting and by the distinction between GH and GS. Emission expressed in g CH(4)/kg FCM declined oil average 14% with an increase of DMI from 14 to 18 kg/day for grass forage diets with a proportion of concentrates of 0.1, and on average 29% with an increase of DMI from 14 to 23 kg/day for diets with a proportion of concentrates of 0.4. Simulation results indicated that a high proportion of concentrates in dietary DM may lead to a further reduction of CH, emission per kg FCM mainly as a result of a higher DM I and milk yield, in comparison to low concentrate diets. Simulation results were evaluated against independent data obtained at three different laboratories in indirect calorimetry trials with COWS consuming GH mainly. The model predicted the average of observed values reasonably, but systematic deviations remained between individual laboratories and root mean squared prediction error was a proportion of 0.12 of the observed mean. Both observed and predicted emission expressed in g CH(4)/kg DM intake decreased upon an increase in dietary N:organic matter (OM) ratio. The model reproduced reasonably well the variation in measured CH, emission in cattle sheds oil Dutch dairy farms and indicated that oil average a fraction of 0.28 of the total emissions must have originated from manure under these circumstances.

A simplified method for referring the energy and overheating performance of window design

This paper describes a simplified dynamic thermal model which simulates the energy and overheating performance of windows. To calculate artificial energy use within a room, the model employs the average illuminance method, which takes into account the daylight energy impacting upon the room by the use of hourly climate data. This tool describes the main thermal performance ( heating, cooling and overheating risk) resulting proposed a design of window. The inputs are fewer and simpler than that are required by complicated simulation programmes. The method is suited for the use of architects and engineers at the strategic phase of design, when little is available.

Millennial climatic fluctuations are key to the structure of last glacial ecosystems

Whereas fossil evidence indicates extensive treeless vegetation and diverse grazing megafauna in Europe and northern Asia during the last glacial, experiments combining vegetation models and climate models have to-date simulated widespread persistence of trees. Resolving this conflict is key to understanding both last glacial ecosystems and extinction of most of the mega-herbivores. Using a dynamic vegetation model (DVM) we explored the implications of the differing climatic conditions generated by a general circulation model (GCM) in “normal” and “hosing” experiments. Whilst the former approximate interstadial conditions, the latter, designed to mimic Heinrich Events, approximate stadial conditions. The “hosing” experiments gave simulated European vegetation much closer in composition to that inferred from fossil evidence than did the “normal” experiments. Given the short duration of interstadials, and the rate at which forest cover expanded during the late-glacial and early Holocene, our results demonstrate the importance of millennial variability in determining the character of last glacial ecosystems.

Last glacial vegetation of northern Eurasia

In order to investigate the potential role of vegetation changes in megafaunal extinctions during the later part of the last glacial stage and early Holocene (42–10 ka BP), the palaeovegetation of northern Eurasia and Alaska was simulated using the LPJ-GUESS dynamic vegetation model. Palaeoclimatic driving data were derived from simulations made for 22 time slices using the Hadley Centre Unified Model. Modelled annual net primary productivity (aNPP) of a series of plant functional types (PFTs) is mapped for selected time slices and summarised for major geographical regions for all time slices. Strong canonical correlations are demonstrated between model outputs and pollen data compiled for the same period and region. Simulated aNPP values, especially for tree PFTs and for a mesophilous herb PFT, provide evidence of the structure and productivity of last glacial vegetation. The mesophilous herb PFT aNPP is higher in many areas during the glacial than at present or during the early Holocene. Glacial stage vegetation, whilst open and largely treeless in much of Europe, thus had a higher capacity to support large vertebrate herbivore populations than did early Holocene vegetation. A marked and rapid decrease in aNPP of mesophilous herbs began shortly after the Last Glacial Maximum, especially in western Eurasia. This is likely implicated in extinction of several large herbivorous mammals during the latter part of the glacial stage and the transition to the Holocene.

Modelling of control options for an outbreak of Mycoplasma gallisepticum in egg production: a decision support tool

Mycoplasma gallisepticum (MG) is a bacterium that causes respiratory disease in chickens, leading to reduced egg production. A dynamic simulation model was developed that can be used to assess the costs and benefits of control using antimicrobials or vaccination in caged or free range systems. The intended users are veterinarians and egg producers. A user interface is provided for input of flock specific parameters. The economic consequence of an MG outbreak is expressed as a reduction in expected egg output. The model predicts that either vaccination or microbial treatment can approximately halve potential losses from MG in some circumstances. Sensitivity analysis is used to test assumptions about infection rate and timing of an outbreak. Feedback from veterinarians points to the value of the model as a discussion tool with producers.