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.

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.

Efficient mining of discriminative molecular fragments

Frequent pattern discovery in structured data is receiving an increasing attention in many application areas of sciences. However, the computational complexity and the large amount of data to be explored often make the sequential algorithms unsuitable. In this context high performance distributed computing becomes a very interesting and promising approach. In this paper we present a parallel formulation of the frequent subgraph mining problem to discover interesting patterns in molecular compounds. The application is characterized by a highly irregular tree-structured computation. No estimation is available for task workloads, which show a power-law distribution in a wide range. The proposed approach allows dynamic resource aggregation and provides fault and latency tolerance. These features make the distributed application suitable for multi-domain heterogeneous environments, such as computational Grids. The distributed application has been evaluated on the well known National Cancer Institute’s HIV-screening dataset.

Climate vs. soil factors in local adaptation of two common plant species

Evolutionary theory suggests that divergent natural selection in heterogeneous environments can result in locally adapted plant genotypes. To understand local adaptation it is important to study the ecological factors responsible for divergent selection. At a continental scale, variation in climate can be important while at a local scale soil properties could also play a role. We designed an experiment aimed to disentangle the role of climate and ( abiotic and biotic) soil properties in local adaptation of two common plant species. A grass (Holcus lanatus) and a legume ( Lotus corniculatus), as well as their local soils, were reciprocally transplanted between three sites across an Atlantic-Continental gradient in Europe and grown in common gardens in either their home soil or foreign soils. Growth and reproductive traits were measured over two growing seasons. In both species, we found significant environmental and genetic effects on most of the growth and reproductive traits and a significant interaction between the two environmental effects of soil and climate. The grass species showed significant home site advantage in most of the fitness components, which indicated adaptation to climate. We found no indication that the grass was adapted to local soil conditions. The legume showed a significant home soil advantage for number of fruits only and thus a weak indication of adaptation to soil and no adaptation to climate. Our results show that the importance of climate and soil factors as drivers of local adaptation is species-dependent. This could be related to differences in interactions between plant species and soil biota.

Evaluation of cumulative externality: environmental economics, oligopoly and the private provision of public goods

This paper evaluates environmental externality when the structure of the externality is cumulative. The evaluation exercise is based on the assumption that the agents in question form conjectural variations. A number of environments are encompassed within this classification and have received due attention in the literature. Each of these heterogeneous environments, however, possesses considerable analytical homogeneity and permit subscription to a general model treatment. These environments include environmental externality, oligopoly and the analysis of the private provision of public goods. We highlight the general analytical approach by focusing on this latter context, in which debate centers around four issues: the existence of free-riding, the extent to which contributions are matched equally across individuals, the nature of conjectures consistent with equilibrium, and the allocative inefficiency of alternative regimes. This paper resolves each of these issues, with the following conclusions: A consistent-conjectures equilibrium exists in the private provision of public goods. It is the monopolistic-conjectures equilibrium. Agents act identically, contributing positive amounts of the public good in an efficient allocation of resources. There is complete matching of contributions among agents, no free-riding, and the allocation is independent of the number of members within the community. Thus the Olson conjecture—that inefficiency is exacerbated by community size—has no foundation in a consistent-conjectures, cumulative-externality, context (212 words).

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.

Homogeneous and heterogeneous distributed classification for pocket data mining

Pocket Data Mining (PDM) describes the full process of analysing data streams in mobile ad hoc distributed environments. Advances in mobile devices like smart phones and tablet computers have made it possible for a wide range of applications to run in such an environment. In this paper, we propose the adoption of data stream classification techniques for PDM. Evident by a thorough experimental study, it has been proved that running heterogeneous/different, or homogeneous/similar data stream classification techniques over vertically partitioned data (data partitioned according to the feature space) results in comparable performance to batch and centralised learning techniques.