A genetic algorithm for the multi-source and multi-sink minimum vertex cut problem and its applications

We present a new penalty-based genetic algorithm for the multi-source and multi-sink minimum vertex cut problem, and illustrate the algorithm’s usefulness with two real-world applications. It is proved in this paper that the genetic algorithm always produces a feasible solution by exploiting some domain-specific knowledge. The genetic algorithm has been implemented on the example applications and evaluated to show how well it scales as the problem size increases.

The genetic basis of human height : the role of estrogen

Height is a complex physical trait that displays strong heritability. Adult height is related to length of the long bones, which is determined by growth at the epiphyseal growth plate. Longitudinal bone growth occurs via the process of endochondral ossification, where bone forms over the differentiating cartilage template at the growth plate. Estrogen plays a major role in regulating longitudinal bone growth and is responsible for inducing the pubertal growth spurt and fusion of the epiphyseal growth plate. However, the mechanism by which estrogen promotes epiphyseal fusion is poorly understood. It has been hypothesised that estrogen functions to regulate growth plate fusion by stimulating chondrocyte apoptosis, angiogenesis and bone cell invasion in the growth plate. Another theory has suggested that estrogen exposure exhausts the proliferative capacity of growth plate chondrocytes, which accelerates the process of chondrocyte senescence, leading to growth plate fusion. The overall objective of this study was to gain a greater understanding of the molecular mechanisms behind estrogen-mediated growth and height attainment by examining gene regulation in chondrocytes and the role of some of these genes in normal height inheritance. With the heritability of height so well established, the initial hypothesis was that genetic variation in candidate genes associated with longitudinal bone growth would be involved in normal adult height variation. The height-related genes FGFR3, CBFA1, ER and CBFA1 were screened for novel polymorphisms using denaturing HPLC and RFLP analysis. In total, 24 polymorphisms were identified. Two SNPs in ER (rs3757323 C>T and rs1801132 G>C) were strongly associated with adult male height and displayed an 8 cm and 9 cm height difference between homozygous genotypes, respectively. The TC haplotype of these SNPs was associated with a 6 cm decrease in height and remarkably, no homozygous carriers of the TC haplotype were identified in tall subjects. No significant associations with height were found for polymorphisms in the FGFR3, CBFA1 or VDR genes. In the epiphyseal growth plate, chondrocyte proliferation, matrix synthesis and chondrocyte hypertrophy are all major contributors to long bone growth. As estrogen plays such a significant role in both growth and final height attainment, another hypothesis of this study was that estrogen exerted its effects in the growth plate by influencing chondrocyte proliferation and mediating the expression of chondrocyte marker genes. The examination of genes regulated by estrogen in chondrocyte-like cells aimed to identify potential regulators of growth plate fusion, which may further elucidate mechanisms involved in the cessation of linear growth. While estrogen did not dramatically alter the proliferation of the SW1353 cell line, gene expression experiments identified several estrogen regulated genes. Sixteen chondrocyte marker genes were examined in response to estrogen concentrations ranging from 10-12 M to 10-8 M over varying time points. Of the genes analysed, IHH, FGFR3, collagen II and collagen X were not readily detectable and PTHrP, GHR, ER, BMP6, SOX9 and TGF1 mRNAs showed no significant response to estrogen treatments. However, the expression of MMP13, CBFA1, BCL-2 and BAX genes were significantly decreased. Interestingly, the majority of estrogen regulated genes in SW1353 cells are expressed in the hypertrophic zone of the growth plate. Estrogen is also known to regulate systemic GH secretion and local GH action. At the molecular level, estrogen functions to inhibit GH action by negatively regulating GH signalling. GH treated SW1353 cells displayed increases in MMP9 mRNA expression (4.4-fold) and MMP13 mRNA expression (64-fold) in SW1353 cells. Increases were also detected in their respective proteins. Treatment with AG490, an established JAK2 inhibitor, blocked the GH mediated stimulation of both MMP9 and MMP13 mRNA expression. The application of estrogen and GH to SW1353 cells attenuated GH-stimulated MMP13 levels, but did not affect MMP9 levels. Investigation of GH signalling revealed that SW1353 cells have high levels of activated JAK2 and exposure to GH, estrogen, AG490 and other signalling inhibitors did not affect JAK2 phosphorylation. Interestingly, AG490 treatment dramatically decreased ERK2 signalling, although GH did stimulate ERK2 phosphorylation above control levels. AG490 also decreased CBFA1 expression, a transcription factor known to activate MMP9 and MMP13. Finally, GH and estrogen treatment increased expression of SOCS3 mRNA, suggesting that SOCS3 may regulate JAK/STAT signalling in SW1353 cells. The modulation of GH-mediated MMP expression by estrogen in SW1353 cells represents a potentially novel mechanism by which estrogen may regulate longitudinal bone growth. However, further investigation is required in order to elucidate the precise mechanisms behind estrogen and GH regulation of MMP13 expression in SW1353 cells. This study has provided additional evidence that estrogen and the ER gene are major factors in the regulation of growth and the determination of adult height. Newly identified polymorphisms in the ER gene not only contribute to our understanding of the genetic basis of human height, but may also be useful in association studies examining other complex traits. This study also identified several estrogen regulated genes and indicated that estrogen modifies the expression of genes which are primarily expressed in the hypertrophic region of the epiphyseal growth plate. Furthermore, synergistic studies incorporating GH and estrogen have revealed the ability of estrogen to attenuate the effects of GH on MMP13 expression, revealing potential pathways by which estrogen may modulate growth plate fusion, longitudinal bone growth and even arthritis.

