A hybrid genetic algorithm for the optimal constrained web service selection problem in web service composition

Web service composition is an important problem in web service based systems. It is about how to build a new value-added web service using existing web services. A web service may have many implementations, all of which have the same functionality, but may have different QoS values. Thus, a significant research problem in web service composition is how to select a web service implementation for each of the web services such that the composite web service gives the best overall performance. This is so-called optimal web service selection problem. There may be mutual constraints between some web service implementations. Sometimes when an implementation is selected for one web service, a particular implementation for another web service must be selected. This is so called dependency constraint. Sometimes when an implementation for one web service is selected, a set of implementations for another web service must be excluded in the web service composition. This is so called conflict constraint. Thus, the optimal web service selection is a typical constrained ombinatorial optimization problem from the computational point of view. This paper proposes a new hybrid genetic algorithm for the optimal web service selection problem. The hybrid genetic algorithm has been implemented and evaluated. The evaluation results have shown that the hybrid genetic algorithm outperforms other two existing genetic algorithms when the number of web services and the number of constraints are large.

Partitioning composite web services for decentralized execution using a genetic algorithm

Composite web services comprise several component web services. When a composite web service is executed centrally, a single web service engine is responsible for coordinating the execution of the components, which may create a bottleneck and degrade the overall throughput of the composite service when there are a large number of service requests. Potentially this problem can be handled by decentralizing execution of the composite web service, but this raises the issue of how to partition a composite service into groups of component services such that each group can be orchestrated by its own execution engine while ensuring acceptable overall throughput of the composite service. Here we present a novel penalty-based genetic algorithm to solve the composite web service partitioning problem. Empirical results show that our new algorithm outperforms existing heuristic-based solutions.

QoS-oriented sesource allocation and scheduling of multiple composite web services in a hybrid cloud using a random-key genetic algorithm

In cloud computing resource allocation and scheduling of multiple composite web services is an important challenge. This is especially so in a hybrid cloud where there may be some free resources available from private clouds but some fee-paying resources from public clouds. Meeting this challenge involves two classical computational problems. One is assigning resources to each of the tasks in the composite web service. The other is scheduling the allocated resources when each resource may be used by more than one task and may be needed at different points of time. In addition, we must consider Quality-of-Service issues, such as execution time and running costs. Existing approaches to resource allocation and scheduling in public clouds and grid computing are not applicable to this new problem. This paper presents a random-key genetic algorithm that solves new resource allocation and scheduling problem. Experimental results demonstrate the effectiveness and scalability of the algorithm.

Genetic Analysis of Tolerance to Rice Tungro Bacilliform Virus in Rice (Oryza sativa L.) Through Agroinoculation

Balimau Putih [an Indonesian cultivar tolerant to rice tungro bacilliform virus (RTBV)] was crossed with IR64 (RTBV, susceptible variety) to produce the three filial generations F1, F2 and F3. Agroinoculation was used to introduce RTBV into the test plants. RTBV tolerance was based on the RTBV level in plants by analysis of coat protein using enzyme-linked immunosorbent assay. The level of RTBV in cv. Balimau Putih was significantly lower than that of IR64 and the susceptible control, Taichung Native 1. Mean RTBV levels of the F1, F2 and F3 populations were comparable with one another and with the average of the parents. Results indicate that there was no dominance and an additive gene action may control the expression of tolerance to RTBV. Tolerance based on the level of RTBV coat protein was highly heritable (0.67) as estimated using the mean values of F3 lines, suggesting that selection for tolerance to RTBV can be performed in the early selfing generations using the technique employed in this study. The RTBV level had a negative correlation with plant height, but positive relationship with disease index value

Railway junction conflict resolution by genetic algorithm

In general, simple and traditional methods are applied to resolve traffic conflicts at railway junctions. They are, however, either inefficient or computationally demanding. A simple genetic algorithm is presented to enable a search for a near optimal resolution to be carried out while meeting the constraints on generation evolution and minimising the search time.

Genetic resources in wild and cultured stocks of the Asian mud crab, Scylla paramamosain