The Queensland study of melanoma : Environmental and genetic associations (Q-MEGA); Study design, baseline characteristics, and repeatability of phenotype and sun exposure measures

Cutaneous malignant melanoma (CMM) is a major health issue in Queensland, Australia, which has the world’s highest incidence. Recent molecular and epidemiologic studies suggest that CMM arises through multiple etiological pathways involving gene-environment interactions. Understanding the potential mechanisms leading to CMM requires larger studies than those previously conducted. This article describes the design and baseline characteristics of Q-MEGA, the Queensland Study of Melanoma: Environmental and Genetic Associations, which followed up 4 population-based samples of CMM patients in Queensland, including children, adolescents, men aged over 50, and a large sample of adult cases and their families, including twins. Q-MEGA aims to investigate the roles of genetic and environmental factors, and their interaction, in the etiology of melanoma. Three thousand, four hundred and seventy-one participants took part in the follow-up study and were administered a computer-assisted telephone interview in 2002-2005. Updated data on environmental and phenotypic risk factors, and 2777 blood samples were collected from interviewed participants as well as a subset of relatives. This study provides a large and well-described population-based sample of CMM cases with follow-up data. Characteristics of the cases and repeatability of sun exposure and phenotype measures between the baseline and the follow-up surveys, from 6 to 17 years later, are also described.

QoS-Based Web Service Scheduling Accommodating Inter-Service Dependencies Using Minimal-Conflict Hill-Climbing Repair Genetic Algorithm

In the filed of semantic grid, QoS-based Web service scheduling for workflow optimization is an important problem.However, in semantic and service rich environment like semantic grid, the emergence of context constraints on Web services is very common making the scheduling consider not only quality properties of Web services, but also inter service dependencies which are formed due to the context constraints imposed on Web services. In this paper, we present a repair genetic algorithm, namely minimal-conflict hill-climbing repair genetic algorithm, to address scheduling optimization problems in workflow applications in the presence of domain constraints and inter service dependencies. Experimental results demonstrate the scalability and effectiveness of the genetic algorithm.

A Penalty-based Genetic Algorithm for QoS-AwareWeb Service Composition with Inter-Service Dependencies and Conflicts

In Web service based systems, new value-added Web services can be constructed by integrating existing Web services. A Web service may have many implementations, which are functionally identical, but have different Quality of Service (QoS) attributes, such as response time, price, reputation, reliability, availability and so on. Thus, a significant research problem in Web service composition is how to select an implementation for each of the component Web services so that the overall QoS of the composite Web service is optimal. This is so called QoS-aware Web service composition problem. In some composite Web services there are some dependencies and conflicts between the Web service implementations. However, existing approaches cannot handle the constraints. This paper tackles the QoS-aware Web service composition problem with inter service dependencies and conflicts using a penalty-based genetic algorithm (GA). Experimental results demonstrate the effectiveness and the scalability of the penalty-based GA.

QoS-based web service composition accommodating inter-service dependencies using minimal-conflict , hill-climbing repair genetic algorithm

In the field of semantic grid, QoS-based Web service composition is an important problem. In semantic and service rich environment like semantic grid, the emergence of context constraints on Web services is very common making the composition consider not only QoS properties of Web services, but also inter service dependencies and conflicts which are formed due to the context constraints imposed on Web services. In this paper, we present a repair genetic algorithm, namely minimal-conflict hill-climbing repair genetic algorithm, to address the Web service composition optimization problem in the presence of domain constraints and inter service dependencies and conflicts. Experimental results demonstrate the scalability and effectiveness of the genetic algorithm.

Regulatory approaches to genetic testing in insurance

Rapid advancements in the field of genetic science have engendered considerable debate, speculation, misinformation and legislative action worldwide. While programs such as the Human Genome Project bring the prospect of seemingly miraculous medical advancements within imminent reach, they also create the potential for significant invasions of traditional areas of privacy and human dignity through laying the potential foundation for new forms of discrimination in insurance, employment and immigration regulation. The insurance industry, which has of course, traditionally been premised on discrimination as part of its underwriting process, is proving to be the frontline of this regulatory battle with extensive legislation, guidelines and debate marking its progress.

Improved joint control using a genetic algorithm for a humanoid robot

This paper describes experiments conducted in order to simultaneously tune 15 joints of a humanoid robot. Two Genetic Algorithm (GA) based tuning methods were developed and compared against a hand-tuned solution. The system was tuned in order to minimise tracking error while at the same time achieve smooth joint motion. Joint smoothness is crucial for the accurate calculation of online ZMP estimation, a prerequisite for a closedloop dynamically stable humanoid walking gait. Results in both simulation and on a real robot are presented, demonstrating the superior smoothness performance of the GA based methods.

A penalty-based genetic algorithm for the composite SaaS placement problem in the cloud

Cloud computing is a latest new computing paradigm where applications, data and IT services are provided over the Internet. Cloud computing has become a main medium for Software as a Service (SaaS) providers to host their SaaS as it can provide the scalability a SaaS requires. The challenges in the composite SaaS placement process rely on several factors including the large size of the Cloud network, SaaS competing resource requirements, SaaS interactions between its components and SaaS interactions with its data components. However, existing applications’ placement methods in data centres are not concerned with the placement of the component’s data. In addition, a Cloud network is much larger than data center networks that have been discussed in existing studies. This paper proposes a penalty-based genetic algorithm (GA) to the composite SaaS placement problem in the Cloud. We believe this is the first attempt to the SaaS placement with its data in Cloud provider’s servers. Experimental results demonstrate the feasibility and the scalability of the GA.

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.