The mud crab (Scylla spp.) aquaculture industry has expanded rapidly in recent years in many countries in the Indo - West Pacific (IWP) region as an alternative to marine shrimp culture because of significant disease outbreaks and associated failures of many shrimp culture industries in the region. Currently, practices used to produce and manage breeding crabs in hatcheries may compromise levels of genetic diversity, ultimately compromising growth rates, disease resistance and stock productivity. Therefore, to avoid “genetic pollution” and its harmful effects and to promote further development of mud crab aquaculture and fisheries in a sustainable way, a greater understanding of the genetic attributes of wild and cultured mud crab stocks is required. Application of these results can provide benefits for managing wild and cultured Asian mud crab populations for multiple purposes including for commercial production, recreation and conservation and to increase profitability and sustainability of newly emerging crab culture industries. Phylogeographic patterns and the genetic structure of Asian mud crab populations across the IWP were assessed to determine if they were concordant with those of other widespread taxa possessing pelagic larvae of relatively long duration. A 597 bp fragment of the mitochondrial DNA COI gene was amplified and screened for variation in a total of 297 individuals of S. paramamosain from six sampling sites across the species’ natural geographical distribution in the IWP and 36 unique haplotypes were identified. Haplotype diversities per site ranged from 0.516 to 0.879. Nucleotide diversity estimates among haplotypes were 0.11% – 0.48%. Maximum divergence observed among S. paramamosain samples was 1.533% and samples formed essentially a single monophyletic group as no obvious clades were related to geographical location of sites. A weak positive relationship was observed however, between genetic distance and geographical distance among sites. Microsatellite markers were then used to assess contemporary gene flow and population structure in Asian mud crab populations sampled across their natural distribution in the IWP. Eight microsatellite loci were screened in sampled S. paramamosain populations and all showed high allelic diversity at all loci in sampled populations. In total, 344 individuals were analysed, and 304 microsatellite alleles were found across the 8 loci. The mean number of alleles per locus at each site ranged from 20.75 to 28.25. Mean allelic richness per site varied from 17.2 to 18.9. All sites showed high levels of heterozygosity as average expected heterozygosities for all loci ranged from 0.917 – 0.953 while mean observed heterozygosity ranged from 0.916 – 0.959. Allele diversities were similar at all sites and across all loci. The results did not show any evidence for major differences in allele frequencies among sites and patterns of allele frequencies were very similar in all populations across all loci. Estimates of population differentiation (FST) were relatively low and most probably largely reflect intra – individual variation for very highly variable loci. Results from nDNA analysis showed evidence for only very limited population genetic structure among sampled S. paramamosain, and a positive and significant association for genetic and geographical distance among sample sites. Microsatellite markers were then employed to determine if adequate levels of genetic diversity has been captured in crab hatcheries for the breeding cycle. The results showed that all microsatellite loci were polymorphic in hatchery samples. Culture populations were in general, highly genetically depauperate, compared with comparable wild populations, with only 3 to 8 alleles recorded for the same loci set per population. In contrast, very high numbers of alleles per locus were found in reference wild S. paramamosain populations, which ranged from 18 to 46 alleles per locus per population. In general, this translates into a 3 to 10 fold decline in mean allelic richness per locus in all culture stocks compared with wild reference counterparts. Furthermore, most loci in all cultured S. paramamosain samples showed departures from HWE equilibrium. Allele frequencies were very different in culture samples from that present in comparable wild reference samples and this in particular, was reflected in a large decline in allele diversity per locus. The pattern observed was best explained by significant impacts of breeding practices employed in hatcheries rather than natural differentiation among wild populations used as the source of brood stock. Recognition of current problems and management strategies for the species both for the medium and long-term development of the new culture industry are discussed. The priority research to be undertaken over the medium term for S. paramamosain should be to close the life cycle fully to allow individuals to be bred on demand and their offspring equalised to control broodstock reproductive contributions. Establishing a broodstock register and pedigree mating system will be required before any selection program is implemented. This will ensure that sufficient genetic variation will be available to allow genetic gains to be sustainably achieved in a future stock improvement program. A fundamental starting point to improve hatchery practices will be to encourage farmers and hatchery managers to spawn more females in their hatcheries as it will increase background genetic diversity in culture stocks. Combining crablet cohorts from multiple hatcheries into a single cohort for supply to farmers or rotation of breeding females regularly in hatcheries will help to address immediate genetic diversity problems in culture stocks. Application of these results can provide benefits for managing wild and cultured Asian mud crab populations more efficiently. Over the long-term, application of data on genetic diversity in wild and cultured stocks of Asian mud crab will contribute to development of sustainable and productive culture industries in Vietnam and other countries in the IWP and can contribute towards conservation of wild genetic resources.

Influence of historical landscapes, drainage evolution and ecological traits on patterns of genetic diversity in Southeast Asian freshwater snakehead fishes

Snakehead fishes in the family Channidae are obligate freshwater fishes represented by two extant genera, the African Parachannna and the Asian Channa. These species prefer still or slow flowing water bodies, where they are top predators that exercise high levels of parental care, have the ability to breathe air, can tolerate poor water quality, and interestingly, can aestivate or traverse terrestrial habitat in response to seasonal changes in freshwater habitat availability. These attributes suggest that snakehead fishes may possess high dispersal potential, irrespective of the terrestrial barriers that would otherwise constrain the distribution of most freshwater fishes. A number of biogeographical hypotheses have been developed to account for the modern distributions of snakehead fishes across two continents, including ancient vicariance during Gondwanan break-up, or recent colonisation tracking the formation of suitable climatic conditions. Taxonomic uncertainty also surrounds some members of the Channa genus, as geographical distributions for some taxa across southern and Southeast (SE) Asia are very large, and in one case is highly disjunct. The current study adopted a molecular genetics approach to gain an understanding of the evolution of this group of fishes, and in particular how the phylogeography of two Asian species may have been influenced by contemporary versus historical levels of dispersal and vicariance. First, a molecular phylogeny was constructed based on multiple DNA loci and calibrated with fossil evidence to provide a dated chronology of divergence events among extant species, and also within species with widespread geographical distributions. The data provide strong evidence that trans-continental distribution of the Channidae arose as a result of dispersal out of Asia and into Africa in the mid–Eocene. Among Asian Channa, deep divergence among lineages indicates that the Oligocene-Miocene boundary was a time of significant species radiation, potentially associated with historical changes in climate and drainage geomorphology. Mid-Miocene divergence among lineages suggests that a taxonomic revision is warranted for two taxa. Deep intra-specific divergence (~8Mya) was also detected between C. striata lineages that occur sympatrically in the Mekong River Basin. The study then examined the phylogeography and population structure of two major taxa, Channa striata (the chevron snakehead) and the C. micropeltes (the giant snakehead), across SE Asia. Species specific microsatellite loci were developed and used in addition to a mitochondrial DNA marker (Cyt b) to screen neutral genetic variation within and among wild populations. C. striata individuals were sampled across SE Asia (n=988), with the major focus being the Mekong Basin, which is the largest drainage basin in the region. The distributions of two divergent lineages were identified and admixture analysis showed that where they co-occur they are interbreeding, indicating that after long periods of evolution in isolation, divergence has not resulted in reproductive isolation. One lineage is predominantly confined to upland areas of northern Lao PDR to the north of the Khorat Plateau, while the other, which is more closely related to individuals from southern India, has a widespread distribution across mainland SE Asian and Sumatra. The phylogeographical pattern recovered is associated with past river networks, and high diversity and divergence among all populations sampled reveal that contemporary dispersal is very low for this taxon, even where populations occur in contiguous freshwater habitats. C. micropeltes (n=280) were also sampled from across the Mekong River Basin, focusing on the lower basin where it constitutes an important wild fishery resource. In comparison with C. striata, allelic diversity and genetic divergence among populations were extremely low, suggesting very recent colonisation of the greater Mekong region. Populations were significantly structured into at least three discrete populations in the lower Mekong. Results of this study have implications for establishing effective conservation plans for managing both species, that represent economically important wild fishery resources for the region. For C. micropeltes, it is likely that a single fisheries stock in the Tonle Sap Great Lake is being exploited by multiple fisheries operations, and future management initiatives for this species in this region will need to account for this. For C. striata, conservation of natural levels of genetic variation will require management initiatives designed to promote population persistence at very localised spatial scales, as the high level of population structuring uncovered for this species indicates that significant unique diversity is present at this fine spatial scale.

Comparison of Nucleotide Sequences between Northern and Southern Philippine Isolates of Rice Grassy Stunt Virus Indicates Occurrence of Natural Genetic Reassortment

Rice grassy stunt virus is a member of the genus Tenuivirus, is persistently transmitted by a brown planthopper, and has occurred in rice plants in South, Southeast, and East Asia (similar to North and South America). We determined the complete nucleotide (nt) sequences of RNAs 1 (9760 nt), 2 (4069 nt), 3 (3127 nt), 4 (2909 nt), 5 (2704 nt), and 6 (2590 nt) of a southern Philippine isolate from South Cotabato and compared them with those of a northern Philippine isolate from Laguna (Toriyama et al., 1997, 1998). The numbers of nucleotides in the terminal untranslated regions and open reading frames were identical between the two isolates except for the 5′ untranslated region of the complementary strand of RNA 4. Overall nucleotide differences between the two isolates were only 0.08% in RNA 1, 0.58% in RNA 4, and 0.26% in RNA 5, whereas they were 2.19% in RNA 2, 8.38% in RNA 3, and 3.63% in RNA 6. In the intergenic regions, the two isolates differed by 9.12% in RNA 2, 11.6% in RNA 3, and 6.86% in RNA 6 with multiple consecutive nucleotide deletion/insertions, whereas they differed by only 0.78% in RNA 4 and 0.34% in RNA 5. The nucleotide variation in the intergenic region of RNA 6 within the South Cotabato isolate was only 0.33%. These differences in accumulation of mutations among individual RNA segments indicate that there was genetic reassortment in the two geographical isolates; RNAs 1, 4, and 5 of the two isolates came from a common ancestor, whereas RNAs 2, 3, and 6 were from two different ancestors.